红黑树
发布于
简单介绍
定义
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:
- 性质1:每个节点要么是黑色,要么是红色。
- 性质2:根节点是黑色。
- 性质3:每个叶子节点是黑色。
- 性质4:每个红色结点的两个子结点一定都是黑色。
- 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
自平衡
左旋
以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变
这个图 就非常的形象的表示了左旋的结果,其实我们理解左旋可以分为以下两点
- 旋转节点的右子节点变为它的父节点,左子节点不变,新的右子节点是原来右子节点的左子节点
- 旋转节点的右子节点 左子节点为 旋转节点;右子节点不变
套用到上图就是
- pivot是旋转节点,y变为pivot的父节点,左节点还是a,右节点变为b
- y的左节点是pivot,右节点不变,还是c
右旋
以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变
同左旋刚好相反,左和右的互换,两个点
- 旋转节点的左子节点变为它的父节点,右子节点不变,新的左子节点是原来左子节点的右子节点
- 旋转节点的左子节点 左子节点不变;右子节点为旋转节点
变色
结点的颜色由红变黑或由黑变红
插入
空树
当树是空的时候,插入的时候,直接将其作为根节点,并且是黑色的
插入的key已经存在了
- 当前节点的颜色不变
- 更改当前节点的值
插入节点的父节点为黑色节点
由于插入的节点颜色是红色的,所以直接插入即可,无需自平衡
插入节点的父节点为红色节点
- 叔叔节点存在并且为红色节点
- 叔叔节点为空,且祖父节点、父节点和新节点处于一条斜线上。
- 叔叔节点为空,且祖父节点、父节点和新节点不处于一条斜线上。
第一种情况
将父节点和叔叔节点与祖父节点的颜色互换
第二种情况
将B节点进行右旋操作,并且和父节点A互换颜色
第三种情况
将C节点进行左旋,这样就从第三种情况转换成第二种情况了,然后针对case 2进行操作处理就行
删除
参考文章: