红黑树

tree

Posted by Jow on July 1, 2019

目录

  1. 红黑树的性质
  2. 旋转
  3. 插入
  4. 删除

当自己清醒的时候,自己非常清楚自己的目标和梦想,但是也就是在自己清醒的时候,但是自己现在的状态一直是沉浸在自责之中,也许自己应该好好的思考一下和指定计划,自己究竟应该怎么去学习和生活。 每天总结一下,睡觉之前总结自己学习到的和明天需要学习的,强调自己每天的任务,并一直朝着这个目标进行努力。

红黑树的性质

红黑树是二叉搜索树,但是它是相较于二叉搜索树而言比较平衡的二叉树。

  1. 每个节点的颜色是红色或者黑色的
  2. 根节点是黑色的
  3. 如果一个节点是红色的,那个它的两个子节点是黑色的
  4. 对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。这个黑个个数称之为黑高。
  5. 每个叶子结(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


删除

删除的时候注意记录那个位置的节点被删除了,颜色是什么,如果删除节点拥有两个子节点,那么删除的节点的位置就是,后继节点,注意后继节点和颜色继承删除节点的颜色。

然后判断改变节点的颜色是否是黑色,如果是就要进行位置校正。

  1. x的兄弟节点w是红色

改变w和x的父节点颜色,然后w左旋

  1. x的兄弟节点w是黑色,而且w的两个孩子节点都是黑色

d变成红色

  1. x的兄弟节点w是黑色,w左是红色,右是黑色

交换w和其左孩子颜色,w右旋,到了4情况

  1. x的兄弟w是黑色,w的右孩子是红色。

x.p进行一次左旋

AVL树

AVL树是一种高度平衡的二叉搜索树,对于每个节点x,x的节点的左子树和右子树的高度至多为1,要维护AVL树,需要一个给节点添加一个新的属性h,表示这棵子树的高度。当插入或者删除之后,二叉树不在平衡,可以通过旋转来维持树的平衡。