Python二叉搜索树(二叉查找树)

二叉搜索树是一种特殊的二叉树,树中的元素排列符合二叉搜索树性质。二叉搜索树中,每一个节点存储的元素称作该节点的键值。二叉搜索树也称二叉查找树。

二叉搜索树基础

二叉搜索树可以是一棵空树,也可以是具有如下几条性质的一棵二叉树:
  • 若任意一个节点的左子树非空,那么左子树中所有的元素都小于当前节点存储的元素;
  • 若任意一个节点的右子树非空,那么右子树中所有的元素都大于当前节点存储的元素;
  • 任意一个节点的左右子树也为二叉搜索树;
  • 二叉搜索树中没有两个节点有相同的键值。

根据这些性质可以推出,插入、删除和查找二叉搜索树操作的时间复杂度都是 O(lgn)。一般来说,二叉搜索树可以用 3 个列表模拟存储,它们分别是 left、right 和 key。这 3 个列表中,下标相同的位置属于同一个节点。编号为 i 的节点的左孩子用 left[i] 表示,右孩子用 right[i] 表示,而键值用 key[i] 表示。

二叉搜索树支持的操作有:
  1. 建立二叉搜索树;
  2. 插入键值为 x 的节点;
  3. 查询键值为 x 的节点在二叉搜索树中的排名;
  4. 删除键值为 x 的节点;
  5. 求键值为 x 的节点的前驱与后继。

二叉搜索树的建立

二叉搜索树的每个节点和二叉树一样,有一个储存节点本身数据的变量,还有两个储存左右孩子的变量,如图 1 所示。
二叉搜索树的节点
图 1:二叉搜索树的节点

同样,把树的节点定义为一个类:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right= None

随后,把二叉搜索树也定义为一个新的类。假设二叉搜索树中的所有元素都以列表的形式输入,我们可以在类内的 init( ) 函数中初始化。

初始化空二叉搜索树的代码如下:
class BST:
    def __init__(self, tlist):
        self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
        for i in tlist[1:]: #按顺序把剩下的元素用insert()函数插入二叉搜索树中
            self.insert(i)

这段代码中,用到了二叉搜索树的插入操作,下面就会讲到。在执行插入操作之前,首先要写出查找操作,即在二叉搜索树中查找是否有键值为 val 的节点。如果有,返回节点的位置;如果没有,返回 0。

二叉搜索树查找节点

我们用图 2 中这棵二叉搜索树来演示一下查找的过程,以查找键值为 8 的节点为例。
从根节点开始
图 2:从根节点开始

1)  首先,如图 2 所示,从根节点开始查找。根节点的键值为 9,比我们要查找的键值要大。可以得出,要查找的节点若存在,必定在它的左子树中。所以,要查找的下一个节点就是根节点的左孩子节点。如图 3 所示,进入左子树。
进入左子树
图 3:进入左子树

2) 其次,把当前节点的键值和要查找的键值对比,发现它的键值小于要查找的键值。可以得出,要查找的节点若存在,必定在当前节点的右子树中。

3) 重复类似的步骤,在键值为 5 的节点处同样判定为进入右子树,如图 4 所示。
找到节点
图 4:找到节点

此时,节点的键值与要查找的键值相等,返回当前位置,查找结束。

4) 最后,我们用键值 18 来做一次查找,这一次 18 不存在于二叉搜索树中。同样,从根节点开始,通过当前节点的键值大小判定,走过键值为 9→14→19→17 的节点,如图 5 所示。
查找键值18的路径
图 5:查找键值 18 的路径

此时,要查找的键值 18 大于当前节点的键值 17。如果要查找的节点存在,那么它必定在当前节点的右子树中。但是,当前节点的右孩子为空,说明不存在右子树,也不存在键值为 18 的节点。返回 0,查找结束。查找的路径如图 5 所示。

