数据结构之二叉树——二叉查找树

2,641 阅读5分钟

定义

二叉查找树(Binary Search Tree),又称为二叉搜索树,二叉排序树。它可以是一棵空树,如果不是空树,则具有下列的性质:

  • 非空左子树的所有键值小于其根结点的键值
  • 非空右子树的所有键值大于其根结点的键值
  • 左、右子树都是二叉查找树

比如下面两棵树,左边的树,因为5小于10,应该在10的左子树上,因此不是二叉查找树,右边的树则符合二叉查找树的条件。

由于二叉查找树的特性,中序遍历二叉查找树,得到的就是一个升序的数列。以上图右边的树为例,它的中序遍历则是:15 30 33 41 50

查找

二叉查找树的查找过程,可以分为下面的步骤:

  • 从根结点开始,如果树为空,则返回NULL
  • 如果树不为空,则根结点的值与查找值X进行比较,并进行不同的处理
    • 如果X等于根结点的值,则查找完成,返回结点
    • 如果X小于根结点的值,则在左子树中继续查找
    • 如果X大于根结点的值,则在右子树中继续查找

下图以查找33为例,展示了查找的轨迹

根据上面的步骤,可以使用递归写出该算法

def find(root: TreeNode, key):
    if not root:
        return None
    if key == root.val:
        return root
    elif key < root.val:
        return find(root.left, key)
    else:
        return find(root.right, key)

当然,上面的递归算法中存在尾递归,一般的编译器都会自动优化尾递归,我们也可以将代码改为迭代的方式

def find(root: TreeNode, key):
    if not root:
        return None
    while root:
        if key == root.val:
            return root
        elif key < root.val:
            root = root.left
        else:
            root = root.right

可以看的出来,算法的复杂度和树的高度有关,每一次对比之后都会舍弃掉原来数据的一半,因此算法的时间复杂为O(logn)

最小元素与最小元素

根据二叉查找树的性质:

  • 最小元素一定是在树的最左分枝的端结点上
  • 最大元素一定是在树的最右分枝的端结点上
    算法的实现也比较清晰
def findMax(root: TreeNode):
    if root:
        while root.right:
            root = root.right
    return root


def findMin(root: TreeNode):
    if root:
        while root.left:
            root = root.left
    return root

插入结点

由于二叉查找树具有特定的性质,因此在插入新的结点的时候,也要保证二叉查找树的性质,整个插入新结点的过程与查找的过程类似,

以插入35为例,下图展示了插入35的轨迹

以插入32为例,下图展示例插入32的轨迹

def insert(root: TreeNode, key):
    if not root:
        return TreeNode(key) # 如果是空树,则新建根结点
    while root:
        if key == root.val:
            break # 如果插入的key已经存在,则直接退出循环
        elif key < root.val:
            # 小于向左子树查找
            if not root.left:
                root.left = TreeNode(key)
            else:
                root = root.left
        else:
            # 大于向右子树查找
            if not root.right:
                root.right = TreeNode(key)
            else:
                root = root.right
    return root

删除结点

删除操作比较复杂,要分情况谈论:

要删除的结点为叶子结点

这种情况下,直接删除。如下图要删除35结点

要删除的结点只有一个孩子结点

这种情况下,直接将要删除结点的孩子结点,向上提,替代要删除的结点,如下图要删除33结点

要删除的结点有左、右两棵子树

这种情况下,可以有两种方案:

  • 左子树的最大元素替代要删除结点
  • 右子树的最小元素替代要删除结点

如果要删除41结点(使用左子树最大元素代替)

左子树的最大元素,依旧比右子树的所有元素小,但是比其他左子树的元素大,因此它成为新的根结点的时候,依旧能保持左子树下的所有元素比根结点小,右子树下的所有元素比根结点大。

如果要删除41结点(使用右子树最小元素代替)

右子树的最小元素,依旧比左子树的所有元素大,但是比其他右子树的元素小,成为新的根结点,依旧能保持二叉查找树的性质

综合上面的情况,代码如下

def delete(root: TreeNode, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        if root.left and root.right:
            # 有左右孩子
            leftMax = findMax(root.left)
            root.val = leftMax.val
            root.left = delete(root.left, leftMax.val)
        elif not root.left and not root.right:
            # 叶子结点
            root = None
        elif root.left:
            # 只有左孩子
            root = root.left
        elif root.right:
            # 只有右孩子
            root = root.right
    return root

在有左右孩子的情况下,实际上只是把替代结点的值赋值给要删除结点的值真正删除的是原来的替代结点,比如要删除41结点,替代结点为35,则把41改为35,然后删除原来的35结点。

总结

二叉查找树将数据按照顺序组织好,排列成二叉树结构,因此相关算法的复杂度基本取决于树的高度,如果在构建二叉查找树的时候,不注意树的高度,容易构建成一棵斜树,这样二叉查找树就失去了优势。

二叉查找树有较高的插入和删除效率,并且具备较高的查找效率,对组织动态数据比较友好。

Thanks!