算法学习记录-查找——二叉排序树(Binary Sort Tree)

一、什么是二叉排序树(Binary Sort Tree)

二叉排序树，又称二叉搜索树或二叉查找树，是一种特殊的二叉树，它的每个节点的左子树所有节点的值都小于该节点的值，而右子树所有节点的值都大于该节点的值。

在二叉排序树中，查找、插入和删除等操作的时间复杂度都是 O(logn)，非常高效。

二、二叉排序树的构建

在构建二叉排序树时，我们可以依次将新节点插入到根节点的左右子树中，保证左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。如果待插入的节点的值与根节点的值相等，我们可以选择将其放入左子树或右子树。

以下是一个简单的构建二叉排序树的例子：

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

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

    def insert(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if node.left is None:
                node.left = Node(val)
            else:
                self._insert(val, node.left)
        else:
            if node.right is None:
                node.right = Node(val)
            else:
                self._insert(val, node.right)

三、二叉排序树的操作

查找

在二叉排序树中查找节点其实就是不断地比较节点的值，如果待查找的节点值小于当前节点的值，则继续在左子树中查找，如果待查找的节点值大于当前节点的值，则继续在右子树中查找。如果找到了待查找的节点，则返回该节点，否则返回 None。

以下是一个简单的查找操作的例子：

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

    def insert(self, val):
        # 略

    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if node is None:
            return None
        elif node.val == val:
            return node
        elif val < node.val:
            return self._search(val, node.left)
        else:
            return self._search(val, node.right)

插入

在二叉排序树中插入节点其实就是查找待插入的节点在树中的位置，然后将其插入到合适的位置上。

以下是一个简单的插入操作的例子：

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

    def insert(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            self._insert(val, self.root)

    # 略

    def _insert(self, val, node):
        # 略

删除

在二叉排序树中删除节点其实就是查找待删除的节点在树中的位置，然后将其从树中删除，并保证删除后仍然是一棵二叉排序树。

一般来说，删除节点有以下三种情况：

1. 待删除的节点没有子节点。直接删除即可。
2. 待删除的节点只有一个子节点。将该子节点替代待删除的节点即可。
3. 待删除的节点有两个子节点。此时需要找到该节点的后继节点或前驱节点作为替代节点。

以下是一个简单的删除操作的例子：

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

    def insert(self, val):
        # 略

    # 略

    def delete(self, val):
        self._delete(val, self.root)

    def _delete(self, val, node):
        if node is None:
            return node

        if val < node.val:
            node.left = self._delete(val, node.left)
        elif val > node.val:
            node.right = self._delete(val, node.right)
        else:
            if node.left is None:
                temp = node.right
                node = None
                return temp
            elif node.right is None:
                temp = node.left
                node = None
                return temp

            temp = self.find_min(node.right)
            node.val = temp.val
            node.right = self._delete(temp.val, node.right)

        return node

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

四、总结

二叉排序树是一种高效的排序和查找算法，可以用于实现查找、插入、删除等操作。在实际应用中，我们需要根据具体的情况选择不同的实现方式，以达到最优的效果。