下面是查找操作的代码实现,同样作为类内的一个函数:
class BST:
    def __init__(self, tlist):
        self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
        for i in tlist[1:]: #按顺序把剩下的元素用insert()函数插入二叉搜索树中
            self.insert(i)
    #查找
    def search(self, node, parent, data):
        if node is None: #如果当前的位置为空,但仍没有查找到与data相等的元素
            return 0, node, parent
        elif data == node.data: #查找到了与data相等的元素
            return 1, node, parent
        elif data < node.data: #data小于当前节点的数据,进入左子树
            return self.search(node.left, node, data)
        else: #data大于当前节点的数据,进入右子树
            return self.search(node.right, node, data)
在这段代码中,无论是否成功查找到 data,都要返回最后的节点 node 和它的父亲节点 parent,用于其他操作中。

除简单的查找操作外,我们还可以在二叉搜索树中查找一个数的前驱和后继。在二叉搜索树中, x 的前驱指小于 x 的所有数中最大的数,而后继指大于 x 的所有数中最小的数。同样地,我们用图片来演示查找前驱和后继的过程。

二叉树前驱节点查找

首先我们来看在二叉树中如何查找一个数的前驱。我们知道,作为 x 前驱的数一定是小于 x 的。那么,如果键值为 x 的节点有左子树,x 的前驱就是它左子树中键值最大的节点。如果键值为 x 的节点没有左子树,那么 x 的前驱一定在从根节点到x经过的查找路径中。很显然,查找的过程就是节点的键值向 x 靠近的一个过程。

以节点 5 为例,在二叉搜索树中查找它的前驱。

如图 6 所示,在搜索到键值为 5 的节点后,发现节点有左子树。
搜索到键值为5的节点
图 6:搜索到键值为 5 的节点

此时,进入左子树并查找左子树中的最大值。如果左子树中有多个节点,进入左子树后应当不断地往右继续遍历,直到右子树为空。此时,如图 7 所示,键值为5的节点的左子树中只有一个键值为3的节点;此时,该节点的右子树已经为空,那么 5 的前驱就是 3 了。
找到前驱
图 7:找到前驱
我们再以15为例求一次前驱。

1)  如图 8 所示,从根节点开始,查找算法走过了图 12 中最右侧的这一条路径,到达了键值为 15 的节点。
查找节点15
图 8:查找节点 15

而键值为 15 的节点没有左子树,则它的前驱在 9→14→19→17 这一条路径中。所以,在这一条路径经过的节点中,所有键值小于 15 的节点里最大的节点就是 15 的前驱。在这棵二叉搜索树中,15 的前驱是 14。

2) 同理,如果二叉搜索树中不存在搜索 x,那么 x 的前驱仍然在它经过的路径中。假设在同一棵二叉搜索树中搜索 18,会经过图 9 所示这样一条路径。
查找节点18
图 9:查找节点 18

4) 此时,如图 9 所示,查找函数到达一个空节点。在这种情况下,当前节点自然不会有左子树。采用同样的方法,在经过的路径中求得前驱 17 即可。

在二叉搜索树中求前驱的代码如下:
#查找前驱
def getlast(self, node, data,maxn):
    if node is None: #如果当前的位置为空,但仍没有查找到与data相等的元素
        return 0, maxn #返回目前经过路径上最大的符合前驱要求的数
    elif data == node.data: #找到了与data相等的元素
        if node.left == None: #值为data的节点没有左子树
            return 1, maxn #返回目前经过路径上最大的符合前驱要求的数
        else: #值为data的节点有左子树
            tmp = node.left #进入左子树后找到左子树中最大的数
            while tmp.right is not None:
                tmp = tmp.right
            return 1, tmp #返回左子树中最大的数(最右边的数)
    elif data < node.data: #data小于当前节点的数据,进入左子树
        return self.getlast(node.left, data, maxn)
    else: #data大于当前节点的数据,进入右子树
        If maxn.data < node.data #如果当前数据比已经存储在maxn中的前驱要大,更新maxn
            maxn = node
        return self.getlast(node.right, data, maxn)

二叉树后继节点查找

查找后继的方法和查找前驱的方法极为类似,只需要改动一些判断条件即可。

