Red-black BST'
暂无描述。系统推荐的高质量记忆内容，适合每天坚持背诵学习。
卡片预览 (9 张)
What is a RB tree?
Encoding of BST by adding extra information to create 3-nodes.
What are the red and black links and what are their properties?
• Red links bind two 2-nodes to represent 3-nodes • Black links bind together 2-3 trees Red links lean left and no node can have two connected. The tree has perfect black balance.
What is left and right rotation?
Used to correct right-leaning links or links in a row. * If right leaning, use left rotation to return link to a node that is the root of a RD BST for the same set of keys whose left link is red (Switching from smaller at root to larger at root. Becomes left child of right child.) * Right rotation: Becomes right child of left child
How do we insert into a single 2-node?
Insert into key and perform rotation if necessary.
How do we insert into a 2-node at the bottom?
• If parent is 2-node, do the same as with 2-node insertion • Parent will become a 3-node.
What are the 3 cases for insertion into a 3-node?
If inserting key is larger: * Atttach to right * Make balance with middle key at root * Flip colours from red to black If key smaller: * Goes on left * Reduce to previous case by rotating top link to the right If key between: * Right leaning below a left leaning * Reduce to previous by rotating right link to left
How do we insert a 3-node at the bottom of the tree?
Same cases arise as above.
What is the height of a red black BST?
No more than 2lg N