本文是我上一篇文章《用C#编程释放二进制搜索树的潜力》的直接延续，在这篇文章中，我介绍了二进制搜索树的基本方法的实现，如添加和删除元素。为了更好地和我一起理解代码，我建议你先阅读我之前的文章。
二叉树的整个概念仍然是一样的。唯一要增加的是在插入一个新节点或删除一个旧节点时对树进行平衡。我们的任务是确保每个子节点的高度之差在绝对值上总是小于或等于1。
这看起来很复杂，但实际上，单个节点的高度只是从其子节点到最低叶子的最长路径。因此，一个没有子节点的高度为0，而一个不存在的节点的高度为-1。
增加数值时更新节点高度
很明显，当添加和删除节点时，递归链中父节点的高度将发生变化。这意味着，在堆栈解开时，我们需要更新堆栈中每个节点的高度。这就是为什么递归算法在这里非常方便。
我们将为每个这样的节点更新高度，如下所示。我们将获取左、右两个子节点的高度。然后，我们将保留这两个中较大的一个，并在其上加一个。因此，节点的高度要么增加1，要么减少1。
应该理解的是，在插入过程中，只有当一个新的节点被添加到一个叶子上时，高度才会改变。因为如果一个节点已经有一个子节点，而另一个子节点被添加到它上面，高度不会因此而改变。
private class Node
{
...
private int _height;
...
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);
}
UpdateHeight();
}
...
private void UpdateHeight()
{
var maxHeight = Math.Max(
_left?._height ?? -1,
_right?._height ?? -1);
_height = maxHeight + 1;
}
}
左旋和右旋
在向树中添加新元素并重新计算栈中节点的高度后，我们需要确定我们的树是否保持平衡。
换句话说，这就是所谓的树的重载。它可以向左或向右过载。
过载的定义是：对于一个给定的节点，左右子树的高度差的绝对值大于1的情况。这将是平衡的信号。但符号会告诉我们树在哪个方向上过载。如果我们得到一个负值，这意味着左边的高度更大，所以我们向右平衡。如果我们得到一个正的差值，这意味着右边的高度更大，所以我们向左平衡。
平衡意味着我们必须将我们的树向左或向右旋转，同时保留节点的顺序。
从本质上讲，右旋转只是意味着，如果一开始，我们围绕着树旋转的节点指向它的左边的子节点，现在左边的子节点将从右边指向它的父节点，反之亦然。
重要的是要记住，可能有一个父节点从上面引用这个节点。因此，必须小心地改变链接，以免破坏任何东西。
此外，这两个节点也可能有子女。为了处理这个问题，我们将创建一个辅助方法，简单地交换这两个节点的键和值。
private class Node
{
...
private static void Swap(Node a, Node b)
{
(a.Value, b.Value) = (b.Value, a.Value);
}
}
最后要做的是更新这两个节点的高度，旋转后它们会发生变化。首先是下层的节点，然后是上层的节点。同样的逻辑也适用于向左旋转；只是所有的动作将被完全镜像。
private class Node
{
...
private void RotateToRight()
{
if (_left is null)
{
throw new InvalidOperationException(
"Could not rotate to the right.");
}
Swap(this, _left);
var formerRight = _right;
_right = _left;
_left = _right._left;
_right._left = _right._right;
_right._right = formerRight;
_right.UpdateHeight();
UpdateHeight();
}
private void RotateToLeft()
{
if (_right is null)
{
throw new InvalidOperationException(
"Could not rotate to the left.");
}
Swap(this, _right);
var formerLeft = _left;
_left = _right;
_right = _left._right;
_left._right = _left._left;
_left._left = formerLeft;
_left.UpdateHeight();
UpdateHeight();
}
}
右-左和左-右的旋转
一棵AVL树不仅可以有左和右的旋转，还可以有右-左和左-右的旋转。如果我们有一棵这样的树。
在这种情况下，我们还需要一个右-左旋转。在这种情况下，我们首先需要将树相对于中间的节点向右旋转，这将把我们带到我们刚刚讨论过的、已经知道如何操作的前一种情况。因此，我们现在将得到的树相对于上面的节点向左旋转，再次达到平衡。
同样的情况也适用于左右旋转，这只是之前的一个镜像。为了确定何时进行简单的右旋转或左旋转，我们需要检查子节点的平衡情况。如果树向左过载，我们就检查左边的孩子的平衡。如果树采取歪曲的形式，那么我们将得到数字1。因此，我们立即进行相对于节点一的左旋转，然后才进行右旋转。
如果我们的树有一个直的形状，节点1的平衡将是减一。因此，我们只需要进行一次右旋。
同样的逻辑也适用于向右的重载树。在这里，我们检查右侧子节点的平衡，如果它等于减一，这意味着树有一个之字形。因此，它需要先向右旋转，然后再向左旋转。
private class Node
{
...
public void Insert(T value)
{
...
UpdateHeight();
Balance();
}
...
private int GetOverload()
{
return (_right?._height ?? -1) - (_left?._height ?? -1);
}
private void Balance()
{
var overload = GetOverload();
if (overload == -2)
{
if (_left?.GetOverload() == 1)
{
_left.RotateToLeft();
}
RotateToRight();
}
else if (overload == 2)
{
if (_right?.GetOverload() == -1)
{
_right.RotateToRight();
}
RotateToLeft();
}
}
}
AVL树中的删除
AVL树中的删除与二进制搜索树中的删除工作方式完全相同。唯一的区别是，在每次删除之后，当我们在旋转过程中解开堆栈时，我们将更新节点的高度，并在必要时平衡它们。这不仅是针对被删除的节点，而且在有两个子节点的情况下，也会针对取代被删除节点的节点。因为它的删除可能再次改变父节点的高度。因此，我们需要递归地遍历每个这样的节点，直到被删除的节点，更新所有高度。
private class Node
{
...
public bool Remove(T value, out Node? root)
{
bool hasRemoved;
var comparison = value.CompareTo(Value);
if (comparison < 0)
{
root = this;
hasRemoved = _left?.Remove(value, out _left) ?? false;
}
else if (comparison > 0)
{
root = this;
hasRemoved = _right?.Remove(value, out _right) ?? false;
}
else if (_left is null || _right is null)
{
root = _left ?? _right;
hasRemoved = true;
}
else
{
var leftMax = _left.Max();
_left.Remove(leftMax.Value, out _left);
Value = leftMax.Value;
root = this;
hasRemoved = true;
}
root?.UpdateHeight();
root?.Balance();
return hasRemoved;
}
...
}
总结
因此，我们已经成功地将我们的树的复杂性降低到对数时间，但递归、沿递归路径不断更新节点高度、沿递归路径计算平衡系数以及沿递归路径执行多次旋转，都大大降低了整个算法的速度，特别是在大量数据的情况下。
为了克服这些限制，人们创造了另一种树，它被称为红黑树。这个名字来自于一个事实，即现在树中的每个节点都有一个颜色，要么是红色要么是黑色。
