black-red-tree-simple


title: black_red_tree_simple
date: 2020-04-10 17:38:15

tags:算法;红黑树

红黑树的初解

红黑树的性质:

​ 性质1:每个节点要么是黑色,要么是红色。

​ 性质2:根节点是黑色。

​ 性质3:每个叶子节点(NIL)是黑色。

​ 性质4:每个红色结点的两个子结点一定都是黑色。

​ 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

根据性质5可以推出:

​ 性质5.1:任意一个节点有一个黑色子节点,那么该节点会存在两个子节点

红黑树插入时一些操作

​ 插入时,节点的颜色是红色,因为不能存在相邻的两个红色节点;

​ 插入进去后需要重新调整树的平衡,一般调整树的平衡操作有:

​ 1.染色

​ 2.左旋转

​ 3.右旋转

旋转的示例图

​ 1 : 左旋转

​ 对节点P进行左旋:进行如下操作:

​ P的右节点代替P的位置,P作为右节点的左节点,P的右节点的左节点作为P的右节点,P的左节点不变(左旋只 操作右侧节点)

​ 操作图解:

​ 手写图解:

​ 网图图解:

​ 2 : 右旋转

​ 对节点P进行右旋:进行如下操作:

​ P的左节点F顶替P的位置,F的右节点为P,P的左节点为F原右节点,P原右节点不变(右旋只旋转左侧节点)

​ 操作图解:

​ 手写图解:

​ 网图图解:

删除节点后的一些操作

删除了节点之后找到右侧节点(如果存在)的最左节点顶替当前节点位置,如果不存在则把左节点顶替当前位置后进行平衡维护

打赏

扫一扫,分享到微信

微信分享二维码

请我喝杯咖啡吧~

支付宝
微信