二叉查找树和二叉排序树

二叉查找树和二叉排序树是同一种数据结构，也称为二叉搜索树。它是一种特殊的二叉树，具有以下性质：若左子树不为空，则左子树上所有节点的值均小于它的根节点的值；若右子树不为空，则右子树上所有节点的值均大于它的根节点的值；左、右子树也分别为二叉排序树；没有键值相等的节点。二叉搜索树可以用于快速查找、插入和删除数据，其平均时间复杂度为 O(log2n)。

相关问题

二叉排序树和二叉平衡树

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：

1. 左子树上的所有节点的键值小于根节点的键值；
2. 右子树上的所有节点的键值大于根节点的键值；
3. 左右子树本身也是一棵二叉排序树。

二叉排序树的优点是可以快速进行查找、插入和删除操作，时间复杂度为O(log n)。

但是，当二叉排序树的节点插入或删除时，可能会导致树的高度变得很大，从而降低了查找、插入和删除操作的效率。为了解决这个问题，引入了二叉平衡树。

二叉平衡树（Balanced Binary Tree）是一种特殊的二叉树，它满足以下性质：

1. 左子树和右子树的高度差不超过1；
2. 左右子树本身也是一棵平衡二叉树。

常见的二叉平衡树有AVL树、红黑树等。二叉平衡树通过限制树的高度差，保证了查找、插入和删除操作的时间复杂度为O(log n)。

二叉排序树查找

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下条件：

1. 对于任意节点，左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。

2. 左右子树也都是二叉排序树。

基于以上性质，二叉排序树可以用于查找、插入和删除操作。其中，查找操作可以通过递归地比较当前节点的值和目标值的大小，来决定向左子树还是右子树继续查找。如果找到了目标值，则返回该节点；如果遍历到叶子节点仍未找到目标值，则返回空。

下面是一个简单的二叉排序树查找的示例代码：

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

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

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

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

在以上代码中，`TreeNode` 表示二叉排序树中的节点，`BST` 表示二叉排序树本身。`search` 方法用来查找特定值，`_search` 方法是递归的，用来在二叉排序树中查找节点。如果找到了目标值，则返回该节点；否则返回空。