red black trees

Question 1

red black tree balance props

Answer 1

• every node has a color: red or blacj
• every leaf is black - root also black
• if a node is red both children are black
  every path from root to leaves contains the same number of black nodes

Question 2

analyse RB trees in terms of complexity, compare to AVL

Answer 2

• all operations are log n
  i similar to AVL but more color changes and maybe fewer rotations
  ++weaker balance conditions than avl
  ++same ad and disadvantages
  ++one bit for color storage vs an int for the height

Question 3

insert algorithm:

Answer 3

• traverse from root to find insertion point
• at each node:
  ++if node is black and both children are red - flip colours
  ++if nodes parent is also red:
  ++++if outside node - single rotation - recolour
  ++++ if inside node - double rotation - recolour
• after inserting current node as red - if parent also red : rotate double or single
• color root black

Question 4

delete procedure

Answer 4

• Deleted nodes have at most one child.
• 2 node deletion is actually replacement so colours are unchanged.

We want to delete a red node.  This will maintain black node path lengths.

Traverse tree from top to bottom.  Ensure that current node is red.  Otherwise, rotate and recolour, without violating conditions.