二叉搜索树

二叉排序树是带根结点的二叉树，其内部结点各自存储一个关键字(以及可选的相关值),并且各自具有两个可区分的子树，通常表示为左和右。该树还拥有二分搜索的属性，该属性声明每个结点中的关键字必须大于或等于左子树中存储的任何关键字，并且小于或等于右子树中存储的任何关键字。^[1] 树的叶子(最终结点)不包含关键字，也没有结构来区分它们。

通常，每个结点代表的信息是一条记录，而不是一个数据元素。 然而，出于排序的目的，结点是根据它们的关键字而不是它们相关记录的任何部分进行比较的。二叉排序树相对于其他数据结构的主要优势是在分类算法和 搜索算法比如有序遍历中非常有效；它们也很容易编码。

二叉搜索树是用于构造更抽象的数据结构（如集合，多集合和关联数组）的基础数据结构。.

• 当在二叉排序树中插入或搜索元素时，必须将每个被访问结点的关键字与要插入或找到的元素的关键字进行比较。
• 二叉排序树的形状完全取决于插入和删除的顺序，并且可能退化。
• 在长时间随机插入和删除的混合序列之后，树的预期高度接近关键字数量的平方根 √n，它的增长速度比 log n快得多。
• 已经有许多研究来防止树的退化，这种退化导致最坏情况下的时间复杂度 O(n) (有关详细信息，请参见部分)。

1.1 顺序关系

顺序关系二元搜索需要一种顺序关系，通过该顺序关系，每个元素（项）可以与总先序状态下的其他元素进行比较。 在比较中有效发生的元素部分称为其关键字。 是否允许在树中允许重复，即具有相同关键字的不同元素，不依赖于顺序关系，而是仅依赖于应用程序。在二分搜索树的上下文中，通过三向比较子例程最灵活地实现总先序。

二叉排序树支持三种主要操作:插入元素、删除元素和查找(检查关键字是否存在)。

2.1 搜索

可以对在二叉排序树中搜索特定关键字进行递归或者迭代地编程。

我们从检查根结点开始。如果树是空的，树中不存在我们正在搜索的关键字。否则，如果关键字等于根关键字，搜索成功，我们返回结点。如果键小于根的关键字，我们搜索左边的子树。类似地，如果关键字大于根的关键字，我们搜索右边的子树。重复这个过程，直到找到关键字或剩余的子树为空。如果在到达空 子树之后，未找到该关键字，则关键字不在树中。这很容易表达为递归算法(在python中实现):

1 def search_recursively(key, node):
2     if node is None or node.key == key:
3         return node
4     if key < node.key:
5         return search_recursively(key, node.left)
6     # key > node.key
7     return search_recursively(key, node.right)

相同的算法可以迭代实现:

 1 def search_iteratively(key, node): 
 2     current_node = node
 3     while current_node is not None:
 4         if key == current_node.key:
 5             return current_node
 6         if key < current_node.key:
 7             current_node = current_node.left
 8         else: # key > current_node.key:
 9             current_node = current_node.right
10     return current_node

这两个例子依赖于顺序关系是一个总先序。

如果顺序关系只是一个总先序，功能的合理扩展如下: 同样在向用户指定的方向向下搜索叶子的情况下。 配备有这种比较功能的二叉树排序变得稳定。

因为在最坏的情况下，该算法必须从树根搜索到离树根最远的叶子，所以搜索操作需要的时间与树的高度成正比(参见树术语)。平均而言，二叉排序树具有 n 结点具有 O(log n) 高度。 然而，在最坏的情况下，不平衡的树类似链表(退化树)，二叉排序树可能有 O(n) 高度。

2.2 插入

插入从搜索开始时开始；如果关键字不等于根的关键字，我们像以前一样搜索左或右子树。最终，我们将到达一个外部结点，根据结点的关键字，将新的键值对(这里编码为记录“新结点”)添加为它的右子结点或左子结点。换句话说，我们检查根，如果它的键小于根的键，我们递归地将新结点插入左子树，如果它的键大于或等于根，我们递归地插入右子树。

