CS2040s: DG 3

Recap:
Each Node can be a parent node and always have 2 child node.

Normal BST:
If we insert and its not balancing, we will have to travel O(n) time.
This is an issue thus there exist an avl tree.
AVL tree will balance for us so searching is O(logn) time.

AVL Tree:
Imagine we are plucking it up when balancing and letting it go which makes it fall down.

Red Black Tree:
1. A node is either red or black
2. Roots and leaves are always black
3. If a node is red, the children is black
4. All paths from node to its NIL descendants contain the same number of black nodes.

Nodes requires one storage bit to keep track of color
The shortest path is all black nodes and longest path is alternating red and black.

Operation: All O(logn), Space is O(n)
Insert/Remove requires rotation

Insertion:
Everytime we insert, we need to rebalance and ensure that the properties are met.
1. Insert node and colour it red
Case 0 : Z=root
Just colour z black
Case 1: Z.uncle = red
Recolour parent grandparent and uncle
Case 2 : Z.uncle = black (Triangle)
B - A - Z is a triangle
rotate Z
case 3: Z.uncle = black (Line)
B - A - Z
         - D
rotate z.grandparent
recolour
2. Fix violation

Time complexity

Insert - logn
Color - 1
fix violation: logn
    recolo - 1
    rotation - 1

Problem 1. Ranking and SelectingIn the previous Discussion Group, we figured out a data structure for the contestants on planet
Kronos. In today’s DG, consider that all the contestants are stored in a Binary Search Tree (BST)
and not a heap. Your employers now want two other operations to be included:

• select(int i) which finds the i’th smallest element.• rank(contestant x) which returns the rank of element x, i.e., its index in the sorted list of
all the elements.


Problem 1.a. Discuss how you can augment the BST to efficiently perform select(int i) andrank(contestant x) queries.Hint: In AVL trees, we stored the balance factor at each node to help us rebalance the tree. What
information can you store at each node that can help you quickly determine a node’s rank? Can
the information also be useful to perform a select?

Problem 1.b. Give pseudocode for select(int i) and rank(contestant x) and state their
asymptotic time complexities.

rank:
Use size
Consider the case where we traverse right then left, then my next right node is larger than my child left

Select: