Что проще реализовать: 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 дерева, однако, может быть трудно реализовать в большинстве языков программирования из-за большого количества особых случаев, связанных с операциями над деревом.Красно-чёрные деревья проще реализовать, поэтому обычно их используют.

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

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

Answer 1

часть о "большем числе особых случаев" кажется мне довольно отсталой (я думаю, что именно в РБ большое количество особых случаев, а не 2-3-4)

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

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

Это знаменитое определение из статьи Окасаки