Wk 4 Binary Search Trees and Balanced Trees (Red-Black)

Question 1

What is the expected fast search algorithm?

Answer 1

lg n

Question 2

What is the main difference between a heap and a BST?

Answer 2

heap had no relationship between siblings. Also heap was full, whereas BST could be not full

Question 3

Why doesn’t a sorted linear array work for a BST?

Answer 3

We would have to go through the entire thing (n) each time we did an add or a drop. Would be too costly. Instead we use pointers, etc.

Question 4

What are the max and min of a BST?

Answer 4

The max is the right-most right child. The min is the left-most left child.

Question 5

Is a linked list a BST?

Answer 5

Yes, albeit it an ugly one with each node having degree of one.

Question 6

How many ways can a BST be created from a particular input?

Answer 6

LOTS.

Question 7

When do we call a BST balanced?

Answer 7

The difference between the longest and shortest paths is a constant.

Question 8

What is the algorithm for IN-ORDER WALK? What is its complexity? Why? What is its output?

Answer 8

if not at nil,
INORDERWALK(L)
Print key (this)
INORDERWALK(R)

Each node is visited exactly 3 times.

O(n) assuming the tree is already built. It’s output is the sorted list of keys.

Question 9

What changes in a pre/post order walk compared to a inorder walk?

Answer 9

only the ordering of the print

Question 10

What is the complexity of search in a BST? Why?

Answer 10

O(h) where h is the height of the tree. If the tree is balanced, the height should be lg n. Worst case you have to go all the way to the bottom at the leaves.

Question 11

How does search of a BST relate to insert?

Answer 11

For an insert, I’m essentially searching for a place to insert the value, so its the same algorithm with a write at the end. (if this were already in here, where would it be?)

Question 12

How would I use a BST to sort random input?

Answer 12

Run an insert at each node. Then at end, do an in-order walk. This would be lg h to add each node for n nodes. plus one in-order walk which would be linear as well. Overall n lg n if balanced, could be as bad as O(n^2) if the tree is a linked list with each node degree of one.

Question 13

What is analogy of D/S as a spring or having potential energy?

Answer 13

Energy you spend putting things into it, minimizes energy spent taking things out. By spending some energy and putting some in by organizing and/or balancing, it becomes easier to get out later. If you spend no energy organizing and just dump everything in it will take more energy to get out later. Overall, the total energy (of information !?) is net.

Question 14

What is the successor of a node in a BST?

Answer 14

For a non-leaf, the successor is the min of the right child.

For a leaf, it is move up and find the first right turn.

Question 15

What is complexity of finding a successor? Why?

Answer 15

lg (h) Could have to do one entire walk of the tree from root to leaf or vice versa.

Question 16

What is algorithm for delete node of BST?

Answer 16

1) Leaf is trivial…. cut it off.
2) Non-Leaf with 1 kid…. put kid in node’s place and remove node.
3) Non-Leaf with 2 kids….Find successor. Put successor’s parent in touch with successor’s kid and move successor to node’s place.

Question 17

Why is keeping a binary tree’s height as small as possible desirable?

Answer 17

Because in several algorithms we may have to walk the height of it (they are O(h)). When we can keep the height at lg n as we work, we will be guaranteed the max performance of any algorithm that depends on the tree height as we go

Question 18

What is the definition of a Red-Black BST? What makes it different from a standard BST

Answer 18

Same as a BST, but we keep the color, red or black at each node. See other question for 4 properties.

Question 19

What is the best analogy for the color in the nodes of a RBT?

Answer 19

The are balance sensors that trip or pop when that branch is getting too big. They point out when a balance is required.

Question 20

What are the 4 properties of Red-Black Trees that we continually maintain?

Answer 20

1. Root is black
2. Leaves are black
3. No Red Parent - Red Child connections
4. All black-heights are the same (black height equals the number of black nodes encountered in a walk from the root to the leave)

Question 21

What is the rotation algorithm, and what is its complexity? Why?

Answer 21

For a right rotate, we move left child up one and make previous parent its right child. We make previous left child’s right child become the previous node’s left child. At most we are moving 10 pointers according to the notes. No matter the size of n, so its Theta(1).

Question 22

Prove that if we can prove a tree has it’s red-black properties, then we prove it is balance BST. IOW what is the height of a RBT w/ n keys?

Answer 22

The height is = h’/2

Question 23

Why do we add NIL’s as children of all the nodes of a RBT?

Answer 23

?

Question 24

What is the algorithm for RB Insert? What is the complexity? Why?

Answer 24

Run insert to put the node in where it belongs and color it red. Then check which properties are violated. (either red-red parent child, or red at root) Red at root, means just color it black.

Three cases for red-red violation….

CASE 1:
If z’s uncle is red, swap z’s parent and z’s uncle to become black, and the grandparent to be red. set z to the grandparent which is now red and run again with new z.

CASE 2:
If z’s uncle is black, first check what child z is. If it’s a right child, rotate to put us in case 3 with z switching to the now-left-child. Fall through to case 3

CASE 3:
z’s uncle is black, and z is a left child. Perform a rotate from z’s parent with z’s parent as the pivot. Recolor the pivot/z’s parent to be black, recolor z’s new sibling to red. Done.

The complexity is 2 lg (n) = O (lg n).

You spend lg n to run top to bottom of the tree one time for insert. When you adjust the tree and fix it up, you push a red-red violation up 2 spots each time which in the worst case could continually go all the way to the root.