1.二叉查找(排序)树BST

（1）什么是BST？

        二叉查找树满足：
  • 左子树上所有结点的值均小于或等于它的根结点的值。
  • 右子树上所有结点的值均大于或等于它的根结点的值。
  • 左、右子树也分别为二叉排序树。
        总结来说左小右大。
        

（2）BST的优缺点

  • 优点：
    比如我们要找节点10，算上根节点，一共找4次就能找到。也就是说，使用BST查找一个元素的最大查找次数等于树的高度。插入新节点也是如此，通过一层一层查找找到合适位置。
  • 缺点：
    在数据递增或递减时，BST会不平衡，导致查找的性能退化成线性的。比如下面这样一棵BST，"左子树"成了线性链表了。

2.红黑树

        为了解决二叉排序树可能退化成线性链表的问题，引入了红黑树。

（1）什么是红黑树？

        红黑树是一种自平衡的二叉排序树。它具有一下特点：
  • 根节点是黑色，其他节点是红色或黑色；
  • 每个叶子节点都是黑色的空节点（称为NIL节点）；
  • 每个红色节点的两个子节点都是黑色，也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点；
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

（2）红黑树调整策略

        当插入(新插入节点都是红色的)或删除节点后，可能打破红黑树的规则，因此需要对红黑树进行调整，有以下两种调整策略：
  • 变色：将红色节点变为黑色，或者把黑色节点变为红色，使该树重新符合红黑树的要求。
  • 旋转：
    • 左旋转：左旋转使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
    • 右旋转：右旋转使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

（3）★★如何向红黑树中插入一个新节点？

        首先根据二叉排序树的性质找到插入位置，因为新插入的节点是红色的，所以如果父节点也是红色(大前提)时需要进行调整。有三种情况：
  • case1：叔叔节点也是红色，将父节点和叔叔节点的颜色与爷爷结点的颜色互换。
  • case2：没有叔叔且新节点、父节点和爷爷节点在一条斜线上，进行旋转，都是左节点就右旋，都是右节点就左旋，最后变色。

  • case3：没有叔叔且新、父、爷不在一条斜线上，两次旋转，第一次旋转成case2，再按case2旋转一次，然后变色即可。

        调整完后向上回溯继续调整其他节点，直到符合红黑树的定义为止。

（4）二叉排序树的删除

        删除二叉排序树的一个节点分为三种情况：
        
  • 待删节点没有子节点，如节点1，直接删除即可。
  • 待删节点有一个子节点，如节点2，将这个子节点(1)替代待删节点即可。
  • 待删节点有两个子节点，如节点4，将待删节点与它中序遍历的后续节点(5)互换，然后删除此时新位置上的待删节点即可。

（5）★红黑树的删除

        删除红黑树首先按照删除二叉排序树的三种情况：
  • 首先是待删节点X没有子节点的情况，待删节点可能是黑色也可能是红色：
    • 如果是红色的话，X的父节点一定是黑色且X没有兄弟，此时直接删除X就结束了；
    • 如果X是黑色的话，那么X一定有兄弟，如果兄弟是黑色，那么兄弟就没有孩子，此时删除X，需要把黑兄弟变红；
    • 如果兄弟是红色，那么兄弟就有俩黑色孩子，此时删除X需要旋转和变色（如最后一张图）。
  • 其次是待删节点X只有一个子节点，由红黑树的性质，只有一个子节点的节点，一定是父(X)黑子红的情况，此时删除X需要用子节点替代X的位置，并变为黑色：

  • 最后是最麻烦一种，也就是待删节点X有两个子节点，这两个子节点分为两红、两黑、一红一黑的3种情况：
    • 两红：删除X后需要用后继与X交换再删除现在的X，然后
    • 两黑：
    • 一红一黑：

（6）红黑树的应用

        TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。

（7）二叉排序树(RST)、平衡二叉树(AVL)和红黑树(RBT)的比较？

        二叉排序树在一般情况下，查找的时间复杂度是O(logn)，但是如果节点是递增或者递减的话，就退化成线性链表了，时间复杂度就成了O(n)，这属于二叉排序树的一大缺点。
        平衡二叉树在二叉排序树的基础上，还要求左右子树高度差不能超过1，这样就能保证不会退化成线性链表了，但是它的问题是在插入和删除时，由于要保证严格的平衡，所以需要频繁旋转。
        红黑树将节点分成红色和黑色两种，还要求了5个性质，它的平衡性比平衡二叉树弱一点，只要求满足红黑树的5条性质即可，不用严格保证高度差不超过1，因此查询时间上会比AVL慢一点。但是在插入和删除时，红黑树可以通过变色来代替旋转，这比平衡二叉树速度又快了一点儿。
        综上所述，如果对于完全随机的数据，就能保证二叉排序树不退化，普通的二叉排序树就很好用；如果对于查询操作较多的情况，AVL比红黑树更胜一筹；但是综合考量的话，还是红黑树更好用，应用场景最广泛。