Red-black BST'

Question 1

What is a RB tree?

Answer 1

Encoding of BST by adding extra information to create 3-nodes.

Question 2

What are the red and black links and what are their properties?

Answer 2

• 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.

Question 3

What is left and right rotation?

Answer 3

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

Question 4

How do we insert into a single 2-node?

Answer 4

Insert into key and perform rotation if necessary.

Question 5

How do we insert into a 2-node at the bottom?

Answer 5

• If parent is 2-node, do the same as with 2-node insertion
• Parent will become a 3-node.

Question 6

What are the 3 cases for insertion into a 3-node?

Answer 6

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

Question 7

How do we insert a 3-node at the bottom of the tree?

Answer 7

Same cases arise as above.

Question 8

What is the height of a red black BST?

Answer 8

No more than 2lg N