223 BST and RBTrees

Question 1

if removing a node with more than one child in a BST what do I do?

Answer 1

find the left most item in the right sub-tree of the node

Question 2

how many nodes in a full binary tree

Answer 2

2^h -1

Question 3

balance factor

Answer 3

left height - right height

Question 4

General case for single rotation right

Answer 4

Node * k1 = k2 - > left ;
k2 - > left = k1 - > right ;
k1 - > right = k2 ;
return k1 ;

Question 5

General case for single rotation left

Answer 5

Node * k1 = k2 - > right ;
k2 - > right = k1 - > let ;
k1 - > left = k2 ;
return k1 ;

Question 6

when to do a double rotate in AVL

Answer 6

inserting into left childs right subtree, o right childs left subtree

Question 7

double rotate with left child

Answer 7

{
root- > left = single_rotate_left ( root- > left );
return single_rotate_right ( root);

Question 8

Double rotate with right child

Answer 8

{
root- > right = single_rotate_right ( root- > right );
return single_rotate_left ( root);

Question 9

basic insertion algorithm for AVL

Answer 9

1. Recursively traverse path for insertion
2. Insert node
3. During backtracking, update heights and determine balance factors
4. Rebalance (rotate) if node’s balance factor less than −1 or greater than 1

Question 10

AVL tree insert time

Answer 10

O(log n)

Question 11

valid red black tree constraints

Answer 11

The root is always Black

3. “NULL” nodes are Black
4. If a node is Red, it’s children cannot be Red
5. All paths from a node to a NULL child has the same number of Black nodes

Question 12

Inserting Nodes (Overview)

Answer 12

Always assign inserted nodes the color Red
• If assigned Black, could make path with too many Black nodes
2. If the parent of the inserted node is Black, we are done!
• Inserting into the root is a special case … just color it Black
3. If the parent is Red, we violate the Red-Black properties
• Have to “rebalance” using tree rotations and apply color changes