3.2.34 #
解答 #
其实就是将所有的结点按照中序序列排成了一个双向链表，对树进行修改时要同时更新这个双向链表。
当插入新结点时，插到左侧的结点会变为父结点的新前驱，同理右侧会变为新后继。
注意要更新父结点原来的前驱和后继结点（如果有）。
删除结点时较为简单，只要更新需要删除结点的前驱和后继结点即可。
原本操作 left 和 right 的代码不需要更改，只需要加上对 prev 和 next 做操作的代码即可。
Prev 方法实现如下（Next 类似），修改了内部的 Get 方法使之返回 Node 而非 TValue。
public TKey Prev(TKey key)
{
var node = Get(root, key);
if (node == null || node.Prev == null)
return null;
return node.Prev.Key;
}
代码 #
处理结点关系的几个方法。
private void DeleteNode(Node x)
{
if (x.Prev != null)
x.Prev.Next = x.Next;
if (x.Next != null)
x.Next.Prev = x.Prev;
}
private void InsertRight(Node parent, Node newNode)
{
parent.Right = newNode;
InsertBetween(parent, newNode, parent.Next);
}
private void InsertLeft(Node parent, Node newNode)
{
parent.Left = newNode;
InsertBetween(parent.Prev, newNode, parent);
}
private void InsertBetween(Node prev, Node newNode, Node next)
{
newNode.Prev = prev;
newNode.Next = next;
if (prev != null)
prev.Next = newNode;
if (next != null)
next.Prev = newNode;
}
Put 方法
protected virtual Node Put(Node x, TKey key, TValue value)
{
if (x == null)
{
return new Node(key, value, 1); // 树是空的。
}
var cmp = key.CompareTo(x.Key);
if (cmp < 0)
{
if (x.Left == null)
{
var newNode = new Node(key, value, 1);
InsertLeft(x, newNode);
}
else
{
x.Left = Put(x.Left, key, value);
}
}
else if (cmp > 0)
{
if (x.Right == null)
{
var newNode = new Node(key, value, 1);
InsertRight(x, newNode);
}
else
{
x.Right = Put(x.Right, key, value);
}
}
else
{
x.Value = value;
}
x.Size = 1 + Size(x.Left) + Size(x.Right);
return x;
}
Delete 方法
protected virtual Node Delete(Node x, TKey key)
{
if (x == null)
return null;
var cmp = key.CompareTo(x.Key);
if (cmp < 0)
x.Left = Delete(x.Left, key);
else if (cmp > 0)
x.Right = Delete(x.Right, key);
else
{
DeleteNode(x); // 在中序链表中删除结点。
if (x.Right == null)
return x.Left;
if (x.Left == null)
return x.Right;
var t = x;
x = Min(t.Right);
x.Right = DeleteMin(t.Right);
x.Left = t.Left;
}
x.Size = Size(x.Left) + Size(x.Right) + 1;
return x;
}
DeleteMin 方法，DeleteMax 类似。
protected virtual Node DeleteMin(Node x)
{
if (x.Left == null)
{
DeleteNode(x);
return x.Right;
}
x.Left = DeleteMin(x.Left);
x.Size = Size(x.Left) + Size(x.Right) + 1;
return x;
}