二叉搜索树

发表于 | 更新于: | 分类于
字数统计: 1.1k

查找问题

  1. 静态查找 不需要进行插入删除操作，使用二分查找即可
  2. 动态查找 需要执行插入删除操作，使用二分查找树

前提是都是有序的。

二叉搜索树

二叉搜索树(BST，Binary Search Tree)， 也称二叉排序树或二叉查找树。

BST可以为空，非空BST如果不为空，满足以下性质：

  1. 非空左子树的所有键值小于其根结点的键值。
  2. 非空右子树的所有键值大于其根结点的键值。
  3. 左、右子树都是二叉搜索树。

BST操作的特殊函数：

1
2
3
4
5
6
7
8
9
10
# 查找元素x
def Find(root, taregt)
# 查找最大元素
def FindMax(root)
# 查找最小元素
def FindMin(root)
# 插入
def Insert(x, root)
# 删除
def Delete(x, root)

函数实现

Find

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
# Find递归实现
def BSTFindRecursion(self, node, targrt):
    if node is None:
        return None

    if target > node.val:
        return self.BSTFindRecursion(node.right)

    elif targrt < node.val:
        return self.BSTFindRecursion(node.left)

    else:
        return node

# 上面的递归是一种伪递归，伪递归可以用迭代实现即循环
# Find非递归实现
def BSTFindNoRecursion(self, node, target):
    while node:
        if target > node.val:
            node = node.right
        elif targrt < node.val:
            node = node.left
        else:
            return node

    return None

FindMax和FindMin

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
25
26
27
28
29
30
31
32
33
# 查找最大元素
def BSTFindMax(self, node):
    if node is None:
        return None
    elif node.right:
        return self.BSTFindMax(node.right)
    else:
        return node

# 查找最大元素非递归
def BSTFindMaxNoRecursion(self, node):
    if node:
        while node.right:
            node = node.right

    return node

# 查找最小元素
def BSTFindMin(self, node):
    if node is None:
        return None
    elif node.left:
        return self.BSTFindMin(node.left)
    else:
        return node

# 查找最小元素非递归
def BSTFindMinNoRecursion(self, node):
    if node:
        while node.left:
            node = node.left

    return node

Insert

主要是插入位置的选择，这里类似于Find，代码实现如下：

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
# 插入操作递归
def BSTInsert(self, node, x):
    if node is None:
        node = TreeNode(x)

        return node

    if node.val > x:
        # 插入的位置位于结点的左边，所以使用node.left
        node.left = self.BSTInsert(node.left, x)
    elif node.val < x:
        # 插入的位置位于结点的左边，所以使用node.right
        node.right = self.BSTInsert(node.right, x)

    return node

# 插入操作非递归
def BSTInsertNoRecursion(self, node, x):
    if node is None:
        node = TreeNode(x)

        return node

    tmp = node

    while tmp:
        if tmp.val > x:
            # node = node.left
            if tmp.left:
                tmp = tmp.left
            else:
                tmp.left = TreeNode(x)
                break
        elif tmp.val < x:
            if tmp.right:
                tmp = tmp.right
            else:
                tmp.right = TreeNode(x)
                break

    return node

Delete

删除操作相对来说复杂一点，需要考虑三种情况：

  1. 如果是叶子节点的话直接删除，其父节点对应的指针置为空
  2. 只有一个子结点，将其父结点对应的指针指向其子结点
  3. 如果有两个子结点，寻找一个合适的结点去替代这个被删除的结点
    1. 使用右子树的最小值
    2. 使用左子树的最大值

为什么第三种情况要这么做？这么做的好处——左子树的最大值或者右子树的最小值一定不是有两个儿子的结点。左子树的最大值肯定位于左子树的最右边，右子树的最小值肯定位于右子树的最左边。

举个例子：
上面树的Delete代码实现如下：

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
def BSTDelete(self, node, x):
    if node is None:
        return node

    if node.val > x:
        node.left = self.BSTDelete(node.left, x)
    elif node.val < x:
        node.right = self.BSTDelete(node.right, x)
    else:
        # 说明已经找到这个结点，开始做删除操作
        if node.left and node.right:
            # 这里使用右子树的最小值进行替换
            # 找到对应的值先替换，接着删除原来这个值对应的结点
            tmp = self.BSTFindMin(node.right)
            node.val = tmp.val
            node.right = self.BSTDelete(node.right, node.val)
        else:
            # 有右孩子或者无子结点
            if node.left is None:
                node = node.right
            # 有左孩子或者无子结点
            elif node.right is None:
                node = node.left

    return node

def BSTDeleteNoRecursion(self, node, x):
    if node is None:
        return node

    tmp = node
    while tmp:
        if tmp.val > x:
            tmp = tmp.left
        elif tmp.val < x:
            tmp = tmp.right
        else:
            if tmp.left and tmp.right:
                tmp.val = self.BSTFindMinNoRecursion(tmp.right).val
                tmp.right = tmp.right.right
                x = tmp.val
            else:
                if tmp.left is None:
                    tmp = tmp.right
                elif tmp.right is None:
                    tmp = tmp.left

    return node