二叉搜索树（BST）的Python实现

本文将会介绍数据结构中的二叉搜索树（BST）的Python实现。

引言

在文章二叉树的Python实现中，笔者介绍了数据结构中的二叉树的Python实现及其可视化。本文在在此基础上，介绍二叉搜索树及其相关的操作、用途和缺点。

二叉搜索树（Binary Search Tree，简称为BST）是指一颗空树或者具有下列性质的二叉树：

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

二叉搜索树的发明者为P.F.Windley, A.D.Booth, A.J.T. Colin, and T.N.Hibbard，它是一种特殊的二叉树，其优势在于查找、插入的时间复杂度较低，为O(log n)，其空间复杂度为O(n)。

从上面的定义中，我们可以看到二叉搜索树中不存在两个数值相等的节点，因此，本文中的二叉搜索树均假设不存在数值相等的节点。

下面将介绍二叉搜索树的相关操作，包括构建（插入）、查找和删除等操作。

BST相关操作

在介绍二叉搜索树之前，我们先引入二叉树类，并在该类中实现二叉树的前序、中序、后序、层序遍历，并利用GraphViz模块来自己实现二叉树的可视化。

二叉树

二叉树类的实现代码如下：

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
# -*- coding: utf-8 -*-
# @file: binary_tree.py
from graphviz import Digraph
import uuid
from random import sample


# 二叉树类
class BTree(object):
    # 初始化
    def __init__(self, data=None, left=None, right=None):
        self.data = data    # 数据域
        self.left = left    # 左子树
        self.right = right  # 右子树
        self.dot = Digraph(comment='Binary Tree')

    # 前序遍历，实现思路：递归
    def pre_order(self):
        if self.data is not None:
            print(self.data, end=' ')
        if self.left is not None:
            self.left.pre_order()
        if self.right is not None:
            self.right.pre_order()

    # 中序遍历，实现思路：递归
    def in_order(self):
        if self.left is not None:
            self.left.in_order()
        if self.data is not None:
            print(self.data, end=' ')
        if self.right is not None:
            self.right.in_order()

    # 后序遍历，实现思路：递归
    def post_order(self):
        if self.left is not None:
            self.left.post_order()
        if self.right is not None:
            self.right.post_order()
        if self.data is not None:
            print(self.data, end=' ')

    # 层次遍历, 实现思路：利用队列
    def level_order(self):
        if self.data is None:
            return []
        queue = [self]
        res = []
        while queue:
            tmp = []
            for i in range(len(queue)):
                node = queue.pop(0)
                tmp.append(node.data)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res

    # 利用Graphviz进行二叉树的可视化
    def print_tree(self, save_path='./Binary_Tree.gv', label=False):

        # colors for labels of nodes
        colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red']

        # 绘制以某个节点为根节点的二叉树
        def print_node(node, node_tag):
            # 节点颜色
            color = sample(colors,1)[0]
            if node.left is not None:
                left_tag = str(uuid.uuid1())            # 左节点的数据
                self.dot.node(left_tag, str(node.left.data), style='filled', color=color)    # 左节点
                label_string = 'L' if label else ''    # 是否在连接线上写上标签，表明为左子树
                self.dot.edge(node_tag, left_tag, label=label_string)   # 左节点与其父节点的连线
                print_node(node.left, left_tag)

            if node.right is not None:
                right_tag = str(uuid.uuid1())
                self.dot.node(right_tag, str(node.right.data), style='filled', color=color)
                label_string = 'R' if label else ''  # 是否在连接线上写上标签，表明为右子树
                self.dot.edge(node_tag, right_tag, label=label_string)
                print_node(node.right, right_tag)

        # 如果树非空
        if self.data is not None:
            root_tag = str(uuid.uuid1())                # 根节点标签
            self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors,1)[0])     # 创建根节点
            print_node(self, root_tag)

        self.dot.render(save_path)      # 保存文件为指定文件

对其进行简单测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from binary_tree import BTree

# 构建二叉树
node1 = BTree(4)
node2 = BTree(5)
node3 = BTree(6)
node3.left = node1
node3.right = node2
node4 = BTree(7)
node5 = BTree(3)
node4.left = node5
node4.right = node3
# 遍历及可视化
node4.pre_order()   # 前序遍历
print()
node4.in_order()    # 中序遍历
print()
node4.post_order()  # 后序遍历
print()
print(node4.level_order())  # 层次遍历
node4.print_tree('./test_tree.gv', True)  # 可视化二叉树

构建的二叉树如下图：

测试二叉树

其前序、中序、后续、层序的输出结果如下：

1
2
3
4
7 3 6 4 5 
3 7 4 6 5 
3 4 5 6 7 
[[7], [3, 6], [4, 5]]

构建BST

有了上述的二叉树，我们可以继承这个类，来构建一颗二叉搜索树。我们利用插入操作来构建二叉搜索树。

对一颗二叉搜索树（可以为空）进行新节点插入操作：

  • 如果其根节点为空，则将根节点置为新节点
  • 若根节点数值小于新节点数值，如果右子树为空，则直接将新节点置为根节点的右子树，如果右子树不为空，则对右子树进行新节点插入操作即可，从而进入递归流程
  • 若根节点数值大于新节点数值，插入操作类似上述第二种情况

二叉搜索树的插入新节点的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from binary_tree import BTree


