有序表

1. 接口

有序表可以理解为一种接口，它为用户提供一种key-value查询的服务，特点是:

key是有序组织的，且提供API
所有操作的复杂度是O(logN)

有序表其底层真正实现的是红黑树，AVL树，SB树和跳表。它提供的API如下:

1)void put(K key, V value):
将一个(key，value)记录加入到表中，或者将key的记录 更新成value。

2)V get(K key):
根据给定的key，查询value并返回。

3)void remove(K key):
移除key的记录。

4)boolean containsKey(K key):
询问是否有关于key的记录。

5)K firstKey():
返回所有键值的排序结果中，最左(最小)的那个。

6)K lastKey():
返回所有键值的排序结果中，最右(最大)的那个。

7)K floorKey(K key):
如果表中存入过key，返回key;否则返回所有键值的排序结果中, key的前一个。

8)K ceilingKey(K key):
如果表中存入过key，返回key;否则返回所有键值的排序结果中, key的后一个。

2. 二叉搜索树

搜索二叉树的增删改查，基本和红黑树，AVL树，SB树一致，只不过它们有各自的额外常数时间的调整和修改，用来去平衡树。

2.1 查

比节点大小，决定滑的方向

2.2 改

找到节点后，即可修改

2.3 增

一直滑动到空，挂在最近的非空节点上

2.4 删

具体分四种情况:

1) 无左无右: 可直接删除
2) 有左无右: 找到替代，再删除
3) 无左有右：和2类似
4) 有右有左: 找到替代，右树上的最左节点，或者左树上的最右节点

3. AVL树

具体可以参考网友资料1,2

3.1 平衡检测

对于一棵树来说，它的高度(height)定义如下：

从根节点(root)开始到某一个叶子节点(leaf)的最长路径(path)上结点的个数

根据AVL树的定义，我们可以为所有的结点定义一个平衡因子(balanced factor)：

某个结点的平衡因子等于该节点的左孩子的高度减去右孩子的高度

根据平衡树的定义，计算得到的平衡因为会出现两种情况：

如果平衡因子是0, 1, -1 这三个数的话，可以认定该节点是符合平衡树的定义的；
否则，该结点不平衡，需要重新平衡；

对于一个BST来说，每次插入的元素只可能放在叶子结点上。所以只能影响某个子树是否平衡，对其他子树不会有任何的影响。在这种情况下，我们只需要根据搜索的路径，从孩子往祖先找，如果有不平衡的结点就可以被找到。如果一直到根结点都没有发现不平衡结点，则可以认为这次的插入操作没有造成树的不平衡。

public Node insert(int element) {
    Node newNode = super.insert(element);
    // 在rebalance函数中，从当前节点开始逐级向父节点上层遍历
    rebalance((AVLNode)newNode);
    return newNode;
}

3.2 重平衡

如果发现了某个不平衡的结点，那么就需要对该结点进行重平衡。实现重平衡的方法，是对该节点的子树进行旋转(rotation)。
在真实的情况下，我们会遇到四种可能出现的情况，都可以通过一次或者两次的旋转，来使得不平衡的结点变平衡。其中，LL,RR 可以通过一次旋转(singly rotation)重新平衡，LR, RL可以通过两次旋转(doubly rotation)重新平衡。

private void rebalance(AVLNode node) {
    while (node != null) {
        // 从当前节点开始，逐级向父节点上层遍历
        Node parent = node.parent;
        // 黑盒，判断错误类型并修复
        node = (AVLNode)parent;
    }
}

private void rebalance(AVLNode node) {
    while (node != null) {

        Node parent = node.parent;

        // 黑盒，判断错误类型并修复
        // 所有的父节点，检查哪种失误类型, 并修复
        int leftHeight = (node.left == null) ? -1 : ((AVLNode) node.left).height;
        int rightHeight = (node.right == null) ? -1 : ((AVLNode) node.right).height;
        int nodeBalance = rightHeight - leftHeight;
        // rebalance (-2 means left subtree outgrow, 2 means right subtree)
        // RR 型或者 RL 型
        if (nodeBalance == 2) {
            if (node.right.right != null) {
                node = (AVLNode)avlRotateLeft(node);
                break;
            } else {
                node = (AVLNode)doubleRotateRightLeft(node);
                break;
            }
        // LL 型或者 LR 型
        } else if (nodeBalance == -2) {
            if (node.left.left != null) {
                node = (AVLNode)avlRotateRight(node);
                break;
            } else {
                node = (AVLNode)doubleRotateLeftRight(node);
                break;
            }
        } else {
            updateHeight(node);
        }

        node = (AVLNode)parent;
    }
}

双旋转是由基本的左旋和右旋组成，在这里简单的介绍下右旋:

旋转节点node向右侧沉，node.left=temp向右侧上，成为新的"头节点"
temp节点的right继承给node.left
修改改变节点的父节点
确定temp节点是以前node节点父节点的哪个孩子？

protected Node rotateRight(Node node) {
    // node的left会成为新的头节点
    Node temp = node.left;
    // 把node的父节点给temp的父节点，temp接替node成为新的头
    temp.parent = node.parent;

    // node的左承接temp的右
    node.left = temp.right;
    // 若不为空，也要修改node.left的父节点
    if (node.left != null) {
        node.left.parent = node;
    }

    // node成为temp的右孩子
    temp.right = node;
    // node的父节点也要改变
    node.parent = temp;

    // temp took over node's place so now its parent should point to temp
    // temp是指向node父节点的左还是右？
    if (temp.parent != null) {
        if (node == temp.parent.left) {
            temp.parent.left = temp;
        } else {
            temp.parent.right = temp;
        }
    } else {
        root = temp;
    }
    return temp;
}

4. 红黑树

红黑树可以参考资料1, 2

4.1 对比红黑树和AVL树

参考资料1
1.AVL平衡树与红黑树的区别

AVL平衡树是为了解决二叉查找树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

2.使用场景
频繁的查询: AVL树，windows对进程地址空间的管理用到了AVL树
频繁的增删: 红黑树，Java的TreeMap实现；广泛用在C++的STL中。map和set都是用红黑树实现的。

3.红黑树各种操作的时间复杂度是多少？

RBT 的操作代价分析：
(1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。

(2) 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。

(3) 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。

RBT 效率总结 : 查找效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

4.红黑树有哪些性质？
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。