Week 6

Question 1

Red Black Tree Rules - type of BST

Answer 1

1. Root is always black
2. Each node is colored black or red
3. A null node is colored black –> every new node must be inserted red
4. every red node has two black noeds
5. every path from ANY node to ANY of its descendant null node must have the same number of black nodes

Question 2

VAL vs red-black trees

Answer 2

red-black trees are less-perfectly balanced. However, they generally need fewer rotations during insertion/deletion, which makes red-black tree superior for growing or shrinking a tree, but less efficient for searching.

Both O(log n) time complexity

AVL might have greater height and use more memory than Red Black Trees

Question 3

VAL self-balancing BST

Answer 3

Uses balance factor (absolut delta between height of left and right subtree).
Balanced if this delta is smaller equal to one for every node.

Question 4

How to rebalance AVL

Answer 4

Start from the lowest unbalanced tree.
Label the three nodes, starting from the unbalanced one.
Rearrange.
Check balance factor of ancestor

Question 5

Condition that must be fulfilled such that tree operations are log n

Answer 5

Tree must be balanced