Что проще реализовать: 2-3-4 Дерево или Красно-Черное дерево?

Question

В учебнике, который я изучаю из (Lafore), впервые представлены красно-черные деревья и не содержит никакого псевдокода, хотя связанные с ним алгоритмы представляются довольно сложными, с множеством уникальных случаев.

Далее он представляет 2-3-4 Деревья, которые мне кажутся намного проще понять, и я бы предположил, что реализовать. Он включает в себя некоторый фактический Java-код, который очень ясен. Кажется, он подразумевает, что 2-3-4 легче реализовать, и я согласен с тем, что я видел до сих пор.

Википедии, однако, говорит обратное ... Я думаю, что это неправильно, возможно:

http://en.wikipedia.org/wiki/2-3-4_tree

2-3-4 деревья изометрия красно-черных деревьев, а это означает, что они эквивалентные структуры данных. Другими словами, для каждых 2-3-4 деревьев существует по крайней мере одно дерево красно-черного дерева с элементами данных в того же порядка. Более того, операции вставки и удаления на 2-3-4 деревьях , которые вызывают разложения, разрывы и слияния узлов, эквивалентны цвету и поворотам цветных изображений на красно-черных деревьях . Вступление к красно-черным деревьям обычно вводят 2-3-4 деревьев, потому что они концептуально проще. 2-3-4 деревья, однако, могут быть трудными реализовать на большинстве языков программирования из-за большого количества особых случаев, связанных с операциями на дереве. Красно-черные деревья проще в применении, поэтому их обычно используют.

В частности, часть о «большем количестве специальных случаев» кажется довольно назад ко мне (я думаю, что это RB, которые имеют большое количество особых случаев, а не 2-3-4). Но, я все еще учусь (и до сих пор честно не совсем полностью обернул голову вокруг красно-черных деревьев), поэтому мне бы хотелось услышать другие мнения.

В качестве опоры ... хотя я согласен с большей частью того, что говорит Лафорд, я думаю, что интересно, что он представил их в противоположном порядке по сравнению с тем, что, по словам Википедии, является обычным (2-3-4 до РБ). Я думаю, что 2-3-4 сначала будет иметь больше смысла, так как RB гораздо труднее концептуализировать. Возможно, он выбрал этот порядок, потому что RB был более тесно связан с BST, который он только что закончил в предыдущей главе.

Answer 1

часть о «большем количестве специальных случаев» кажется довольно назад ко мне (я думаю, что это RB, которые имеют большое количество особых случаев, а не 2-3-4)

RB Деревья могут быть реализованы в дюжине строк, если у вас есть соответствие шаблону в вашем langugage:

data Color = R | B 
data Tree a = E | T Color (Tree a) a (Tree a) 

balance :: Color -> Tree a -> a -> Tree a -> Tree a 
balance B (T R (T R a x b) y c   ) z d        = T R (T B a x b) y (T B c z d) 
balance B (T R a   x (T R b y c)) z d        = T R (T B a x b) y (T B c z d) 
balance B a        x (T R (T R b y c) z d   ) = T R (T B a x b) y (T B c z d) 
balance B a        x (T R b   y (T R c z d)) = T R (T B a x b) y (T B c z d) 
balance col a x b = T col a x b 

insert :: Ord a => a -> Tree a -> Tree a 
insert x s = T B a y b where 
    ins E   = T R E x E 
    ins s@(T col a y b) 
    | x < y  = balance col (ins a) y b 
    | x > y  = balance col a y (ins b) 
    | otherwise = s 
    T _ a y b = ins s 

Это известное определение from Okasaki's paper