red-black tree
- bh(x) <= 2lg(n+1)
- insert
- 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
- 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
- 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
- select a basic data structure
- additional info to be added to the structure
- maintain the info in the structure
- new operation
- range tree x.low x.high x.max traversal-search
- red-black tree, x.low as key of node
- x.max is max of x.high of all nodes under that node
- x.max = max(x.high, x.left.max, x.right.max)
- traversal-search