以下是如何在C ++中的二叉树中执行典型的二叉搜索树插入：

void insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key == root->key)
    root->value = value;
  else if (key < root->key)
    insert(root->left, key, value);
  else  // key > root->key
    insert(root->right, key, value);
}

或者，可以像这样实现非递归版本。 使用指向指针的指针来跟踪我们来自哪里让代码避免显式检查和处理需要在树根处插入结点的情况[2]：

void insert(Node** root, int key, int value) {
  Node **walk = root;
  while (*walk) { 
    int curkey = (*walk)->key;
    if (curkey == key) {
      (*walk)->value = value;
      return;
    }
    if (key > curkey) 
      walk = &(*walk)->right;
    else 
      walk = &(*walk)->left;
  }
  *walk = new Node(key, value);
}

上述破坏性程序变体修改了树。 它仅使用常量堆空间（并且迭代版本也使用常量堆栈空间），但树的先前版本将丢失。 或者，如下面的Python示例所示，我们可以重建插入结点的所有祖先; 对原始树根的任何引用仍然有效，使树成为永久的数据结构：

def binary_tree_insert(node, key, value):
   if node is None:
       return NodeTree(None, key, value, None)
   if key == node.key:
       return NodeTree(node.left, key, value, node.right)
   if key < node.key:
       return NodeTree(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
   return NodeTree(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

重建的部分在平均情况下使用O(log n)空间，在最坏的情况下使用 O(n)。在任一版本中，此操作需要与最坏情况下树的高度成比例的时间，即在所有树的平均情况下为O(log n)时间，但在最坏情况下为O(n)时间。解释插入的另一种方法是，为了在树中插入新结点，首先将其键与根的键进行比较。如果其键小于根，则将其与根的左子树的键进行比较。如果它的键更大，则将它与根结点的右子树进行比较。此过程继续，直到将新结点与叶结点进行比较，然后将其添加为此结点的右子结点或左子结点，具体取决于其键：如果键小于叶子的键，则将其作为叶子插入左孩子，否则作为叶子的右孩子。

还有其他方法可以将结点插入到二叉树中，但这是在叶子处插入结点并同时保留BST结构的唯一方法。

2.3 删除

从二叉搜索树中删除结点时，必须维护结点的有序序列。 有很多可能性来做到这一点。 然而，T.Hibbard在1962年提出的以下方法[3]保证了主题子树的高度至多改变了一个。 有三种可能的情况需要考虑：。

• 删除没有子结点的结点：只需从树中删除结点即可。
• 删除带有一个子结点的结点:删除该结点并用其结结点替换它。
• 删除具有两个子结点的结点：调用要删除的结点D.不要删除D.而是选择其先序遍历的前结点或其后序遍历的后继结点作为替换结点E（s图）。 将E的使用值复制到D. [注2]如果E没有孩子，只需从其前双亲结点G中删除E.如果E有一个孩子，比如说F，它是一个右孩子。 在E的双亲结点下用F替换E.

在所有情况下，当D恰好是根时，再次使替换结点为根结点。

从广义上讲，有孩子的结点更难删除。 与所有二叉树一样，结点的先序后继是其右子树的最左边的子结点，结点的先序前驱是左子树的最右边的子结点。 在其他情况下，该结点将只有一个或根本没有孩子。 根据上述两个简单案例中的一个删除它。

对于两子案例的每个实例一致地使用先序后继或先序前驱可能导致出现不平衡树，因此选择不同实现所需时间也不同。

运行时间分析：虽然此操作并不总是将树遍历到叶子，但这始终是可能的; 因此，在最坏的情况下，它需要与树的高度成比例的时间。 即使结点有两个子结点，它也不需要更多时间，因为它仍然遵循单个路径并且不会访问任何结点两次。

def find_min(self):   # Gets minimum node in a subtree
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None):
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key):
    if key < self.key:
        self.left_child.binary_tree_delete(key)
        return
    if key > self.key:
        self.right_child.binary_tree_delete(key)
        return
    # delete the key here
    if self.left_child and self.right_child: # if both children are present
        successor = self.right_child.find_min()
        self.key = successor.key
        successor.binary_tree_delete(successor.key)
    elif self.left_child:   # if the node has only a *left* child
        self.replace_node_in_parent(self.left_child)
    elif self.right_child:  # if the node has only a *right* child
        self.replace_node_in_parent(self.right_child)
    else:
        self.replace_node_in_parent(None) # this node has no children

