java面试-彻底搞懂红黑树
红黑树性质 1、每个结点或是红色的，或是黑色的2、根节点是黑色的3、每个叶结点（NIL）是黑色的4、如果一个节点是红色的，则它的两个儿子都是黑色的。5、对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。 和AVL树的比较 AVL树是一棵严格的平衡树，它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在XXX，因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。 红黑树用非严格的平衡来降低插入删除时旋转的次数。 因此，如果你的业务中查找远远多于插入、删除，那选AVL树；如果查找、插入、删除频率差不多，那么选择红黑树。 插入过程 默认插入的结点为红色。为何？因为红黑树中黑节点至少是红节点的两倍，因此插入节点的父节点为黑色的概率较大，而此时并不需要作任何调整，因此效率较高。 1. 父为黑 插入后无需任何操作。由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后无需任何调整，这就是红黑树比AVL树插入效率高的原因！ 2. 父为红 父为红的情况破坏了红黑树的性质，此时需要根据叔叔的颜色来做不同的处理。 叔叔为红此时很简单，只需交换爸爸、叔叔和爷爷的颜色即可。此时若爷爷节点和太爷爷节点颜色相同，再以爷爷节点为起始节点，进行刚才相同的操作，即：根据爷爷的兄弟颜色做相应的操作。 叔叔为黑此时较为复杂，分如下四种情况：a）爸爸在左、叔叔在右、我在左以爸爸为根节点，进行一次R旋转。b）爸爸在左、叔叔在右、我在右先以我为根节点，进行一次L旋转；再以我为根节点，进行一次R旋转。c）叔叔在左、爸爸在右、我在左先以我为根节点，进行一次R旋转；再以我为根节点，进行一次L旋转。d）叔叔在左、爸爸在右、我在右以爸爸为根节点，进行一次L旋转。 删除过程 二叉搜索树的删除 若删除二叉搜索树的节点A，实际上删除的是二叉搜索树中序遍历的前驱节点，注意：1. 这个被删除节点要么就是一个叶子节点，2. 要么有且仅有一个左孩子然后将孩子顶替它原来的位置，最后将被删的节点值覆盖待删除的那个节点A。 红黑树按照二叉搜索树的方式删除节点，之后再进行相应的旋转操作，使得删除后的树仍然是一棵红黑树。 定义 待删除节点：要删除的那个节点 实际删除节点：待删除节点的中序遍历前驱 红黑树实际删除节点的性质 实际删除节点要么是叶子节点，要么有且仅有一个左孩子； 若为叶子节点，必为红色； 若实际删除节点还有孩子，则该必为左孩子；a）若左孩子为红色，则实际删除节点必为黑色；b）若左孩子为黑色，则实际删除节点红黑均可以。 约定 蓝色箭头：表示判定点 在删除操作开始前，蓝色箭头首先指向实际删除节点。 『实际删除节点』在图中以『父』表示。 旋转过程开始： 1. 父为红色（待删节点为叶子） 直接删除父节点即可： 2. 父为黑 子为红（待删节点为黑、待删节点子节点为红+左孩子） 用子节点覆盖父节点，并保持父节点的颜色： 3. 父为黑 子为黑（待删节点和子节点均为黑） 3.1. 叔叔为红 PS：叔叔为红，则爷爷必为黑！ 父在左 叔在右a）子节点覆盖父节点b）进行一次左旋 父在右 叔在左a）子节点覆盖父节点b）进行一次右旋 3.2. 叔叔为黑 PS：叔叔、爸爸都为黑，那爷爷颜色就不确定了！ 祖父红 两个侄子黑以下两种情况操作一致：1.子覆盖父（删除）2.交换祖父和叔叔的颜色。 a）父在左 叔在右b）父在右 叔在左同上。 祖父黑 两个侄子黑以下两种情况操作一致：1. 祖父染成子节点的颜色；2. 子节点染成黑色；3. 叔叔染成红色a）父在左 叔在右b）父在右 叔在左 祖父颜色随意 至少有一个红侄a）红侄为左左（叔左、红侄左）1. 红侄进行一次右旋2. 红侄染成黑色3. 交换叔叔和祖父的颜色b）红侄为左右（叔左、红侄右）1. 红侄进行一次右旋+左旋2. 红侄染成父节点颜色；3. 父节点染成黑色c）红侄为右左（叔右、红侄左）1. 红侄进行一次右旋+左旋2. 红侄染成父节点颜色；3. 父节点染成黑色；d）红侄为右右（叔右、红侄右）1. 红侄进行一次左旋2. 叔叔染成父节点颜色；3. 红侄染成黑色；
