Menu
I am studying red-black trees and I am reading the Cormen's "Introduction to Algorithms" book. Now I am trying to create red-black tree with numbers 1-10 by using the pseudo-code described in the book - RB-INSERT-FIXUP(T, z). Here is the screenshot
Everything was fine until I inserted number "6" into the tree. According to pseudo-code I get the following result
As you can see all red-black tree requirements met, but I am confused because I know that red-black tree should be balanced on each step.
I can manually perform "left-rotate" procedure with "2" and "4" and change the colours. In that case I will get the following result, which is balanced appropriately
So my question is:
Is that all right to have unbalanced tree?, or I missed something during insertion nodes?
272
In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
I think rb tree can become unbalanced up to 2 log n in depth. you should check this. a perfectly balanced tree is roughly log n in depth. unbalanced-ness in rb tree is not bad enough to screw up it's big O for various operations.
A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors are used to ensure that the tree remains balanced during insertions and deletions.
A balanced binary tree will follow the following conditions: The absolute difference of heights of left and right subtrees at any node is less than 1. For each node, its left subtree is a balanced binary tree. For each node, its right subtree is a balanced binary tree.
This is fine. Red-black trees are balanced, but not necessarily perfectly. To be precise, properties of red-black tree guarantee that the longest path to the leaf (implicit, not shown in your picture) is at most twice as long as the shortest. Shortest one has length 2 (2 -> 1 -> leaf), longest one has length 4 (2 -> 4 -> 5 -> 6 -> leaf), so the invariant does hold.
101
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
