red-black tree

- bh(x) <= 2lg(n+1)

- insert

1. case 1: z and z.p are red. z.uncle's color is red -> set colors of z.p and z.uncle to black. set z.p.p to red. make z.p.p as new z
2. case 2: z and z.p are red. z.uncle's color is black. z is right child of z.p -> left rotate z and z.p to case 3. z and z.p exchanged
3. case 3: z and z.p are red. z.uncle's color is black. z is left child of z.p -> right rotate z.p and z.p.p. set z.p to black. set z.p.p to red

- deletion

z, y, x, w

https://blog.****.net/xiaojun111111/article/details/51898486

- extension

• dynamic sequential statistics. 

        add one more meta data, size, to tree node. the size is number of internal nodes under the given node. 

        node.left.size +1 is the ordered location of that node if it's in-order traversal.

• how to extend a data structure

1. select a basic data structure
2. additional info to be added to the structure
3. maintain the info in the structure
4. new operation

• range tree      x.low x.high    x.max traversal-search

1. red-black tree, x.low as key of node
2. x.max is max of x.high of all nodes under that node
3. x.max = max(x.high, x.left.max, x.right.max)
4. traversal-search

•