同理,作为 x 后继的数一定大于 x。如果键值为 x 的节点有右子树,x 的后继就是它右子树中键值最小的节点,也就是进入右子树后最左侧的节点。如果键值为 x 的节点没有右子树,那么 x 的后继一定在从根节点到 x 经过的查找路径中。

1) 我们以 14 为例,在图 10 中的二叉搜索树进行后继的查找。
找到键值为14的节点
图 10:找到键值为 14 的节点

2) 在开始查找后,很快就找到了键值为 14 的节点,如图 10 所示。此时,进入 14 的右子树,并不断向左搜索,直到当前节点的左子树为空。很快,14 的后继 15 就找到了,如图 11 所示。
找到后继
图 11:找到后继

3) 当二叉搜索树中没有要查找的值,或查找到的节点没有右子树时,与查找前驱时一样,在路径中找到最小的后继即可。

下面是后继查找的代码实现:
#查找后继
def getnext(self, node, data,minn):
    if node is None: #如果当前的位置为空,但仍没有查找到与data相等的元素
        return 0, minn #返回目前经过路径上最小的符合后继要求的数
    elif data == node.data: #找到了与data相等的元素
        if node.right == None: #值为data的节点没有右子树
            return 1, minn #返回目前经过路径上最小的符合后继要求的数
        else: #值为data的节点有右子树
            tmp = node.right #进入右子树后找到右子树中最小的数
            while tmp.left is not None:
                tmp = tmp.left
            return 1, tmp #返回右子树中最小的数(最左边的数)
    elif data < node.data: #data小于当前节点的数据,进入左子树
        if minn.data > node.data #如果当前数据比已经存储在minn中的后继要小,更新minn
            minn = node
            return self.getlast(node.left, data, minn)
    else: #data大于当前节点的数据,进入右子树
        return self.getlast(node.right, data, minn)

由于查找后继的代码与查找前驱结构基本相同,在此不多做阐述。

二叉搜索树插入节点

而插入操作和查找操作的原理极为相似,使用相同的判定方法,为节点查找到插入的正确位置。我们仍然以同一棵二叉查找树为例,用元素 18 模拟插入的过程。

1) 如图 12 所示,插入操作同样从根节点开始,根节点上的键值 9 小于 18,说明 18 正确的插入位置应当在节点的右子树中。
从根节点开始查找
图 12:从根节点开始查找

2) 类似地,18 也大于 14,所以仍然进入右子树,如图 13 所示。
进入右子树
图 13:进入右子树

3) 按照这个规律,元素 18 的插入操作沿着 9→14→19→17 的路线一路向下,到达了键值为 17 的节点,如图 14 所示。
找到插入位置的父亲节点
图 14:找到插入位置的父亲节点

4) 此时,元素 18 大于 17,应该进入 17 的右子树;但 17 的右指针为空,说明它没有右孩子。这时候,新建一个空节点,把新节点的键值赋值为 18,再让键值为 17 的节点的右指针指向新的节点。插入之后的二叉搜索树如图 15 所示。
插入节点
图 15:插入节点

这样,节点就插入完成了。如果二叉搜索树中节点的键值没有与要插入的元素重合,那么一定会有这样一个唯一的空位供新节点插入;反之,如果有重合的节点,那么一定会被查找到。这时候,不需要插入,直接 return 退出函数即可。

将插入操作的代码加入类中,具体如下:
class BST:
    #初始化
    def __init__(self, tlist):
        self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
        for i in tlist[1:]: #按顺序把剩下的元素用insert函数插入二叉搜索树中
            self.insert(i)
    #查找
    def search(self, node, parent, data):
        if node is None: #如果当前的位置为空,但仍没有查找到与data相等的元素
            return 0, node, parent
        elif data == node.data: #找到了与data相等的元素
            return 1, node, parent
        elif data < node.data: #data小于当前节点的数据,进入左子树
            return self.search(node.left, node, data)
        else: #data大于当前节点的数据,进入右子树
            return self.search(node.right, node, data)
    #插入
    def insert(self, data):
        exist, n, p = self.search(self.root, self.root, data) #接收查找操作的数据
        if exist: #如果数据为data的节点已经存在,则不需要执行插入操作,直接返回
            return
        else: #数据为data的节点不存在
            new_node = TreeNode(data) #新建一个节点
            if data > p.data: #如果data大于父亲节点,在右孩子的位置上插入
                p.right = new_node
            else: #如果data小于父亲节点,在左孩子的位置上插入
                p.left= new_node

