红黑树
2023-10-14 17:54:08 2 举报红黑树的一些基本操作
作者其他创作
大纲/内容
80
53
46
72
74
1
18
70
25
88
8
2
82
50
操作:父节点为黑插入无需进行操作
34
12
null
3
90
2、左左
11
变色
右旋
指的是父节点是祖父节点的左孩子还是右孩子，子节点是父节点的左孩子还是右孩子比如：左左，就是父节点为左孩子，该节点也为父节点的左孩子
红黑树性质
这样看很容易看出来符合前四个原则但是，只要把null节点都填上去就会发现，34节点右边只有三个黑节点，而其他的有四个黑节点
三个黑节点
76
叔节点和父节点都为红
左旋
10
以此为线
叔节点和父节点全部变为黑色，爷爷节点变为红色
81
红黑树的插入
92
64
插入
4、左右
12 15 25
先右旋再左旋
83
46 50
........
满足红黑树的性质 4 ：parent 为黑色节点。
红黑树等价变化
普通红黑树
先左旋再右旋
需要旋转的节点的右孩子的左孩子变为旋转节点的右孩子
86
2为轴
需要旋转的节点变为该左孩子的右节点
需要旋转的节点的左孩子的右孩子变为旋转节点的左孩子
当前插入节点11，它的父节点为红色，所以就违反了性质四
父亲节点为黑
57
红黑树的旋转（仅仅考虑旋转）
1、右右
规律：首先把需要旋转的节点的孩子节点和孙子节点形成一个平面，先观察此平面的上部分是往那边偏的，往那边偏就是往那边转，一次转不成功就旋转两次
15
3、右左
又出现了父红叔红的情况，继续进行上一步的操作
需要旋转的节点变为右孩子的左节点
34 53 80
性质1. 结点是红色或黑色。性质2. 根结点是黑色。性质3. 所有叶子都是黑色。（叶子是NIL结点）性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
叔节点为黑和父节点为红
不满足红黑树的性质 4 ：parent 为红色节点
4个黑节点
根节点为红
73
根节点变黑
70 74
收藏
收藏
0 条评论
下一页
