Just for Life.

明月更几时

0%

AVL树的Python实现

发表于 更新于
本文字数： 4.6k 阅读时长 ≈ 4 分钟

AVL是平衡树，平衡因子概念什么的就不阐述了，主要是在不平衡时候如何旋转。（1）右子树右节点插入：左旋转。（2）左子树左节点插入：右旋转。（3）右子树左节点插入：右旋转后左旋转。（4）左子树右节点插入：左旋转后右旋转。

  • 所谓的左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。
  • 如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。
  • 如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。

如果对本文有疑问或者想找男朋友，可以联系我，点击此处有我联系方式。

有关AVL树的具体旋转操作请看这里，讲的贼详细。

AVL树有左右孩子的概念，所以，在实现AVL树之前，有必要先引入Python中类的概念，先来个MWE。

Python的类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Car:
    # 初始化
    def __init__(self, brand, gas):
        self.brand = brand
        self.gas = gas
        print('一辆新的', self.brand, '被生产出来了！')
    # 定义方法
    def add_gas(self, amount):
        self.gas += amount
    # 定义方法
    def show_gas(self):
        print('剩余汽油：', self.gas)

# 实例化
benz = Car('Benz', 100)
# 调用方法
benz.add_gas(200)
benz.show_gas()

AVL树的实现

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
182
183
184
import numpy as np
import time


class TreeNode(object):
    # 定义每个节点的数据，左孩子右孩子，平衡因子
    def __init__(self):
        self.data = 0
        self.left = None
        self.right = None
        self.height = 0


class BTree(object):

    def __init__(self):
        self.root = None

    def __Max(self, h1, h2):
        if h1 > h2:
            return h1
        elif h1 <= h2:
            return h2

    # 左左情况，向右旋转
    def __LL(self, r):
        node = r.left
        r.left = node.right
        node.right = r
        r.height = self.__Max(self.getHeight(r.right), self.getHeight(r.left)) + 1
        node.height = self.__Max(self.getHeight(node.right), self.getHeight(node.left)) + 1
        return node

    # 右右，左旋
    def __RR(self, r):
        node = r.right
        r.right = node.left
        node.left = r
        r.height = self.__Max(self.getHeight(r.right), self.getHeight(r.left)) + 1
        node.height = self.__Max(self.getHeight(node.right), self.getHeight(node.left)) + 1
        return node

    # 左右，先左旋再右旋
    def __LR(self, r):
        r.left = self.__RR(r.left)
        return self.__LL(r)

    # 右左，先右旋再左旋
    def __RL(self, r):
        r.right = self.__LL(r.right)
        return self.__RR(r)

    # r是self.root
    def __insert(self, data, r):
        if r == None:
            node = TreeNode()
            node.data = data
            return node
        elif data == r.data:
            return r
        elif data < r.data:
            r.left = self.__insert(data, r.left)
            # 左高右低
            if self.getHeight(r.left) - self.getHeight(r.right) >= 2:
                if data < r.left.data:
                    r = self.__LL(r)
                else:
                    r = self.__LR(r)
        else:
            r.right = self.__insert(data, r.right)
            if self.getHeight(r.right) - self.getHeight(r.left) >= 2:
                if data > r.right.data:
                    r = self.__RR(r)
                else:
                    r = self.__RL(r)

        r.height = self.__Max(self.getHeight(r.left), self.getHeight(r.right)) + 1
        return r

    # 删除data节点
    def __delete(self, data, r):
        if r == None:
            return r

        elif r.data == data:
            # 如果只有右子树，直接将右子树赋值到此节点
            if r.left == None:
                return r.right
            # 如果只有左子树，直接将左子树赋值到此节点
            elif r.right == None:
                return r.left
            # 如果同时有左右子树
            else:
                # 左子树高度大于右子树
                if self.getHeight(r.left) > self.getHeight(r.right):
                    # 找到最右节点 返回节点值 并删除该节点
                    node = r.left
                    while(node.right != None):
                        node = node.right
                    r = self.__delete(node.data, r)
                    r.data = node.data
                    return r
                # 右子树高度大于左子树
                else:
                    node = r.right
                    while node.left != None:
                        node = node.left
                    r = self.__delete(node.data, r)
                    r.data = node.data
                    return r

        elif data < r.data:
            # 在左子树中删除
            r.left = self.__delete(data, r.left)
            # 右子树高度与左子树高度相差超过1
            if self.getHeight(r.right) - self.getHeight(r.left) >= 2:
                if self.getHeight(r.right.left) > self.getHeight(r.right.right):
                    r = self.__RL(r)
                else:
                    r = self.__RR(r)

        elif data > r.data:
            # 右子树中删除
            r.right = self.__delete(data, r.right)
            # 左子树与右子树高度相差超过1
            if self.getHeight(r.left)-self.getHeight(r.right) >= 2:
                if self.getHeight(r.left.right)>self.getHeight(r.left.left):
                    r = self.__LR(r)
                else:
                    r = self.__LL(r)
        # 更新高度
        r.height = self.__Max(self.getHeight(r.left), self.getHeight(r.right))+1
        return r

    # 先序遍历
    def __show(self, root):
        if root != None:
            # print (root.data)
            self.__show(root.left)
            self.__show(root.right)
        else:
            return 0

    def Insert(self, data):
        self.root = self.__insert(data, self.root)
        return self.root

    def Delete(self, data):
        self.root = self.__delete(data, self.root)

    # 求结点的高度
    def getHeight(self, node):
        if node == None:
            return -1
        # print node
        return node.height

    def Show(self):
        self.__show(self.root)


if __name__ == '__main__':
    bi = BTree()
    insert_time = []
    delete_time = []
    for right_interval in range(1000, 500000, 50000):
        array = np.random.randint(1, 100, right_interval)
        since = time.time()
        for i in array:
            bi.Insert(i)
        end = time.time() - since
        insert_time.append(end)
        print('AVL insert : ' + str(right_interval) + ' Data: ' + str(end) + 's')

    for right_interval in range(1000, 500000, 50000):
        array = np.random.randint(1, 100, right_interval)
        since = time.time()
        for i in array:
            bi.Delete(i)
        end = time.time() - since
        delete_time.append(end)
        print('AVL delete : ' + str(right_interval) + ' Data: ' + str(end) + 's')
        for i in array:
            bi.Insert(i)

结果展示

Have a look about the result of insertion and delete operation to AVL。
Insertion:

Delete:

Statistic:

本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章