二叉搜索树删除节点

最后要讲到的一种操作是二叉搜索树中的删除操作,效果是删除二叉搜索树中键值为 x 的节点。首先,先查找到键值为 x 的节点,再进行删除操作。

在删除二叉搜索树中的节点时,又分为两种情况:
  1. 键值为 x 的节点的子节点个数小于 2,此时直接删除掉当前节点,并令当前节点的子节点填补上删除后的空位,与父节点相连;
  2. 键值为 x 的节点有左右子树,此时在二叉搜索树中查找键值x的后继节点 next。此时,next 必然没有左子树,所以直接删除 next,让 next 的右孩子代替 next 原来的位置。随后,再把键值 x 改成 next 的键值。

我们仍然用图解的方法来展示删除节点的过程。

1) 首先,以删除键值为17的节点为例。如图 16 所示,在二叉搜索树中搜索到节点17,并且得到判断:当前节点只有左子树。
找到键值为17的节点
图 16:找到键值为 17 的节点

此时,直接删除键值为 17 的节点,并使它的左孩子直接与父节点相连。删除节点 17 后的二叉搜索树如图 17 所示。
删除完毕
图 17:删除完毕

2) 接着,举个待删除节点有两个孩子节点的例子。当要删除键值为 5 的节点时,同样先在二叉搜索树中进行搜索,如图 18 所示。
找到键值为5的节点
图 18:找到键值为 5 的节点

3) 检测到当前节点有两个孩子节点,这时候,如图 19 所示,在二叉搜索树中查找 5 的后继,得到键值为 8 的节点。
找到5的后继8
图 19:找到 5 的后继 8

4) 此时,对键值为 8 的节点同样执行二叉搜索树中的删除操作。由于这个节点没有孩子节点,所以直接把这个节点删除即可。图 20 所示为删除后继完毕之后的二叉查找树。
删除后继完毕
图 20:删除后继完毕

5) 最后,把原来要删除的节点上的键值改为后继的值,如图 21 所示。
改变要删除节点的键值
图 21:改变要删除节点的键值:

至此,删除操作就完成了。

二叉搜索树中删除操作的代码实现如下:
#删除操作
def delete(self, root, data):
    exist, n, p = self.search(root, root, data)
    if not exist: #要删除的数据不存在
        print("data does not exist")
    else:
        if n.left is None: #要删除的节点左子树为空
            if n == p.left: #如果n是左孩子,把p的左孩子赋值为n的右孩子
                p.left= n.right
            else: #如果n是右孩子,把p的右孩子赋值为n的右孩子
                p.right= n.right
            del n #删除n
        elif n.right is None: #要删除的节点右子树为空
            if n == p.left: #如果n是左孩子,把p的左孩子赋值为n的左孩子
                p.left= n.left
            else: #如果n是右孩子,把p的右孩子赋值为n的左孩子
                p.right= n.left
            del n #删除n
        else: # 左右子树均不为空
            tmp = n.right #进入n的右子树
            if tmp.left is None: #如果n的右孩子没有左子树,则n的右孩子就是n的后继
                n.data = tmp.data
                n.right = tmp.right
                del tmp
            else:
                next = tmp.left
                while next.left is not None: #在右子树中查找n的后继
                    tmp = next
                    next = next.left
                n.data = next.data
                tmp.left= next.right
                del next #删除next

把实现这些操作的函数都写在类中,就可以组成一棵拥有完整功能的二叉搜索树了。