通用算法-平衡二叉树

发表于 | 分类于 ， | 阅读次数：

一、平衡树

  • 为什么提出平衡树：普通二叉树在遍历的过程中需要遍历所有节点才能找到对应的数据，这里根据希望根据数据的数值大小，定向的找到数据的存储位置。
  • 所以希望平衡树能有以下性质：
    • 对于任意节点，其左边的所有点的数值都一定小于其右边所有节点的数值
    • 对于节点的两个分支的深度之差不大于1

根据以上需求提出一种平衡树生成算法，该算法只能在以下情况下使用：

  • 没有重复数值
  • 只能从空节点逐渐插入数值。（无法从普通二叉树直接转为平衡树）

使用一个简单的动图表示算法效果：

GIF

二、原理说明

2.1 旋转

如上动图，在对二叉树的操作中，可以拆分为两个动作，左旋和右旋

2.1.1 左旋

口诀：左旋提右，右接左

解释如下图所示，对数字83进行左旋操作，先把右儿子90提上来当爸爸，再把83的右儿子连接到90的左儿子85。

GIF

所以总共动了3根线：

  • 85——90
  • 83——90
  • 68——90

所以在进行旋转的时候，需要记录旋转节点83，对应儿子90，以及父节点68。

代码如下（T为旋转点）：

1
2
3
4
5
6
7
8
9
10
11
12
13
if parent.rChild == T：    # 记录是父节点的左节点还是右节点
    A = True
else:
    A = False

R = T.rChild
T.rChild = R.lChild
R.lChild = T

if A:
    parent.rChild = R
else:
    parent.lChild = R
2.1.2 右旋

口诀：右旋提左，左接右

解释如下图所示，对数字50进行右旋操作，先把左儿子40提上来，再把50的左儿子连接到40的右儿子45。

GIF

所以总共动了3根线：

  • 45——40
  • 50——40
  • 68——40

所以在进行旋转的时候，需要记录旋转节点50，对应儿子40，以及父节点68。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
if parent.rChild == T：    # 记录是父节点的左节点还是右节点
    A = True
else:
    A = False

L = T.lChild
T.lChild = L.rChild
L.rChild = T

if A:
    parent.rChild = L
else:
    parent.lChild = L

（其实就是和左旋是对称结构，其实可以写成一个函数，但是为了直观，写成两个）

2.2 旋转组合

什么时候需要旋转？

这里需要提出平衡因子这个参数，平衡因子的值只有-1,0,1，平衡因子是根据该节点的右子树的深度减去左子树的深度计算得到。如果不为这3个数值，就会进行旋转操作，达到平衡。

在实际插入数值过程中，会存在两种情况：

  • 旋转一次
    • 左旋
    • 右旋
  • 旋转两次
    • 左旋，后右旋
    • 右旋，后左旋
2.2.1 旋转一次

什么时候旋转一次呢？

找到一个平衡因子不在三个数字之内的节点，假设为2。而插入的数值在起儿子右边，如下图：

1575537174232

在图中：0的平衡因子为2，1的平衡因子为1，2是插入数值，其平衡因子为0。此时，对其进行一次左旋转即可以达到平衡，如下图：

1575537285414

进行右旋的是其相反情况，不再解释。

2.2.2 旋转两次

什么时候旋转两次呢？

找到一个平衡因子不在三个数字之内的节点，假设为2。而插入的数值在其儿子左边，如下图：

1575537434297

在图中：0的平衡因子为2，1的平衡因子为1，2是插入数值，其平衡因子为0。但是此时无法对0进行左旋，所以需要对1先进行右旋，再对0进行左旋。

1575537546321

右旋

1575537637079

左旋

另外一种情况是其相反情况，不再解释。

三、代码实现

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
# -*- coding: utf-8 -*-
# @Time    : 2019/12/3 15:29
# @Author  : zwenc
# @File    : adfad.py

class Node(object):
    # 每个Node都有4个数据
    def __init__(self, data, rChild=None, lChild=None):
        self.data = data  # 储存的数据
        self.rChild = rChild  # 右节点
        self.lChild = lChild  # 左节点
        self.height = 1  # 树的高度


def updata(T):
    """
    更新节点深度
    :param T:  节点
    :return: None
    """
    if T == None:
        return False

    if T.rChild != None:
        A = T.rChild.height
    else:
        A = 0

    if T.lChild != None:
        B = T.lChild.height
    else:
        B = 0

    T.height = max(A, B) + 1


def rotateFactor(T):
    """
    计算平衡因子
    :param T:  节点
    :return:  平衡因子
    """
    if T.rChild != None:
        A = T.rChild.height
    else:
        A = 0

    if T.lChild != None:
        B = T.lChild.height
    else:
        B = 0

    return A - B


def lrotate(T):
    """
    左旋转
    :param T: 节点T
    :return: 旋转后的头结点
    """
    R = T.rChild
    T.rChild = R.lChild
    R.lChild = T

    updata(R.lChild)   # 更新深度
    updata(R)

    return R


def rrotate(T):
    """
    右旋转
    :param T: 节点T
    :return: 旋转后的头结点
    """
    L = T.lChild
    T.lChild = L.rChild
    L.rChild = T

    updata(L.rChild)
    updata(L)

    return L


def check(T, parent):
    """
    旋转，更新节点的高度
    :param T:  树节点
    :return: None
    """
    if T == None:  # 判断非空，虽然在本程序中不会出现这种情况，但是出于工程礼仪。。
        return False

    updata(T)  # 更新节点深度

    factor = rotateFactor(T)
    if T == parent.lChild:  # 记录T的在父节点的位置（左还是右）
        A = True
    else:
        A = False

    if factor > 1:  # 右边树高
        rfactor = rotateFactor(T.rChild)
        if rfactor > 0:
            ret = lrotate(T)        # 一次旋转情况
        else:
            ret = rrotate(T.rChild) # 二次旋转情况
            T.rChild = ret
            ret = lrotate(T)

    elif factor < -1:  # 左边树高
        lfactor = rotateFactor(T.lChild)

        if lfactor < 0:
            ret = rrotate(T)
        else:
            ret = lrotate(T.lChild)
            T.lChild = ret
            ret = rrotate(T)
    else:
        return True

    if A:
        parent.lChild = ret
    else:
        parent.rChild = ret


def insertNode(T, data, parent):
    """
    插入节点
    :param T: 当前节点
    :param data: 数据
    :param parent: 当前节点的父节点
    :return: bool
    """
    if T == None:
        if parent.data == None:             # 注意，链表头节点无数据
            parent.rChild = Node(data)
            return False

        if (data > parent.data):            # 添加新的节点
            parent.rChild = Node(data)
        else:
            parent.lChild = Node(data)
        return False

    if data > T.data:
        insertNode(T.rChild, data, T)
    elif data < T.data:
        insertNode(T.lChild, data, T)
    else:
        return True                        # 找到了一样的数据，则返回True

    check(T, parent)                       # 判断是否平衡，如果不平衡，则进行选择操作
    return False


def insert(root, data):
    """
    :param root: 根节点，无数据
    :param data: 数据
    :return: None
    """
    insertNode(root.rChild, data, root)    # 需要时刻记录旋转节点的相对父节点root
    updata(root)


#  测试，需要在debug下查看数据
if __name__ == "__main__":
    root = Node(None)  # 根节点，里面只会保存树的高度，没有数据

    insert(root, 20)
    insert(root, 5)
    insert(root, 4)
    insert(root, 30)
    insert(root, 50)
    insert(root, 25)
-------------本文结束感谢您的阅读-------------
0%