Trees

Question 1

What is (worst case) time complexity for input into Binary Search Tree in sorted descending order?

Answer 1

O(n)

Question 2

What is (worst case) time complexity for input into Binary Search Tree in sorted ascending order?

Answer 2

O(n)

Question 3

What is used to resolve time complexity for Binary Search Trees in cases where insertions happen to be made in some sorted order

Answer 3

AVL Trees which introduce height balancing

Question 4

What is height rebalancing?

Answer 4

The difference of. the Left and Right subtrees will generate a Balance Factor

Question 5

What is Balance Factor?

Answer 5

Balance Factor is an integer to represent how much the difference between the left and right subtree’s height. This value is restricted to ensure one sub tree’s height does not exceed the other’s by too large of a factor.

For an AVL tree the Balance Factor is set to stay within -1, 0 ,1 to be considered BALANCED

Question 6

How many types of AVL Rotations?

Answer 6

Left rotation: single rotation
Right rotation: single rotation
Left-Right rotation:double rotation
Right-Left rotation: double rotation

Question 7

Properties of Red-Black Trees

RB invariants are more complicated than the AVL balance property; however they can be implemented to provide somewhat faster operations on the tree

R-B Invariant ensures tree is always balanced

• if red nodes removed then you have a balanced tree
• every internal node has at least 2 children, and all leaves are at the same level
• adding back the red nodes increases path length by at most a constant factor

Insert, delete, and find functions are O(log n) worst-case. Height can never be more than 2 (log_2 N) +1

Answer 7

Insert, and delete operations are easy to implement by constant factor in aVL trees. The average level of a node in a random red-black tree is close to random AVL tree (log_2 N), so find() functions are as fast in average case

KEY: Red-Black Tree implement insert and delete such that it ensures invariants are invariants.

Insert only needs to go down once and never need to traverse back up to check balance. This is more efficient, iterative implementation than how AVL inserts (needing to traverse twice once down and again up)

Red-Black insertion uses single and double aVL rotations, plus “color-change” operations, to ensure the red-black properties are invariant

Question 8

Insertion Protocol for Red-Black Tree

A new node is inserted as a leaf with usual binary search tree insert algorithm. It will be black if inserting root. Otherwise, it will be red.

But this poses a problem as child of a red node cannot be red, this operations must take place to change subtree before inserting new red node

Changes are made going down the tree assuming inserting a red node as leaf (before insertion), once all the rotations and changes are set, then red node is inserted as final step.

Answer 8

Consider what happens if insertion (not root) is a black node. What violations occur? (number of black nodes from root to leaf)

Any fixe are done with just an AVL rotation which holds BST ordering property

Anticipate all the possible situations to insert into.