# Binary Search Tree Class inherits from BTree
class BST(BTree):

    def __init__(self, data=None, left=None, right=None):
        super(BST, self).__init__(data, left, right)

    # A utility function to insert a new node with the given key
    def insert(self, root, node):
        if root is None:
            root = node
        else:
            if root.data < node.data:
                if root.right is None:
                    root.right = node
                else:
                    self.insert(root.right, node)
            else:
                if root.left is None:
                    root.left = node
                else:
                    self.insert(root.left, node)

如果我们从空节点开始，对其进行一系列新节点的插入，这样我们就能构建一颗二叉搜索树了。

简单的测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 构建BST
test_root = BST(50)
test_root.insert(test_root, BTree(32))
test_root.insert(test_root, BTree(30))
test_root.insert(test_root, BTree(20))
test_root.insert(test_root, BTree(40))
test_root.insert(test_root, BTree(70))
test_root.insert(test_root, BTree(60))
test_root.insert(test_root, BTree(80))
test_root.insert(test_root, BTree(10))
test_root.insert(test_root, BTree(90))

test_root.print_tree('./BST.gv', True)
print('中序遍历为：')
test_root.inorder()
print()

构建的二叉搜索树如下图：

测试二叉搜索树

其中序遍历结果如下：

1
2
中序遍历为：
10 20 30 32 40 50 60 70 80 90

查找操作

利用递归操作即可实现节点查找。我们在之前的类中实现这些方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# check if the new data is in BST
def isInBST(self, root, new_data):
    if root is None:
        return False
    else:
        if root.data == new_data:
            return True
        elif root.data < new_data:
            return self.isInBST(root.right, new_data)
        else:
            return self.isInBST(root.left, new_data)

# search for new data, return a BST whose root is new data
def search(self, root, new_data):
    inflag = self.isInBST(root, new_data)
    if not inflag:
        print("%s is not in BST." % new_data)
    else:
        if root.data == new_data:
            return root
        elif root.data < new_data:
            return self.search(root.right, new_data)
        else:
            return self.search(root.left, new_data)

我们对刚才构建的二叉搜索树查找数值为60的节点：

1
2
search_node = test_root.search(test_root, 60)
print(search_node.data, search_node.left, search_node.right)

输出结果为：

1
60 None None

因为数值为60的节点是叶子结点，因此并没有左、右子树。

删除操作

二叉搜索树中的节点删除操作较为麻烦，首先我们先要确保需要删除的节点在树的节点中。删除操作如下：

  • 如果删除节点的数值小于根节点，则在左子树中删除该节点
  • 如果删除节点的数值大于根节点，则在右子树中删除该节点
  • 如果删除节点等于根节点，则分以下三种情况进行讨论：
  1. 只有左子树或者只有右子树，则直接将根节点置为它的左子树或右子树
  2. 如果都没有左子树和右子树，则根节点置为None
  3. 如果左、右子树都存在，则需要找到右子树中的最小值节点，将根节点的数值赋值为该最小值节点的数值，最终将此时的根节点的右子树置为右子树删除最小值节点后的数，即进入递归操作。

在之前的类中实现节点删除操作。

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
# find the node which has the minimum value
    def findMinNode(self, root):
        if root is None:
            return None
        elif root.left is None:
            return root
        else:
            return self.findMinNode(root.left)

    # A utility function to delete a node with given data
    def delNode(self, root, val):
        # 删除二叉搜索树中值为val的点
        if root is None:
            return
        if val < root.data:
            root.left = self.delNode(root.left, val)
        elif val > root.data:
            root.right = self.delNode(root.right, val)
        # 当val == root.val时，分为三种情况：只有左子树或者只有右子树、有左右子树、即无左子树又无右子树
        else:
            if root.left and root.right:
                # 既有左子树又有右子树，则需找到右子树中最小值节点
                temp = self.findMinNode(root.right)
                root.data = temp.data
                # 再把右子树中最小值节点删除
                root.right = self.delNode(root.right, temp.data)
            elif root.right is None and root.left is None:
                # 左右子树都为空
                root = None
            elif root.right is None:
                # 只有左子树
                root = root.left
            elif root.left is None:
                # 只有右子树
                root = root.right
        return root

我们在刚才构建的二叉搜索树中删除数值为50的节点（其为跟节点）：

1
2
del_test_root = test_root.delNode(test_root, 50)
del_test_root.print_tree('./BST_del.gv', True)
节点删除前后的二叉搜索树对比

BST用途

二叉搜索树的其中一个用途就是排序，只要对其进行中序遍历，就能得到节点数值的升序排列了。因此，我们只要对列表中的数值构建二叉搜索树，对其中序遍历，就能得到有序数组了。

这个结论也不难证明，利用数学归纳法的思想即可证明。

BST缺点

二叉搜索树也存在着一些不存之处。如果我们需要构建的二叉搜索树本身就是有序数组（假设其长度为n），那么我们就会得到一个高度为n的二叉搜索树。这是二叉树中最糟糕的情形了。

因此，也存在着一些对二叉搜索树的改良方法，主要是对其高度进行平衡，也就是大名鼎鼎的AVL数和红黑树了。有机会我们再介绍。

总结

本文主要介绍了二叉搜索树（BST）的概念及其相关操作，最后介绍了它的用途和缺点。

笔者早在几年前就想写写数据结构相关的文章，而二叉搜索树、Huffman树早已学习很久了，这次还趁着这个机会写一下，算是弥补之前的懒惰了。

Python
#二叉搜索树
二叉搜索树（BST）的Python实现
https://percent4.github.io/二叉搜索树（BST）的Python实现/
作者
Jclian91
发布于
2024年6月19日
许可协议