2.4 遍历

一旦创建了二叉搜索树，就可以通过递归遍历根节点的左子树，访问节点本身，然后递归遍历节点的右子树，继续使用每个节点的模式来按顺序检索其元素。 这个树是递归访问的。 与所有二叉树一样，可以进行先序遍历或后序遍历，但两者都不可能对二叉搜索树有用。 二叉搜索树的先序遍历将始终产生节点项（数字，字符串或其他类似项）的有序列表。

下面给出了Python中先序遍历的代码。 它将调用树中每个节点的回调（程序员希望调用节点值的一些函数，例如打印到屏幕上）。

def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)

遍历需要O（n）时间，因为它必须访问每个节点。 该算法也是O（n），因此它是渐近最优的。

遍历也可以迭代实现。 对于某些应用，例如 更大的等效搜索，近似搜索，单步（迭代）遍历的操作可能非常有用。 当然，这是在没有回调构造的情况下实现的，并且平均花费O（1）和在最坏的情况下O（log n）的时间复杂度。

2.5 确认

有时我们已经有了一棵二叉树，我们需要确定它是否是一个二叉排序树。这个问题有一个简单的递归解决方案。

二叉排序树属性—右子树上的每个节点必须大于当前节点，并且左子树上的每个节点必须小于当前节点 - 是确定树是否是BST的关键。 贪婪算法—简单地遍历树，在每个节点检查节点是否包含大于左子节点的值并且小于右子节点上的值 - 对于所有情况不一定都起作用。 考虑以下树：

     20岁
    /  \
  10    30岁
       /  \
      5    40岁

在上面的树中，每个结点都满足这样的条件，即该结点包含的值大于其左孩子，小于其右孩子，但它不是BST:值5位于包含20的结点的右子树上，这不符了二叉排序树属性。

我们也需要从父结点流下来的信息，而不是仅仅基于结点及其子结点的值做出决策。在上面的树的例子中，如果我们能记住包含值20的结点，我们会看到值5的结点违反了二叉排序树属性条件。

因此，我们需要在每个结点检查的条件是:

• 如果结点是其父结点的左子结点，则它必须小于(或等于)父结点，并且必须将值从其父结点传递到其右子树，以确保该子树中没有任何结点大于父结点
• 如果结点是其父结点的右子结点，那么它必须大于父结点，并且必须将值从其父结点传递到其左子树，以确保该子树中没有任何结点小于父结点。

C++中的递归解决方案可以进一步解释这一点:

