沉思录

种一棵树最好的时间是十年前，其次是现在。

二叉查找树

在线性的链表数据结构中，如果我们要查找某个数据，只能逐个遍历，这无疑效率会很差。同链表一样，二叉树节点间的关系也是通过指针建立的，现在我们给二叉树加入一些规则：

  1. 左子节点小于父节点。
  2. 右子节点大于或等于父节点。

满足这些条件的二叉树称为二叉查找树（Binary Search Tree，BST），一棵平衡的二叉查找树插入和查找性能可以达到 $O(log \ n)$ ，虽然没有有序数组 $O(1)$ 的查找性能，但也不像数组那样插入和删除节点需要挪动数据影响性能。当然也远优于链表 $O(n)$ 的插入和查找性能。

一棵二叉查找树

[!NOTE] 注意

如果允许在二叉查找树中出现值相等的节点，这些相等的节点可以选择放在左子树或右子树，不管选择放在哪边，后续必需遵循这个规则。

查找节点

现在我们就来看看二叉查找树查找节点的过程，看它是如何达到 $O(log \ n)$ 性能的。

查找过程如果不指定节点，通常是从根节点开始。先将要查找的值跟当前节点比较，如果小于当前节点则继续从左子树中查找（因为左子节点小于父节点），如果大于当前节点则继续从右子树中查找（右子节点大于或等于父节点）。这个过程与数组的二分查找类似。如果等于当前节点或者当前节点是叶结点，那么查找过程结束。

以下图为例：

查找节点过程

假设要查找值为62的节点。首先和根节点80比较，62较小，所以要找的结果可能在当前节点的左子树；左子节点的值是40，小于62，继续查看右子节点；70比62大，继续找左子结点，这个节点的值是62，正是我们要找的节点。

如果一棵二叉树每一层都尽可能满，那么它的高度是 $log \ n$，查找节点性能就是 $O(log \ n)$。

最大值和最小值

根据二叉查找树的特点，最大值节点一定在最右边，最小值的节点一定在最左边。要找到最大值，沿着根节点从右侧边缘一直走，直到不再有右子节点，那么当前节点就是最大值的节点；同理，只要沿左侧一直走到尽头，便是最小值节点。最大值和最小值节点未必是叶结点。

最大节点和最小节点

插入节点

想要为二叉查找树插入节点，必需保持节点的关系，在添加新节点之后，这棵树必需仍然满足二叉查找树的特性。

插入新节点首先需要找到合适的地方，先执行查找操作，找到合适的位置后，将新节点作为叶结点添加到树中。如果树为空则直接作为根节点。

下图中，将4插入已有的二叉查找树中，先从根节点开始查找，直至找到适合作为叶结点的位置。

插入节点

删除节点

与添加新节点一样，从二叉查找树中删除节点后，必需确保它仍是一棵二叉查找树。

删除节点会复杂些，有以下三种情形需要考虑：

如果是叶子节点

这种情形最简单，删除叶结点只需要断开与父节点的连接，把叶节点直接删掉，由于它没有子节点，后续也不存在需要处理的节点。

直接删除叶结点

如果只有一个子节点

如果要删除的节点只有一个子节点（或子树），删除节点后，把子节点提升，替换原来的位置，即让父节点重新指向子节点。这样依然满足二叉查找树的特性。

删除节点5并提升结点4作替代

如果有两个子节点

如果要删除的节点有两个子节点，这种情形会复杂些。在删除节点后，两个子节点需要有新的归宿。根据二叉查找树的特点可知，左子树的最大节点一定小于当前节点，而右子树的最小节点一定大于或等于当前节点。对于任一节点来说，如果用左子树的最大节点或右子树的最小节点的值(或称为元素)替换当前节点的值，这棵二叉树仍然满足二叉查找树的特性。

因此，如果删除的节点有两个子节点，我们可以用它左子树中最大节点或者右子树的最小节点值作为替换，然后删掉子树中用作替换的节点。于是，删除有两个子节点的节点的问题可以简化为删除叶结点或只有一个子节点的情形。

  • 替换节点是叶结点： 下图中删除节点 4，用左子树的最大节点值替换它，整个删除操作被简化成了删除一个叶结点。

替换节点是叶结点

  • 替换节点不是叶结点： 下图用右子树的最小节点替换，但替换节点不是叶结点。用最小子节点替换后，其实问题已经变成了只有一个子节点的情形，只需要按照上面的方式操作即可。

替换节点不是叶结点

[!TIP] 提示

作为替换的节点不可能有两个子节点，因为它既不是最大值也不是最小值。

