3 ms·
On constructing 2-3 trees (2018) [pdf]
- kazinator 3y agoRed-black trees have the same "black height" from the root to every leaf; red nodes do not count toward black height, but are limited in number: a red node cannot have red child. Thus at most half the nodes can be red in a given path to a leaf, and that keeps the tree sufficiently balanced for efficient search operations. A 2-3 tree is formed from red-black when red nodes are absorbed into their parent as an extra child. We get a height-balanced tree (as required) since the equal black heights become actual heights. When I learned that years ago, I lost interest in 2-3 trees.
- zogrodea 3y ago2-3 Trees do have less (or actually no) storage metadata than AVL and Red-Black Trees which store one bit each node (lg n storage complexity in total), and I personally appreciate that about them. Another balanced tree described by the author of this PDF, Ralf Hinze, helped me implement immutable and purely functional Ropes which is faster than any other I know of that avoids mutation. They are 1-2 Brother Trees[0], which have less storage cost than AVL and Red Black Trees but more than that of 2-3 Trees. (Some nodes in a 1-2 Brother Tree have no data associated with them, but there is no metadata used for balancing otherwise unlike an AVL/RB Tree node which always has an integer.) A nice property of both 1-2 Brother Trees and 2-3 Trees (besides lower metadata) is that they both grow upwards when inserted into instead of doing rotations. That made it easier to implement a Rope because minimal modifications to the balancing algorithm were needed to split a long leaf node into three shorter ones. https://www.cs.ox.ac.uk/ralf.hinze/publications/Brother12.pdf https://www.cs.ox.ac.uk/ralf.hinze/publications/Brother12.pd...