数据排序和搜索的优化方法

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

我们会清楚地知道该往哪里走；往左走，丢掉右边一半的数据，或者往右走，丢掉左边一半的数据。这意味着，每次搜索操作的元素数量将减少一半。这给我们带来的只是快速对数的复杂性

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

在这种情况下，链表更适合。

它的插入真的是在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，这将再次让我们实现对数复杂度，而不管传入的数据如何。