Implementation of Red-Black Trees in 2-3 Trees
Implementation of Red-Black Trees within the structure of 2-3 Trees involves representing 3-nodes using red links, maintaining specific restrictions on representation, ensuring perfect black balance, and establishing a correspondence between red-black BSTs and 2-3 trees. Observations include the color changes during node insertion and the black coloration of the root. An example is provided to illustrate the concepts discussed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Red-Black Implementation of 2-3 Trees
Represent 3-nodes using red links Red links indicate that the node comprises a 3-node with its parent. A field in the Node class indicates whether the parent link is red.
Restrictions on Representation (from Sedgewick) Red links lean left We only want to limit red links to left links When we make a right red link we will use rotation to make it a left red link. After the rotation the child remains red This requires swapping the colors of the parent and child involved in the rotation.
Restrictions on Representation (from Sedgewick) No node has two red links connected to it because that would amount to a 4-node Flipping colors is like pushing the middle key to the parent in a 2-3 tree. After flipping, the root will be red, unless it is the root to the whole tree, in which case it will be black.
Restrictions on Representation (from Sedgewick) The tree has perfect black balance The number of black links traversed to every leaf is the same.
Restrictions on Representation (from Sedgewick) There is a 1-1 correspondence between red-black BST s and 2-3 trees If we collapse the red links, we get a 2-3 tree.
Observations When we add a new node to a 2-3 tree, it always combines with an existing node, with the exception of when adding to a null tree. With the execption of the root, all inserted nodes will be red. After flipping colors, the root will be red, with the exception of the root for the whole tree. Since the tree root is always black, we can simply color it black after each insertion.
Example Example
