数据结构-Tree小结

Posted on

树的基本操作

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
class TreeNode(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class OperationTree(object):

    def query(self, root, data):
        if root is None:
            return None
        if root.value == data:
            return root
        elif root.left:
            return self.query(root.left, data)
        elif root.right:
            return self.query(root.right, data)

    def pre_order(self, root):
        if root is None:
            return None
        print(root.value, end=" ")
        self.pre_order(root.left)
        self.pre_order(root.right)

    def in_order(self, root):
        if root is None:
            return None
        self.in_order(root.left)
        print(root.value, end=" ")
        self.in_order(root.right)

    def back_order(self, root):
        if root is None:
            return None
        self.back_order(root.left)
        self.back_order(root.right)
        print(root.value, end=" ")

二叉查找树(BST)

二叉查找树，Binary Search Tree，或者称为二叉搜索树。

性质：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(logn)

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
class TreeNode(object):

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree(object):

    def __init__(self, root):
        self.root = root

    def depth(self, root):
        if root is None:
            return None
        else:
            return 1 + max(self.depth(root.left), self.depth(root.right))

    def insert(self, root, value):

        if root is None:
            root = TreeNode(value)
        elif root.value > value:
            root.left = self.insert(root.left, value)
        elif root.value < value:
            root.right = self.insert(root.right, value)
        return root

    def search1(self, root, value):
        if root is None:
            return None
        if root.value == value:
            return root
        elif root.value < value:
            return self.search1(root.right, value)
        elif root.value > value:
            return self.search1(root.left, value)

    def search2(self, root, value):
        while root is not None and root.value != value:
            if root.value > value:
                root = root.left
            elif root.value < value:
                root = root.right
        return root

    def max_value1(self, root):
        if root is None:
            return None

        if root.right is None:
            return root.value
        else:
            return self.max_value1(root.right)

    def max_value2(self, root):
        if root is None:
            return None

        while root.right is not None:
            root = root.right
        return root.value

    def min_value1(self, root):
        if root is None:
            return None

        if root.left is None:
            return root.value
        else:
            return self.min_value1(root.left)

    def min_value2(self, root):
        if root is None:
            return None

        while root.left is not None:
            root = root.left
        return root.value


if __name__ == '__main__':
    a = TreeNode(15)
    b = TreeNode(6)
    c = TreeNode(18)
    d = TreeNode(4)
    e = TreeNode(8)
    f = TreeNode(17)
    g = TreeNode(20)
    h = TreeNode(13)
    i = TreeNode(9)
    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.left = f
    c.right = g
    e.right = h
    h.left = i
    bst = BinarySearchTree(a)
    print(bst.search1(a, 13).value)
    print(bst.search2(a, 13))
    print(bst.insert(a, 23))
    print(bst.max_value1(a))
    print(bst.max_value2(a))
    print(bst.min_value1(a))
    print(bst.min_value2(a))

平衡二叉树(AVL)：旋转耗时

在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树本质上还是一棵二叉搜索树，它的特点是：

  1. 本身首先是一棵二叉搜索树。
  2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

旋转

  • 单向右旋平衡处理LL：由于在a的左子树根结点的左子树上插入结点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
  • 单向左旋平衡处理RR：由于在a的右子树根结点的右子树上插入结点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
  • 双向旋转（先左后右）平衡处理LR：由于在a的左子树根结点的右子树上插入结点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
  • 双向旋转（先右后左）平衡处理RL：由于在a的右子树根结点的左子树上插入结点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

avatar

查找、插入和删除在平均和最坏情况下的时间复杂度都是O ( log ⁡ n ) {\displaystyle O(\log {n})}O(logn).

由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此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
class TreeNode(object):

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1


class AVLTree(object):

    def get_height(self, root):
        if root is None:
            return 0

        return root.height

    def get_balance(self, root):

        if root is None:
            return 0

        return self.get_height(root.left) - self.get_height(root.right)

    def right_rotate(self, root):

        new_root = root.left
        new_right = new_root.right

        new_root.right = root
        root.left = new_right

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        new_root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        return new_root

    def left_rotate(self, root):

        new_root = root.right
        new_left = new_root.left

        new_root.left = root
        root.right = new_left

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        new_root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        return new_root

    def insert(self, root, value):

        if root is None:
            root = TreeNode(value)

        if root.value < value:
            root.right = self.insert(root.right, value)
        elif root.value > value:
            root.left = self.insert(root.left, value)

        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        balance = self.get_balance(root)

        if balance > 1 and value < root.left.value:
            return self.right_rotate(root)

        if balance < -1 and value > root.right.value:
            return self.left_rotate(root)

        if balance > 1 and value > root.left.value:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        if balance < -1 and value < root.right.value:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

2-3-4树

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构，可以保证在O(lgn)的时间内完成查找、插入和删除操作。它主要满足以下性质：

（1）每个节点每个节点有1、2或3个key，分别称为2（孩子）节点，3（孩子）节点，4（孩子）节点。

（2）所有叶子节点到根节点的长度一致（也就是说叶子节点都在同一层）。

（3）每个节点的key从左到右保持了从小到大的顺序，两个key之间的子树中所有的

key一定大于它的父节点的左key，小于父节点的右key。

红黑树：树太高

2-3-4树和红黑树是完全等价的，由于绝大多数编程语言直接实现2-3-4树会非常繁琐，所以一般是通过实现红黑树来实现替代2-3-4树，而红黑树本也同样保证在O(lgn)的时间内完成查找、插入和删除操作。

红黑树是每个节点都带有颜色属性的平衡二叉查找树 ，颜色为红色或黑色。除了二叉查找树一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

  • 节点是要么红色或要么是黑色。
  • 根一定是黑色节点。
  • 每个叶子结点都带有两个空的黑色结点（称之为NIL节点，它又被称为黑哨兵）。
  • 每个红色节点的两个子节点都是黑色（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点）。
  • 从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点。

这些性质保证了根节点到任意叶子节点的路径长度，最多相差一半（因为路径上的黑色节点相等，差别只是不能相邻的红色节点个数），所以红黑树是一个基本平衡的二叉搜索树，它没有AVL树那么绝对平衡，但是同样的关键字组成的红黑树相比AVL旋转操作要少，而且删除操作也比AVL树效率更高，实际应用效果也比AVL树更出众。当然红黑树的具体实现也复杂的多。

avatar

B树

一个m阶的B树具有如下几个特征：B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。

  1. 根结点至少有两个子女。
  2. 每个中间节点都包含k-1个元素和k个孩子，其中 ceil（m/2） ≤ k ≤ m
  3. 每一个叶子节点都包含k-1个元素，其中 ceil（m/2） ≤ k ≤ m
  4. 所有的叶子结点都位于同一层。
  5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
  6. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）。其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。
    Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。
    n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

查询

avatar

以上图为例：若查询的数值为５：

第一次磁盘IO：在内存中定位（与17、35比较），比17小，左子树；
第二次磁盘IO：在内存中定位（与８、12比较），比８小，左子树；
第三次磁盘IO：在内存中定位（与3、5比较），找到5，终止。

整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

插入

对高度为ｋ的m阶B树，新结点一般是插在叶子层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论：

  1. 若该结点中关键码个数小于m-1，则直接插入即可。
  2. 若该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点(ｋ-1层)中

重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层。

B+树

B+树是对B树的一种变形，与B树的差异在于：

一个m阶的B+树具有如下几个特征：

  1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
  2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

avatar

插入

B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。

删除

B+树中的关键码在叶结点层删除后，其在上层的复本可以保留，作为一个”分解关键码”存在，如果因为删除而造成结点中关键码数小于ceil(m/2)，其处理过程与B-树的处理一样。在此，我就不多做介绍了。

B+树相比B树的优势：

  1. 单一节点存储更多的元素，使得查询的IO次数更少；
  2. 所有查询都要查找到叶子节点，查询性能稳定；
  3. 所有叶子节点形成有序链表，便于范围查询。

参考文章

  1. https://www.cnblogs.com/lliuye/p/9118591.html
  2. https://blog.csdn.net/qq_34364995/article/details/80787193
  3. https://www.jb51.net/article/166572.htm
  4. https://blog.csdn.net/rosefun96/article/details/108686365?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242
  5. https://blog.csdn.net/dongcai1905/article/details/101890478
  6. https://blog.csdn.net/u010853261/article/details/78217823
  7. https://blog.csdn.net/liangjiubujiu/article/details/84023736