二叉搜索树

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

综述

本文主要介绍二叉搜索树的概念、方法以及实现。本文的完整代码可以在我的github找到。

概念

二叉搜索树是一棵满足以下性质的树：

若x为二叉搜索树中的结点，如果y为x左子树的中的一个结点，那么y.key<=x.key。如果y是x右子树的一个结点，则y.key >= x.key。

对于二叉搜索树，有三种遍历方式：

  1. 前序遍历法：先访问根结点，再访问左结点（左子树，下同），最后访问右结点（右子树， 下同）。
  2. 中序遍历法：先访问左结点，再访问根结点，最后访问右结点。
  3. 后序遍历法：先访问左结点，在访问右结点，最后访问根结点。

对于二叉搜索树来说，中序遍历可以得到对树的key值进行排序。

二叉搜索树的方法

二叉搜索树主要有查找、插入、删除、中序遍历、最值等方法。其python代码的实现如下：

1
2
3
4
5
6
7
8
9
10
11
class Node:
    def __init__(self, k):
        self.key = k
        self.parent = None
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None

查找

根据二叉搜索树的性质：设当前结点为cur，若当前结点的key值小于待查找的k，则带查找的元素在其左子树，若相等，则找到，若大于，则在其右子树。搜索时间直接取决于树的高度logn，即其时间复杂度是O(logn)。

1
2
3
4
5
6
7
8
9
10
11
def search(self, k):
    cur = self.root
    while cur:
        if k < cur.key:
            cur = cur.left
        elif k > cur.key:
            cur = cur.right
        else:
            break

    return cur

插入

向一棵二叉搜索树中插入一个元素k，首先要查找到其要搜索的位置，类似于上述的查找过程。因此其时间复杂度也为O(logn)。需要指出的是，树的插入是插入在其叶子节点上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def insert(self, k):
    p = None
    cur = self.root
    while cur:
        p = cur
        if k < cur.key:
            cur = cur.left
        elif k > cur.key:
            cur = cur.right
        else:
            break

    if p is None:
        self.root = Node(k)
    elif k < p.key:
        p.left = Node(k)
        p.left.parent = p
    else:
        p.right = Node(k)
        p.right.parent = p

最值

根据二叉查找树的性质，以node为根结点的树其最小值必然在其左子树上，最大值必然在其右子树上。其时间复杂度均为O(logn)。最大值和最小值的函数并没有直接返回其最值，而是返回其结点。因为对于以node为根结点的树，node的前驱即为其左子树的最大值结点，node的后继即为其右子树的最小值结点。

1
2
3
4
5
6
7
8
9
10
11
def minimum(self, node):
    while node.left:
        node = node.left

    return node

def maximum(self, node):
    while node.right:
        node = node.right

    return node

删除

二叉搜索树删除关键字的基本思路如下：

  1. 查找要删除的结点cur
  2. 如果要删除的结点没有左结点，则使用其右结点替换此结点；如果要删除的结点没有右结点，则使用其左结点替换此结点；如果此结点左右结点都存在，则用其前驱或者后继来替代。在这里，使用其后继结点来替代。transplant函数用结点v去替换结点u。因此其时间复杂度为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
def transplant(self, u, v):
    if u.parent is None:
        self.root = v
    elif u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v

    if v:
        v.parent = u.parent

def delete(self, k):
    cur = self.search(k)
    if cur is None:
        print('there is no value k')
        return -1

    if cur.left is None:
        self.transplant(cur, cur.right)
    elif cur.right is None:
        self.transplant(cur, cur.left)
    else:
        tmp = self.minimum(cur.right)
        if tmp.parent != cur:
            self.transplant(tmp, tmp.right)
            tmp.right = cur.right
            tmp.right.parent = tmp

        self.transplant(cur, tmp)
        tmp.left = cur.left
        tmp.left.parent = tmp

中序遍历

中序遍历的时间复杂度为O(n)，其输出序列为key值按照升序排列的数组。

1
2
3
4
5
def midsort(self, t):
    if t:
        self.midsort(t.left)
        print(t.key, t.parent.key if t.parent else -1)
        self.midsort(t.right)

Reference

本文主要参考《算法导论》。