二叉查找树

在文章《常用数据结构及复杂度》中，介绍了一些计算机程序设计中常用的线性数据结构，包括 Array、ArrayList、LinkedList、List、Stack、Queue、Hashtable 和 Dictionary 等。并简单介绍了这些数据结构的内部实现原理和常用操作的运算复杂度，以及如何选择合适的数据结构。本篇文章中，我们将介绍常见的树形结构及其常用操作的运算复杂度。

• 二叉树（Binary Tree）
  • 完全二叉树和满二叉树
• 二叉查找树（Binary Search Tree）
  • 插入节点
  • 删除节点
  • 遍历节点

我们知道像家谱族谱、公司组织结构等都是以树结构的形式组织数据。例如下图中所展示的公司组织结构图。

树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）。子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方。树的根（Root）指的是一个没有父节点的单独的节点。

所有的树都呈现了一些共有的性质：

1. 只有一个根节点；
2. 除了根节点，所有节点都有且只有一个父节点；
3. 无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径。（正是前两个性质保证了无环的成立。）

树中使用的术语

• 根（Root）：树中最顶端的节点，根没有父节点。
• 子节点（Child）：节点所拥有子树的根节点称为该节点的子节点。
• 父节点（Parent）：如果节点拥有子节点，则该节点为子节点的父节点。
• 兄弟节点（Sibling）：与节点拥有相同父节点的节点。
• 子孙节点（Descendant）：节点向下路径上可达的节点。
• 叶节点（Leaf）：没有子节点的节点。
• 内节点（Internal Node）：至少有一个子节点的节点。
• 度（Degree）：节点拥有子树的数量。
• 边（Edge）：两个节点中间的链接。
• 路径（Path）：从节点到子孙节点过程中的边和节点所组成的序列。
• 层级（Level）：根为 Level 0 层，根的子节点为 Level 1 层，以此类推。
• 高度（Height）/深度（Depth）：树中层的数量。比如只有 Level 0,Level 1,Level 2 则高度为 3。

实现 BinaryTree 类。在《你曾实现过二叉树吗》一文中，实现了一个基于泛型的简单的二叉树模型。

我们已经了解了数组是将元素连续地排列在内存当中，而二叉树却不是采用连续的内存存放。实际上，通常 BinaryTree 类的实例仅包含根节点（Root Node）实例的引用，而根节点实例又分别指向它的左右孩子节点实例，以此类推。所以关键的不同之处在于，组成二叉树的节点对象实例可以分散到 CLR 托管堆中的任何位置，它们没有必要像数组元素那样连续的存放。

如果要访问二叉树中的某一个节点，通常需要逐个遍历二叉树中的节点，来定位那个节点。它不象数组那样能对指定的节点进行直接的访问。所以查找二叉树的渐进时间是线性的 O(n)，在最坏的情况下需要查找树中所有的节点。也就是说，随着二叉树节点数量增加时，查找任一节点的步骤数量也将相应地增加。

那么，如果一个二叉树的查找时间是线性的，定位时间也是线性的，那相比数组来说到底哪里有优势呢？毕竟数组的查找时间虽然是线性 O(n)，但定位时间却是常量 O(1) 啊？的确是这样，通常来说普通的二叉树确实不能提供比数组更好的性能。然而，如果我们按照一定的规则来组织排列二叉树中的元素时，就可以很大程度地改善查询时间和定位时间。

算法复杂度分析》中有一些关于时间复杂度的描述。可知，log-₂n = y，相当于 2^y = n。即，如果节点数量增加 n，查找时间只缓慢地增加到 log-₂n。下图中显示了 O(log-₂n) 和线性增长 O(n) 的增长率之间的区别。时间复杂度为 O(log-₂n) 的算法运行时间为下面那条线。

从上图可以看出，O(log-₂n) 曲线几乎是水平的，随着 n 值的增加，曲线增长十分缓慢。举例来说，查找一个具有 1000 个元素的数组，需要查询 1000 个元素，而查找一个具有 1000 个元素的 BST 树，仅需查询不到10 个节点（log₂1024 = 10）。

而实际上，对于 BST 查找算法来说，其十分依赖于树中节点的拓扑结构，也就是节点间的布局关系。下图描绘了一个节点插入顺序为 20, 50, 90, 150, 175, 200 的 BST 树。这些节点是按照递升顺序被插入的，结果就是这棵树没有广度（Breadth）可言。也就是说，它的拓扑结构其实就是将节点排布在一条线上，而不是以扇形结构散开，所以查找时间也为 O(n)。

当 BST 树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到亚线性的运行时间 O(log₂n)。因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构像上图中的样子时，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点。也就是说，在这种情况下，在 BST 中查找节点与在数组（Array）中查找就基本类似了。

因此，BST 算法查找时间依赖于树的拓扑结构。最佳情况是 O(log-₂n)，而最坏情况是 O(n)。

An Extensive Examination of Data Structures Using C# 2.0

考察数据结构 - 第三部分：二叉树和BSTs[译]

Red–black tree

Red/Black Tree Algorithm Visualization

Left-Leaning Red-Black Trees

Red-Black Trees

Introduction to Algorithms ： LECTURE 10 Balanced Search Trees 

教你透彻了解红黑树

本文《二叉查找树》由 Dennis Gao 发表自博客园博客，任何未经作者本人允许的人为或爬虫转载均为耍流氓。