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