用 C# 编写的简单二叉搜索树

• 下载演示和源文件 - 27.1 KB

引言

在计算机科学中，二叉树是一种节点层次结构，每个节点最多引用两个子节点。每个二叉树都有一个根节点，从中衍生出前两个子节点。如果一个节点没有子节点，那么这些节点通常被称为叶子，并标志着树结构的范围。

一种特殊的二叉树，称为二叉搜索树，对于存储数据以便快速访问、存储和删除非常有用。二叉搜索树中的数据存储在树节点中，并且必须具有相关的序数值或键；这些键用于构造树，使得左子节点的值小于父节点的值，右子节点的值大于父节点的值。有时，键和数据是同一个。典型的键值包括简单的整数或字符串，键的实际数据将取决于应用程序。在本文中，我将描述一个存储字符串/双精度浮点数对的二叉搜索树。也就是说，键是字符串值，与键关联的数据是双精度浮点数值。开发人员可以使用字符串值搜索树。

背景

可以对二叉搜索树执行许多基本操作，最明显的包括插入、搜索和删除。

要将新节点插入到树中，可以使用以下方法。我们首先从树的根节点开始，并将根节点的序数值与要插入节点的序数值进行比较。如果序数值相同，则表示存在重复项，我们返回给调用方指示。如果序数值小于根节点，则我们沿着根节点的左分支，否则我们沿着右分支。我们现在再次开始比较，但在我们采取的分支处，将子节点的序数值与要插入的节点进行比较。树的遍历以这种方式继续，直到我们到达一个为空且无法再继续的左节点或右节点。此时，我们将新节点插入到此空位置。请注意，新节点总是作为叶子插入到树中，严格来说，节点是追加而不是插入。

搜索二叉搜索树几乎与插入新节点相同，只是当我们找到要查找的节点时停止遍历（在插入过程中，这将表示树中存在重复节点）。如果未找到节点，则我们向调用方报告此情况。

