Red Black Trees

• Red-Black Tree, which is a self-balancing Binary Search Tree, resulting in a worst-case O(log n) time complexity, that is able to insert and remove elements by doing just a single pass through the tree, unlike an AVL Tree, which requires two passes through the tree.
• AVL Trees are actually more balanced than Red-Black Trees
• four properties of RBT:
  1. All nodes must be "colored" either red or black
  2. The root of the tree must be black
  3. If a node is red, all of its children must be black (i.e., we can’t have a red node with a red child)
  4. For any given node u, every possible path from u to a "null reference" (i.e., an empty left or right child) must contain the same number of black nodes
• exercise break: CORRECT STATEMENTS
  1. Red-Black Trees and AVL Trees have the same average-case find, insert, and remove Big-O time complexities
  2. The height of a Red-Black Tree can be larger than the height of an AVL Tree with the same elements
  3. Red-Black Trees and AVL Trees have the same worst-case find, insert, and remove Big-O time complexities
  4. The height of a Red-Black Tree is at most twice the height of an AVL Tree with the same elements
  5. Some, but not all, Red-Black Trees are AVL Trees
• Insertion: our default color for newly-inserted nodes is always red. The motivation behind this is that, if we were to automatically color a newly-inserted node black, we would probably break the "same number of black nodes along paths to null references" restriction (Property 4)
  1. If this new node is the first one in the tree (i.e., it is the root), simply recolor it black.
  2. Otherwise, during your traversal down the tree in the Binary Search Tree insertion algorithm, if you ever run into a black node with two red children, recolor all three nodes
  3. the newly-inserted red node became the child of a red node? It turns out that we can fairly simply fix this problem using AVL rotations and recoloring.
  4. in the case of a kink, we need to perform a double rotation.