struct TreeNode {
    int key;
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isBST(struct TreeNode *node, int minKey, int maxKey) {
    if (node == NULL) return true;
    if (node->key < minKey || node->key > maxKey) return false;
    
    return isBST(node->left, minKey, node->key-1) && isBST(node->right, node->key+1, maxKey);
}

node->key+1 和 node->key-1 只允许BST中不同的元素。

如果我们希望同样的元素也存在，那么我们只能在两个地方使用 node->key。

对该函数的初始调用可以是这样的:

if (isBST(root, INT_MIN, INT_MAX)) {
    puts("This is a BST.");
} else {
    puts("This is NOT a BST!");
}

本质上，我们一直在创建一个有效的范围(从[最小值开始，最大值开始)，并在递归下降时不断缩小每个结点的范围。

正如#Traversal部分所指出的，二叉搜索树的先序遍历返回已排序的结点。 因此，我们只需要在遍历树时保留上一个被访问结点，并检查其关键字与当前关键字相比是否更小（或更小/相等，如果树中允许重复）。

3.1 分类

二叉排序树可以用来实现一个简单的 分类算法。类似于堆排序，我们将希望排序的所有值插入到新的有序数据结构中——在本例中是二叉排序树——然后按顺序遍历它。

build_binary_tree 的最坏的情况是O(n²)—如果您向它提供一个排序的值列表，它会将它们链到一个没有左子树链表。例如， build_binary_tree([1, 2, 3, 4, 5]) 出产树 (1 (2 (3 (4 (5)))))。

有几种方案可以用简单的二叉树克服这个缺陷；最常见的是自平衡二叉排序树。如果使用这样的树完成相同的过程，则总体最坏情况时间是O（n log n），这对于比较排序是渐近最优的。 实际上，基于树的排序（特别是节点分配）在时间和空间上增加的开销会使其不如其他渐近最优的排序，例如静态列表排序的堆。 另一方面，它是增量排序的最有效方法之一，随着时间的推移将项添加到列表中，同时始终对列表进行排序。

3.2 优先级队列操作

二叉排序树可以用来实现优先级队列: 允许插入任意键以及查找和删除最小(或最大)键的结构。插入操作如前所述。 查找最小值的方法是沿着树走，尽可能地跟随左边的指针，但不要碰到叶子:

//前提条件:它不是叶子
功能 find-min(T):
    正在… 左侧(T):
        t。左(右)
    返回 键(T)

找最大值也是类似的：尽可能沿着往右的指针。 删除最小值(最大值)可以简单地看作查找最小值(最大值)，然后将其删除。 这样，插入和删除都采用对数时间，就像它们在二分的堆中一样，但与二分制堆和大多数其他优先级队列实现不同，单个树可以同时支持所有查找最小值，查找最大值，删除最小值和删除最大值，使二叉搜索树适合作为双端优先级队列。^[2]

有许多类型的二叉搜索树。 AVL树和红黑树都是 自平衡二叉排序树的形式。伸展树是一个二叉搜索树，可以自动移动更靠近根的频繁访问的元素。 在treap（树堆）中，每个节点还拥有（随机选择的）优先级，父节点的优先级高于其子节点。 探戈树是为快速搜索而优化的树。 T树是经过优化可以减少存储空间开销的二叉搜索树，广泛用于内存数据库。

退化树是一棵满足对于每个父节点，只有一个关联的子节点的树。 它是不平衡的，在最坏的情况下，性能会降低到链表的性能。 如果您的添加节点功能不能处理重新平衡，那么您可以通过向已经排序的数据提供退化树来轻松地构建退化树。 这意味着在性能测量中，树的行为基本上类似于链表数据结构。

4.1 性能比较

D.A. Heger (2004年)^[3] 介绍了二叉排序树的性能比较。 Treap 被发现具有最好的平均性能，而发现红黑树的性能变化最小。

4.2 最佳二叉排序树

如果我们不打算修改搜索树，并且我们确切地知道每个项目被访问的频率，我们可以构造^[4] 一 最佳二叉排序树，首先它是一棵搜索树，其查找项目的平均成本(即 预期搜索成本)最小。

即使我们只对搜索成本进行估算，这样的系统也可以大大加快查找速度。例如，如果您在拼写检查程序中使用了英语单词的BST，则可以根据文本语料库中的单词频率平衡树，将单词(如the)放置在词根附近，并将单词（如agerasia）放在叶子附近。可以将这样的树与霍夫曼树进行比较，霍夫曼树类似地寻求在根部附近放置经常使用的项以便产生密集的信息编码;但是，霍夫曼树仅在叶子中存储数据元素，并且不需要对这些元素进行排序。

如果我们不知道预先访问树中元素的顺序，我们可以使用与我们可以为任何特定查找操作序列构造的任何静态搜索树渐近一样的伸展树。

字母树是具有额外约束顺序的霍夫曼树，或者等效地搜索具有所有元素存储在叶子中的修改的树。存在用于最佳字母二叉树（OABT）的更快算法。。

1. The notion of an average BST is made precise as follows. Let a random BST be one built using only insertions out of a sequence of unique elements in random order (all permutations equally likely); then the expected height of the tree is O(log n). If deletions are allowed as well as insertions, "little is known about the average height of a binary search tree".^[1]