Menu
I have a basic understanding of both red black trees and 2-3-4 trees and how they maintain the height balance to make sure that the worst case operations are O(n logn).
But, I am not able to understand this text from Wikipedia
2-3-4 trees are an isometry of red-black trees, meaning that they are equivalent data structures. In other words, for every 2-3-4 tree, there exists at least one red-black tree with data elements in the same order. Moreover, insertion and deletion operations on 2-3-4 trees that cause node expansions, splits and merges are equivalent to the color-flipping and rotations in red-black trees.
I don't see how the operations are equivalent. Is this quote on Wikipedia accurate? How can one see that the operations are equivalent?
295
Two empty trees are isomorphic. For example, following two trees are isomorphic with following sub-trees flipped: 2 and 3, NULL and 6, 7 and 8. Try It! We simultaneously traverse both trees. Let the current internal nodes of two trees being traversed be n1 and n2 respectively.
Tree Isomorphism Problem. Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
An equivalent data structure of 2-3-4 trees is called a Red-Black tree. Being the binary search tree, Red Black trees are much easier to implement. In the next section, we discuss the mapping of a 2-3-4 tree to a red-black tree. A 2-node in a 2-3-4 tree becomes a black node in a red-black tree.
A 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that can be used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three, or four child nodes:
rb-tree(red-black-tree) is not isomorphic to 2-3-4-tree. Because the 3-node in 2-3-4-tree can be lean left or right if we try to map this 3-node to a rb-tree. But llrb-tree(Left-leaning red-black tree) does.
Words from Robert Sedgewick(In Introduction section):
In particular, the paper describes a way to maintain
a correspondence between red-black trees and 2-3-4 trees,
by interpreting red links as internal links in 3-nodes and
4-nodes. Since red links can lean either way in 3-nodes
(and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1
Also Page29 and Page30 of presentation from Robert Sedgewick. This a presentation about LLRB tree.
And "Analogy to B-trees of order 4" section of "Red-black Tree" in the wikipedia, it contains a good graph.
133
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
