0. Binary tree的小坑

  • full binary tree :除了树叶以外,每个节点都有两个小孩。
  • complete binary tree :各层节点全满,除了最后一层,最后一层节点全部靠左。
  • perfect binary tree :各层节点全满。同时也是 full binary tree 和 complete binary tree 。

bin_tree

1. AVL tree

高度:空节点为 –1,单节点为 0
平衡因子:左子树高度 - 右子树高度
约束:
单旋转:LL(旋转左子树至根),RR
双旋转:LR(R旋转左儿子右子树至左儿子,L旋转左儿子至根),RL
复杂度:
$$
H = O(logN) \
T(N) = O(H) = O(logN)
$$

2. Splay Tree

伸展树(Splay Tree)
伸展:
被访问的节点为 X

  1. X 父节点为树根,单旋转
  2. X 有父节点与祖父节点
  3. 若 X 为 ZigZag 型,双旋转
  4. 若 X 为 ZigZig 型,一字型旋转
  5. 递归向上进行至根
    删除:
    访问待删除元素,得到左右子树,访问左子树最大元素(一路向右)使其到
    达根,将右子树作为左子树右儿子。

3. B+ Tree

秩:M
【Definition】A B+ tree of order M is a tree with the following structural properties:
(1) The root is either a leaf or has between 2 and M children.
(2) All nonleaf nodes (except the root) have between ⌈M / 2⌉ and M children.
(3) All leaves are at the same depth.
Assume each nonroot leaf also has between ⌈M / 2⌉,

性质:

  1. 所有数据存储在叶节点上

  2. 中间节点有 M 个指向叶节点的指针,及 M - 1 个叶节点中最小值在其中间。
    插入:不满足时递归向上分裂
    删除:节点过少时与兄弟合并,递归向上检查

4. Red Black Tree

(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NIL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

insert:

insert

4. Leftist Heap

【Definition】The null path length, Npl(X), of any node X is the length of the shortest path from X to a node without two children. Define Npl(NULL) = –1.

Npl(X)= min { Npl(C)+ 1 for all C as children of X }

【Definition】The leftist heap property is that for every node X in the heap, the null path length of the left child is at least as large as that of the right child.

Skew Heap: Simple version of leftist heap

Always swap the left and right children except that the largest of all the nodes on the right
paths does not have its children swapped. No Npl.