插入和搜索都是天然的递归操作，可以说，当考虑到它们的单元操作时，更容易理解。基本的递归搜索算法将如下所示

    node search (node, key) {
       if node is null then return null;
       
       if node.key = key then
          return node
          
       if key < node then
          return search (node.left, key);
       else
          return search (node.right, key);

在本文提供的源代码中，插入是递归实现的，而搜索使用迭代方法。

删除有点复杂，但归结为三个规则。这三个规则指的是删除没有子节点的节点、带有一个子节点的节点和带有两个子节点的节点。如果一个节点没有子节点，则该节点被简单地删除。如果该节点带有一个子节点，则该节点被删除，并且子节点被移到前面以链接到父节点。当一个节点带有两个子节点时，复杂性就出现了。然而，即使在这里，当说明规则时，它们也是直接的。要删除带有两个子节点的节点，右分支上的下一个序数节点（称为后续节点）用于替换被删除的节点。然后删除后续节点。后续节点将始终是右分支上最左边的节点（同样，前驱节点将是左分支上最右边的节点）。下图说明了删除规则。

使用二叉搜索树的常见替代方法是使用哈希表。哈希表具有更好的搜索和插入性能指标。理论上，在哈希表中插入或搜索项目所需的时间与存储的数据项数量无关。相比之下，二叉搜索树的缩放比例为 log (N)，其中 N 是数据项的数量（仍然远优于线性搜索）。.NET 库包含对哈希表的显式支持。

平衡树

在树中插入或搜索特定项目所需的时间将受到树深度的影响。深度树搜索时间更长，并且插入到树中的顺序会影响树的形状。随机插入顺序通常会产生比有序插入更茂密、因此更浅的树。茂密的树通常被称为平衡树，虽然此处未实现，但平衡树是二叉搜索树实现中非常理想的特性。某些算法（例如红黑树）在构建树时会自动平衡（请参阅红黑树动画）。下图显示了由三个相同数据集生成但以不同顺序插入的三棵树。第一个是最平衡的，因此是三个示例中最浅的。

使用递归方法实现搜索和插入方法可能会导致性能不佳，特别是当树不平衡时。

Using the Code

使用本文提供的源代码非常简单。以下代码说明了新二叉树的实例化、数据插入到树中以及随后的检索。insert() 方法用于插入新数据，findSymbol() 方法用于定位和检索数据。如果 findSymbol() 未能找到数据项，它将返回 null。如果成功，findSymbol() 将返回一个 TTreeNode 对象，该对象具有两个属性：name 和 value。以下代码说明了如何使用二叉搜索树。二叉树的类名是 TBinarySTree，各个节点的类类型是 TTreeNode。

// Create a new binary tree
bt = new TBinarySTree();

// Insert data
bt.insert ("Canis Minoris", 5.37);
bt.insert ("Gamma Cancri", 4.66);
bt.insert ("Phi Centauri", 3.83);
bt.insert ("Kappa Tauri", 4.21);
 
// Retrieve data  
TTreeNode symbol = bt.findSymbol ("Phi Centauri");
if (symbol != null)
   Console.WriteLine ("Star {1} has magnitude = {0}", symbol.name, symbol.value);

其他感兴趣的方法包括

bt.clear();
bt.count();

count 返回树中节点的数量。

bt.delete (key);

delete 将删除具有给定键的节点。如果该方法未能找到该节点，该方法将抛出一个简单异常。

源代码根据 BSD 许可证授权。源代码应在 C# 2.0 上编译。

要使用源代码，请解压源代码，加载二叉树解决方案 (binaryTree.sln) 并编译 BinaryTree 项目。在您自己的项目中，将其作为对 BinaryTree.dll 的引用。此版本是使用 Visual Studio 2003 编写的。

关注点

以下图表比较了二叉树搜索与 .NET 内置的 Hashtable 类的性能。随着存储数据项数量的增加，实现遵循预期的缩放定律。X 轴表示存储的数据项数量，范围从 1000 到 1,000,000 项（总共 21 个间隔）。Y 轴表示检索一个数据项所需的平均时间（平均 20,000 次检索尝试）。Hashtable 大致遵循 O(1)，即检索数据所需的时间与存储的数据项数量无关。相比之下，二叉搜索树大致遵循 O(log (N))。然而，这远优于线性搜索，线性搜索将按 O(N) 缩放；也就是说，存储项目数量翻倍会使检索单个数据项的平均时间翻倍。左侧的图表显示了在对数轴上绘制的数据。

时间是使用 QueryPerformanceCounter() 方法计算的。计时代码来源于Tobi+C#=T#。

其他可能性

应该将这里概述的实现视为最小的实际实现。此实现源自的项目不需要任何进一步的复杂性。但是，有许多领域可以显着改进。特别是，两个领域值得进一步研究

1. 当前的实现专门用于存储名称/值对。理想情况下，人们会更喜欢一个更通用的实现，开发人员可以使用他们自己的对象类型。
2. 如果树变得严重不平衡，该实现在面对大数据集时可能会出现性能下降。理想情况下，可以实现红黑变体以避免此问题（有关详细信息，请参阅文章末尾的参考 1）。

其他次要更改包括使用属性代替 public 方法 count，添加更多实用方法，以及更改类和方法的命名约定，使其与 .NET 更一致。

历史

1. 修复了第三棵树图 3 中的一个小错误（缺少 C 节点）。
2. CodeProject 上有一篇较旧的文章讨论了 C# 中的红黑树，我本应该早点发现（C# 中的红黑树）。

参考文献

关于使用 .NET 1.1 的二叉搜索树的资料似乎很少；以下内容，特别是第一个链接，提供了与 .NET 2.0 相关的内容。

1. 使用 C# 2.0 对二叉搜索树的考察.
2. C5 是一个适用于 C# 的 .NET 2.0 泛型集合类库.
3. 一个数据结构集合，包括二叉搜索树.