如果觉得上面处理删除节点的方法过于复杂，其实还有一种简单的解决办法。对于要删除的节点，我们可以给它添加一个标记，表示它已经无效了。在删除操作不多的情况下，这么做还是挺有用的。但是如果删除操作有很多，这么做的话会拖累整棵树的查找效率。

清晰明白二叉查找树的原理之后，不难用代码实现它：

use std::cmp::Ordering;
use std::fmt::Debug;

struct Node<T> {
    v: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn from(v: T) -> Self {
        Self {
            v,
            left: None,
            right: None,
        }
    }
}

struct BinarySearchTree<T: Ord> {
    root: Option<Box<Node<T>>>,
}

impl<T: Ord + Debug> BinarySearchTree<T> {

    /// 查找节点
    fn find(&self, v: &T) -> Option<&Box<Node<T>>> {
        let mut node = self.root.as_ref();
        while node.is_some() && &node.unwrap().v != v {
            if v < &node.unwrap().v { // 走左边子节点
                node = node.unwrap().left.as_ref();
            } else { // 走右边子节点
                node = node.unwrap().right.as_ref();
            }
        }
        node
    }

    /// 插入节点
    fn insert(&mut self, v: T) {
        if self.root.is_none() {
            self.root.insert(Box::new(Node::from(v)));
            return;
        }

        let mut current = self.root.as_mut().unwrap();
        loop {
            if &v <= &current.v { // 走左边
                if current.left.is_none() {
                    current.left.replace(Box::new(Node::from(v)));
                    return;
                }
                current = current.left.as_mut().unwrap();
            } else { // 走右边
                if current.right.is_none() {
                    current.right.replace(Box::new(Node::from(v)));
                    return;
                }
                current = current.right.as_mut().unwrap();
            }
        }
    }

    /// 删除节点
    fn delete(&mut self, v: &T) {
        let mut current = &mut self.root;
        while let Some(node) = current {
            match v.cmp(&node.v) {
                Ordering::Less => current = &mut current.as_mut().unwrap().left,
                Ordering::Greater => current = &mut current.as_mut().unwrap().right,
                Ordering::Equal => {
                    match (node.left.as_mut(), node.right.as_mut()) {
                        (None, None) => *current = None,
                        (Some(_), None) => *current = node.left.take(),
                        (None, Some(_)) => *current = node.right.take(),
                        (Some(_), Some(_)) => current.as_mut().unwrap().v =
                            Self::take_min(&mut node.right).unwrap().v
                            // current.as_mut().unwrap().v = Self::take_max(&mut node.left).unwrap().v
                    }
                }
            }
        }
    }

    fn take_min(node: &mut Option<Box<Node<T>>>) -> Option<Box<Node<T>>> {
        let mut current = node;
        while let Some(node) = current {
            current = &mut current.as_mut().unwrap().left;
        }
        current.take()
    }

    fn take_max(&mut self, node: &mut Option<Box<Node<T>>>) -> Option<Box<Node<T>>> {
        let mut current = node;
        while let Some(node) = current {
            current = &mut current.as_mut().unwrap().right;
        }
        current.take()
    }
}

性能问题

二叉查找树不管是添增节点还是删除节点，都需要先执行查找操作，查找操作执行完之后，后续的添加和删除的时间复杂度都是常数级 $O(1)$，因此，决定二叉查找树性能的是查找性能。

在一棵满二叉树中，最底层的节点比树的其它节点总数多1，也就是说，满树中大约有一半的节点在最底层，大约有四分之一的操作在倒数第二层，依此类推。因此，查找、插入和删除节点的操作大约有一半都需要找到最底层节点，只有大约四分之一在倒数第二层，依此类推。

查找操作需要从上到下逐层查找，每层都需要访问一个节点，所需的访问次数取决于这个节点所在的层数。节点所在层数越浅，所需步骤越少；层数越深，所需步骤就越多。换句话说，决定二叉查找树性能的，是这棵树的高度。树越矮性能越好，反之越差。从根往下，只有每一层的节点都尽可能多，这棵树才会尽可能满，也才会尽可能矮。

如果一棵二叉树查找树尽可能满，它的高度就是 $log \ n$（准确的高度是 $log \ n + 1$），查找节点的时间复杂度也就是 $O(log \ n)$。

但是，随着二叉查找树不断添加和删除节点，有些子树会很茂盛，有些会很残缺，树会变得很不平衡。在添加有序节点时，二叉查找树甚至会退化成链表。

二叉查找树添加有序数列退化成链表

因此，要维持二叉查找树的效率，在增加和删除节点时，必须限制左右子树的高度差，让树维持平衡，这类树称为平衡查找树（Balanced Search Tree），我们将会在下一篇文章中讨论 AVL树，看它是如何维持二叉查找树平衡的。

版权声明： 本文为原创内容，未经许可，不得转载。