在处理大量的数据时,排序会花费很多时间。如果我们不需要每次都对数据进行排序,而是直接将它们写到内存中的正确位置,在那里它们已经被排序了,那就太好了。这将使我们总是提前知道在哪里搜索它们,例如,从中心开始。
我们会清楚地知道该往哪里走;往左走,丢掉右边一半的数据,或者往右走,丢掉左边一半的数据。这意味着,每次搜索操作的元素数量将减少一半。这给我们带来的只是快速对数的复杂性
但如果我们真的想把它插入到正确的位置,工作起来会相当缓慢。毕竟,我们首先需要在内存中为所需数量的元素分配新的空间。然后把旧数据的一部分复制到那里,再把新数据放进去,再把所有剩余的元素复制到新的位置。换句话说,我们得到的是快速搜索但缓慢插入。
在这种情况下,链表更适合。
它的插入真的是在O(1)时间内即时发生的,不需要任何复制。然而,在这之前,我们必须通过链接列表的大部分节点来找到插入的地方,这将再次导致我们达到 O(N)的线性复杂性
为了快速操作,人们发明了二进制搜索树。它是一个由节点组成的 分层数据结构,每个节点都存储数据,是一个键值对,最多可以有两个孩子。
在一个简单的二进制树中,数据可以按任何顺序存储。然而,在二进制搜索树中,数据只能按照特殊的规则添加,使上述操作能够快速工作。
为了理解这些规则,首先让我们为这个树和它的节点建立一个基础。
public class BinarySearchTree<T> where T : IComparable<T>
{
private Node? _head;
private class Node
{
public readonly T Value;
private Node? _left;
private Node? _right;
public Node(T value)
{
Value = value;
}
}
}
插入一个新值
那么,让我们来实现一个新值的插入。首先,如果根最初不存在,也就是说,树是完全空的,我们只需添加一个新的节点,它就成为根。接下来,如果被添加的新元素小于我们当前所站的节点,我们就递归地向左移动。如果它大于或等于当前节点,我们就递归地向右移动。
当我们找到子节点的父节点是NULL的地方,也就是指向NULL的地方,我们就执行插入。
public class BinarySearchTree<T> where T : IComparable<T>
{
...
public void Add(T value)
{
if (_head is null)
{
_head = new Node(value);
}
else
{
_head.Insert(value);
}
}
...
}
private class Node
{
...
public void Insert(T value)
{
ref var branch = ref value.CompareTo(Value) < 0
? ref _left
: ref _right;
if (branch is null)
{
branch = new Node(value);
}
else
{
branch.Insert(value);
}
}
}
由于递归的存在,我们在寻找正确位置时遍历的所有元素都存储在一个堆栈中。一旦一个新的节点被添加,递归开始解开,我们将通过每个祖先节点上升,直到我们到达根。这个特点大大简化了未来的代码。因此,请牢记这一点。
如果我们继续以这种方式插入新元素,我们会注意到它们最终都会被排序。小的节点将总是在左边,而大的节点将总是在右边。得益于此,我们在插入新元素和搜索时总是能迅速找到正确的路径,而不影响树中的其他节点。
因此,现在我们在O(log(N))时间内进行搜索和插入。这也使我们能够快速找到树上的最小和最大元素。最小值将总是左边的最低元素,而最大值将是右边的最低元素。
因此,在第一种情况下,我们只是一直向左递归,直到碰到NULL。在第二种情况下,情况类似,但我们向右递减。重要的是要明白,这样的节点不能有一个以上的孩子。否则,它们就不会是最小或最大。
public class BinarySearchTree<T> where T : IComparable<T>
{
...
public T Min()
{
if (_head is null)
{
throw new InvalidOperationException("The tree is empty.");
}
return _head.Min().Value;
}
public T Max()
{
if (_head is null)
{
throw new InvalidOperationException("The tree is empty.");
}
return _head.Max().Value;
}
...
}
private class Node
{
...
public Node Min()
{
return _left is null ? this : _left.Min();
}
public Node Max()
{
return _right is null ? this : _right.Max();
}
}
项目搜索
我们将创建一个简单的搜索函数,根据其值在树中找到一个特定的节点。由于树的结构,搜索过程是相对直接的。如果当前节点包含给定的值,我们将返回它。如果被搜索的值小于当前节点的值,我们将在左侧子树中进行递归搜索。反之,如果搜索的值大于当前节点的值,我们将在右侧子树中寻找。如果我们到达一个空的子树,即它指向NULL,那么具有搜索值的节点就不存在。该算法与插入算法类似,我们将为树实现包含方法,为节点实现查找方法。
public class BinarySearchTree<T> where T : IComparable<T>
{
...
public bool Contains(T value)
{
return _head?.Find(value) is not null;
}
...
}
private class Node
{
...
public Node? Find(T value)
{
var comparison = value.CompareTo(Value);
if (comparison == 0)
{
return this;
}
return comparison < 0
? _left?.Find(value)
: _right?.Find(value);
}
}
删除值
现在,为了使我们的树在我们想从中删除一些元素时不会断裂,我们需要一些特殊的删除规则。首先,如果被删除的元素是一个叶子节点,那么我们只需用NULL替换它。
如果这个元素有一个子节点,那么我们不是用NULL而是用这个子节点来替换被删除的节点。
因此,在这两种情况下,删除可以简单地归结为用它的子节点替换被删除的节点,它可以是一个普通的现有节点,也可以是NULL。因此,我们只需检查父节点肯定没有两个子节点,然后用它的一个子节点覆盖被删除的节点,我再说一遍,这个子节点可能是一个现有的节点或者是NULL。
最后一种情况是,被删除的节点有两个孩子。在这种情况下,取代被删除节点的节点必须大于被删除节点的左子树上的所有节点,并且小于被删除节点的右子树上的所有节点。
因此,首先,我们需要找到左子树中最大的元素或右子树中最小的元素。找到之后,我们覆盖被删除节点的数据,并递归地删除移动到被删除节点位置的节点。它将按照同样的规则被删除:它要么被替换为NULL,要么被替换为它唯一的子节点。
public class BinarySearchTree<T> where T : IComparable<T>
{
...
public bool Remove(T value)
{
return _head?.Remove(value, out _head) ?? false;
}
...
}
private class Node
{
...
public bool Remove(T value, out Node? root)
{
var comparison = value.CompareTo(Value);
if (comparison < 0)
{
root = this;
return _left?.Remove(value, out _left) ?? false;
}
if (comparison > 0)
{
root = this;
return _right?.Remove(value, out _right) ?? false;
}
if (_left is null || _right is null)
{
root = _left ?? _right;
return true;
}
var leftMax = _left.Max();
_left.Remove(leftMax.Value, out _left);
Value = leftMax.Value;
root = this;
return true;
}
}
树的遍历
为了检查删除是否成功,以及所有节点的顺序是否被保留,有一个特殊的树形遍历方法,允许我们以升序输出所有节点。这种方法被称为顺序内遍历。它涉及到递归输出,首先是左边的子节点,然后是父节点,最后是右边的子节点。让我们使用内序遍历将树转换为一个普通的列表。
public class BinarySearchTree<T> where T : IComparable<T>
{
...
public List<T> ToList()
{
var list = new List<T>();
_head?.AddTo(list);
return list;
}
...
}
private class Node
{
...
public void AddTo(ICollection<T> list)
{
_left?.AddTo(list);
list.Add(Value);
_right?.AddTo(list);
}
}
现在我们有一个简单的方法来将树输出到控制台。让我们来做这件事,并确保删除工作正常。
var tree = new BinarySearchTree<int>();
tree.Add(50);
tree.Add(40);
tree.Add(30);
tree.Add(45);
tree.Add(35);
Print(tree.ToList());
tree.Remove(35);
tree.Remove(40);
Print(tree.ToList());
void Print(List<int> list)
{
foreach (var value in list)
{
Console.Write(value);
Console.Write(" ");
}
Console.WriteLine();
}
另一种类型的树形遍历被称为预排序遍历。它涉及到先输出父代,然后是左代,再是右代。例如,当在内存中复制一棵树时,这可能是有用的,因为我们按照它们在树中从上到下的完全相同的顺序遍历节点。
还有其他类型的二进制搜索树的遍历,但它们的实现差别不大。
结论
最后,我们有了一个可以快速完成一切的数据结构。让我们花点时间思考一下,创建一棵从元素1到5的树。如果每个后续节点总是大于或总是小于前一个节点,那么我们又得到了一个普通的链表,其操作复杂度为O(N)。
因此,我们的树被证明是完全无用的。幸运的是,人们很快就意识到了这一点,并想出了一种更先进的树,叫做自平衡的AVL,这将再次让我们实现对数复杂度,而不管传入的数据如何。