二叉查找树(BST)的基本概念及常用操作

二叉查找树

二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,均为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

常用操作

定义树的节点如下：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

1. 查找

在二叉搜索树 b b 中查找x$x$的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则递归搜索左子树；否则:
4. 递归查找右子树

使用python实现如下：

def search(root, val):
    if root == None:
        return False, None
    elif val > root.val:
        return search(root.right, val)
    elif val < root.val:
        return search(root.left, val)
    else:
        return True, root

2. 插入

向一个二叉搜索树 b b 中插入一个节点s$s$的算法，过程为：

• 若b是空树，则将s所指结点作为根节点插入，否则：
• 若s.val等于b的根节点的数据域之值，则返回，否则：
• 若s.val小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
• 把s所指节点插入到右子树中（新插入节点总是叶子节点）

def insert(self, root, node):
    """insert inplace"""
    if root ==  None:
        root = node
        return
    if node.val == root.val:
        return
    elif node.val > root.val:
        self.insert(root.right, node)
    else:
        self.insert(root.left, node)

3. 删除

二叉搜索树的删除操作分三种情况讨论:
1. 如果待删除的节点是叶子节点，那么可以立即被删除，如下图所示：
例：删除数据为16的节点，是叶子节点，可以直接删除

2. 如果有一个子节点，要将下一个子节点上移到当前节点，即替换之
例：删除数据为25的节点，它下面有唯一一个子节点35, 上移到替换之

3. 如果有两个子节点，则将其右子树的最小数据代替此节点的数据，并将其右子树的最小数据删除，如下图所示
例：删除节点数据为5的节点，找到被删除节点右子树的最小节点。需要一个临时变量successor，将11节点下面的子节点进行查询，找到右子树最小节点7，并把右子树最小节点7替换被删除节点，维持二叉树结构。如下图

class solution:
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if root == None:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left == None:
                return root.right
            elif root.right == None:
                return root.left
            else:
                min_node = self.findMinNode(root.right)
                root.val = min_node.val
                root.right = self.deleteNode(root.right, root.val)
        return root

    def findMinNode(self, node):
        while node.left:
            node = node.left
        return node

4. 遍历

可以采用前序，中序，后序来遍历该二叉搜索树，或者使用广度优先搜索的方式。这里用中序遍历来实现，可以保证按从小到大的顺序打印。

def traverse_binary_tree(root):
    if root is None:
        return
    traverse_binary_tree(root.left)
    print(root.value)
    traverse_binary_tree(root.right)

5. 构造一颗二叉查找树

用一组数值建造一棵二叉查找树的同时，也把这组数值进行了排序。其最差时间复杂度为 O(n2) O ( n 2 ) 。例如，若该组数值经是有序的（从小到大），则建造出来的二叉查找树的所有节点，都没有左子树

def build_binary_tree(values):
    tree = None
    for v in values:
        tree = insert(tree, Node(v))
    return tree

性能分析

查找：最佳情况 Olog(n) O l o g ( n ) , 最坏情况 O(n) O ( n )
插入：最佳情况 Olog(n) O l o g ( n ) , 最坏情况 O(n) O ( n )
删除：最佳情况 Olog(n) O l o g ( n ) , 最坏情况 O(n) O ( n )