BST(二叉搜索树)

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

简介

树的数据结构觉得了它能构建成索引结构，且能高效的减少集合的搜索深度，再配合上有序的插入规则，就能进行高效的搜索。这里介绍一种简单的二叉搜索树（BST），BST 的插入规则为，任意节点的左孩子比自身小，右孩子比自身大。

基本操作

插入

时间复杂度：O(log2N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def _insert(self, parent, node):
    ## 这里不处理相同的数
    if parent.value == node.value:
        return
    ## 比较顺序后放入较小的左子树
    elif parent.value > node.value:
        ## 孩子为空，可以插入
        if parent.left == None:
            parent.left = node
            return
        else:
            self._insert(parent.left, node)
            return
    ## 比较顺序后放入较大的右子树
    elif parent.value < node.value:
        ## 孩子为空，可以插入
        if parent.right == None:
            parent.right = node
            return
        else:
            self._insert(parent.right, node)
            return

移除

时间复杂度：O(log2N)

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
def _remove(self,node, key, parent, isLeft):
    ## 搜索节点
    if node == None:
        return
    ## 搜索较大的右子树
    elif node.value < key:
        return self._remove(node.right, key, node, False)
    ## 搜索较的左子树
    elif node.value > key:
        return self._remove(node.left, key, node, True)
    ## 执行移除
    elif node.value == key:
        rmNode = node
        ## 左右子树任意一个为空，都可以直接把另外一个子树提上一层，替换掉移除的节点
        if node.left == None:
            parent.setChild(isLeft, node.right)
        elif parent.right == None:
            parent.setChild(isLeft, node.left)
        else:
        ## 左右子树不为空
            last = node
            ## 在较大的右子树中找到最小的节点与移除的节点进行替换，并移除目标节点
            minNode = node.right
            while minNode.left:
                last = minNode
                minNode = minNode.left
            
            parent.setChild(isLeft, minNode)
            last.setChild(True, None)

        return rmNode

搜索

按照比较顺序进行搜索，可以快速确定目标元素所在子树，减少冗余枝干的遍历操作。

时间复杂度：O(log2N)

1
2
3
4
5
6
7
8
9
def _search(self, parent, value):
    if parent == None:
        return None, False
    elif parent.value == value:
        return parent,True
    elif parent.value < value:
        return self._search(parent.right, value)
    elif parent.value > value:
        return self._search(parent.left, value)

PS:

BST 的所有操作都与树的深度有关，在插入操作时，如果插入的顺序是有序的，那么 BST 就会变成深度为 N 的一叉树，大大降低搜索效率。所以在初始化时，可以进行随机取数，减少有序的概率。

以下是此数据结构的 python 实现
github:[https://github.com/dupouyer/algo/tree/master/BST]