使用 C# 编程释放二叉搜索树的潜力

╰+哭是因爲堅強的太久メ 2023-09-26 21:47 108阅读 0赞

处理大量数据时，排序可能会花费大量时间。如果不是每次都对数据进行排序，而是直接将它们写入内存中已排序的正确位置，那就太好了。这将使我们能够始终提前知道在哪里搜索它们，例如，从中心开始。

我们会确切地知道去哪里；向左，丢弃右侧的一半数据，或向右，丢弃左侧的一半数据。这意味着每次搜索操作的元素数量将减半。这只会给我们带来快速的 对数复杂度。

但是如果我们真的想把它插入到正确的位置，它会很慢。毕竟，我们首先需要在内存中为所需数量的元素分配新的空间。然后把一部分旧数据复制到那里，然后放新数据，再把剩下的所有元素复制到新的位置。换句话说，我们得到了一个快速的搜索但很慢的插入。

在这种情况下，链表更合适。  
![在这里插入图片描述][e354a4ff8a464542931bf9c47fc0fd92.png]  
其中的插入确实在 O(1) 时间内立即发生，无需任何复制。然而，在我们这样做之前，我们将不得不遍历链表的大部分节点来找到插入的位置，这将再次导致我们的线性复杂度为O(N)。

为了使这些操作更快，发明了二叉搜索树。它是由节点组成的分层数据结构，每个节点存储数据，一个键值对，最多可以有两个孩子。

![在这里插入图片描述][7ebda9c983604f7dbe2190fb6e7e9007.png]  
在简单的二叉树中，数据可以按任意顺序存储。然而，在二叉搜索树中，只能根据允许上述操作快速进行的特殊规则添加数据。

为了理解这些规则，让我们首先为这棵树及其节点创建一个基础。

C＃  
1个  
公共 类 BinarySearchTree < T > 其中 T : IComparable < T >  
2个  
\{  
3个  
私人 节点？ \_头；  
4个  
的  
5个  
私有 类 节点  
6个  
\{  
7  
公共 只读 T 值；  
8个  
私人 节点？ \_左；  
9  
私人 节点？ \_对了；  
10  
的  
11  
公共 节点（T 值）  
12  
\{  
13  
价值 = 价值；  
14  
\}  
15  
\}  
16  
\}

插入新值  
那么，让我们来实现一个新值的插入。首先，如果根最初不存在，即树完全是空的，我们简单地添加一个新节点，它成为根。接下来，如果添加的新元素小于我们所在的当前节点，我们递归地向左移动。如果它大于或等于当前节点，我们递归地向右移动。

当我们找到child的parent为NULL的地方，也就是指向NULL的时候，我们就进行插入。

C＃  
1个  
公共 类 BinarySearchTree < T > 其中 T : IComparable < T >  
2个  
\{  
3个  
…  
4个  
的  
5个  
public void 添加（T 值）  
6个  
\{  
7  
如果（\_head 为 空ÿ

[e354a4ff8a464542931bf9c47fc0fd92.png]: https://img-blog.csdnimg.cn/e354a4ff8a464542931bf9c47fc0fd92.png
[7ebda9c983604f7dbe2190fb6e7e9007.png]: https://img-blog.csdnimg.cn/7ebda9c983604f7dbe2190fb6e7e9007.png