目录
- 红黑树的性质
- 旋转
- 插入
- 删除
当自己清醒的时候，自己非常清楚自己的目标和梦想，但是也就是在自己清醒的时候，但是自己现在的状态一直是沉浸在自责之中，也许自己应该好好的思考一下和指定计划，自己究竟应该怎么去学习和生活。 每天总结一下，睡觉之前总结自己学习到的和明天需要学习的，强调自己每天的任务，并一直朝着这个目标进行努力。
红黑树的性质
红黑树是二叉搜索树，但是它是相较于二叉搜索树而言比较平衡的二叉树。
- 每个节点的颜色是红色或者黑色的
- 根节点是黑色的
- 如果一个节点是红色的，那个它的两个子节点是黑色的
- 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。这个黑个个数称之为黑高。
- 每个叶子结(nil)是黑色的
为了方便处理红色树的临界点，红黑树存在一个哨兵节点，表示nil，所有指向nil
旋转
对红黑树进行操作的时候，插入删除，为了维护红黑树的性质，一般对树进行旋转改变颜色的操作，旋转分为左旋和右旋。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
local function treeLeftRotate(tree, x)
local y = x.right
x.right = y.left
if y.left then
y.left.parent = x
end
y.parent = x.parent
if x.parent == nil then
tree.root = y
elseif x == x.parent.left then
x.parent.left = y
else
x.parent.right = y
end
y.left = x
x.parent = y
end
local function treeRightRotate(tree, x)
local y = x.parent
y.left = x.right
x.right.parent = y
if y.parent == nil then
tree.root = x
elseif y.parent.left == y then
y.parent.left = x
else
y.parent.right = x
end
x.right = y
y.parent = x
end
插入
在插入的过程中，向二叉搜索树，那样进行插入，并将初始节点染成红色，然后对树进行校正。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
local function fixTree(t, z)
while z.parent.color == 2 do
if z.p == z.parent.parent.left then
local y = z.parent.parent.left
if y.color == 2 then
z.parent.color = 1
y.color = 1
z.parent.parent.color = 2
z = z.parent.parent
elseif z == z.parent.right then
z = z.parent
treeLeftRotate(t, z)
end
z.parent.color = 1
z.parent.parent.color = 2
treeRightRotate(t, z.parent.parent)
else
-- same like up then right and left exchanged
end
end
t.root.color = 1
end
local function insertTree(tree, v)
local node = tree.root
local y = nil
if node == nil then
tree.root = v
return
end
while node do
y = node
if v.key > node.key then
node = node.right
else
node = node.left
end
end
v.parent = y
if y.parent == nil then
tree.root = v
elseif v.key < y.key then
y.left = v
else
y.right = v
end
v.color = 2
fixTree(tree, v)
end
删除
删除的时候注意记录那个位置的节点被删除了，颜色是什么，如果删除节点拥有两个子节点，那么删除的节点的位置就是，后继节点，注意后继节点和颜色继承删除节点的颜色。
然后判断改变节点的颜色是否是黑色，如果是就要进行位置校正。
- x的兄弟节点w是红色
改变w和x的父节点颜色，然后w左旋
- x的兄弟节点w是黑色，而且w的两个孩子节点都是黑色
d变成红色
- x的兄弟节点w是黑色，w左是红色，右是黑色
交换w和其左孩子颜色，w右旋，到了4情况
- x的兄弟w是黑色，w的右孩子是红色。
x.p进行一次左旋
AVL树
AVL树是一种高度平衡的二叉搜索树，对于每个节点x，x的节点的左子树和右子树的高度至多为1，要维护AVL树，需要一个给节点添加一个新的属性h，表示这棵子树的高度。当插入或者删除之后，二叉树不在平衡，可以通过旋转来维持树的平衡。
