跳转至

二叉树

简单二叉树的遍历

先序：(根左右)考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。

中序：(左根右)考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。

后序：(左右根)考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。

二叉查找树

二叉查找树（英语：Binary Search Tree），也称为 二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点。 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(\log n)O(logn)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望 O(log n)，最坏 O(n)（数列有序，树退化成线性表）。

虽然二叉查找树的最坏效率是 O(n)O(n)，但它支持动态查询，且有很多改进版的二叉查找树可以使树高为 O(log n)，从而将最坏效率降至 O(log n)，如 AVL 树、红黑树等。

二叉搜索树的有优点是，即便在最坏的情况下，也允许你在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。

通常来说，如果你想有序地存储数据或者需要同时执行搜索、插入、删除等多步操作，二叉搜索树这个数据结构是一个很好的选择。

自平衡二叉搜索树

支持插入，搜索，删除操作的动态数据结构——自平衡二叉搜索树

实际上，BST 操作的运行时间与树的高度（Height）是有关系的。一个树的高度指的是从树的根开始所能到达的最长的路径长度。树的高度可被递归性地定义为：

  • 如果节点没有子节点，则高度为 0；
  • 如果节点只有一个子节点，则高度为该子节点的高度加 1；
  • 如果节点有两个子节点，则高度为两个子节点中高度较高的加 1；

计算树的高度要从叶子节点开始，首先将叶子节点的高度置为 0，然后根据上面的规则向上计算父节点的高度。以此类推直到树中所有的节点高度都被标注后，则根节点的高度就是树的高度。

假设这棵树上节点总数为 n，一个平衡树能把高度维持在 h = log n。因此这棵树上支持在 O(h) = O(log n) 时间内完成 插入，搜索，删除 操作。

我们来讨论一下树的节点总数 N 和高度 h 之间的关系。对于一个平衡二叉搜索树, 我们已经在前文中提过，

但一个普通的二叉搜索树，在最坏的情况下，它可以退化成一个链。

因此，具有 N 个节点的二叉搜索树的高度在 logN 到 N 区间变化。也就是说，搜索操作的时间复杂度可以从 logN 变化到 N 。这是一个巨大的性能差异。

所以说，高度平衡的二叉搜索树对提高性能起着重要作用。

有许多不同的方法可以实现。尽管这些实现方法的细节有所不同，但他们有相同的目标:

采用的数据结构应该满足二分查找属性和高度平衡属性。 采用的数据结构应该支持二叉搜索树的基本操作，包括在 O(logN) 时间内的搜索、插入和删除，即使在最坏的情况下也是如此。 我们提供了一个常见的的高度平衡二叉树列表供您参考：

  • 红黑树
  • AVL树
  • 伸展树
  • 树堆

高度平衡的二叉搜索树在实际中被广泛使用，因为它可以在 O(logN) 时间复杂度内执行所有搜索、插入和删除操作。

高度平衡的二叉搜索树的实际应用

高度平衡的二叉搜索树在实际中被广泛使用，因为它可以在 O(logN) 时间复杂度内执行所有搜索、插入和删除操作。

平衡二叉搜索树的概念经常运用在 Set 和 Map 中。Set 和 Map 的原理相似。 我们将在下文中重点讨论 Set 这个数据结构。

Set（集合）是另一种数据结构，它可以存储大量 key（键）而不需要任何特定的顺序或任何重复的元素。 它应该支持的基本操作是将新元素插入到 Set 中，并检查元素是否存在于其中。

通常，有两种最广泛使用的集合：散列集合（Hash Set）和 树集合（Tree Set）。

树集合，Java 中的 Treeset 或者 C++ 中的 set ，是由高度平衡的二叉搜索树实现的。因此，搜索、插入和删除的时间复杂度都是 O(logN) 。

散列集合，Java 中的 HashSet 或者 C++ 中的 unordered_set ，是由哈希实现的，但是平衡二叉搜索树也起到了至关重要的作用。当存在具有相同哈希键的元素过多时，将花费 O(N) 时间复杂度来查找特定元素，其中N是具有相同哈希键的元素的数量。 通常情况下，使用高度平衡的二叉搜索树将把时间复杂度从 O(N) 改善到 O(logN) 。

哈希集和树集之间的本质区别在于树集中的键是有序的。