3.2.34

上次更新:2019-10-08
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

其实就是将所有的结点按照中序序列排成了一个双向链表,对树进行修改时要同时更新这个双向链表。

当插入新结点时,插到左侧的结点会变为父结点的新前驱,同理右侧会变为新后继。
注意要更新父结点原来的前驱和后继结点(如果有)。

删除结点时较为简单,只要更新需要删除结点的前驱和后继结点即可。

原本操作 leftright 的代码不需要更改,只需要加上对 prevnext 做操作的代码即可。

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;
}

另请参阅

BinarySearchTree 库

上一题 下一题