# DSA yong liu HW 3
## Exercise 7.4-5 in CLRS Textbook
## Problem 7-2 in CLRS Text book
## 11.2-1
For the i-th hashed key $k_i$, $E\{X_i\}$ is the expectation value, of the number of times $k_i$ being collided by those key, $j$'s, hashed afterward.
$$ E\{X_i\} = \sum_{j > i} 1 \Pr\{h(k_j)) = h(k_i)\} = \sum_{j > i} 1 / m = (n - i) / m $$
$$ \sum_{i = 1}^n E\{X_i\} = \sum_{i = 1}^n \frac{n - i}{m} = \frac{n^2 - n(n + 1) / 2}{m} = \frac{n^2 - n}{2m}.$$

## 12.2-9
- T is a BST.
- x has no childs.
- x.parent is y.
- x is y.Lchild, or, x is y.Rchild.
- We want to satisfy:
- y.key is the smallest key in T larger than x.key
- I.e., **y is x.successor**
- y.key is the largest key in T smaller than x.key
- I.e., **y is x.predecessor**

### soln
- x is y.Lchild
- try to fing x.successor
- try to go to the bottum right of x.Lsubtree.
x is a leaf.
Go up left.
It is y.
- Try to fing x.predecessor.
- Not y, but we have got we want.

- x is y.Rchild
- try to fing x.predecessor
- Try to go to the bottum right of x.Lsubtree.
x is a leaf.
Go up left.
It is y.
- Try to fing x.successor.
Not y, but we have got we want.