[知识点]平衡树之Splay

简介

Splay是一种自适应的平衡树，它能够在O(logN)的时间复杂度内完成插入、删除和查找操作。它的最大优点在于它的代码实现简单，易于理解和调试。

基本操作

Splay树的基本操作包括三种：Access、Split和Join。

Access

Access操作可以让我们把一个节点旋转到根节点位置，这项操作通常在树上进行路径压缩时使用。让我们来看看Access操作的实现：

def access(v):
    splay(v)
    if v.right:
        v.right.parent = None
        v.right = None
    while v.left:
        w = v.left
        v.left = w.right
        if w.right:
            w.right.parent = v
        w.right = v
        v.parent = w
        update(v)
        v = w
    splay(v)

这段代码的核心部分是将节点v旋转到根节点位置。为此，我们需要不断地将v的父节点转换成v的右儿子，以此将v旋转上去。这段代码的时间复杂度为O(logN)。

Split

Split操作可以将Splay树从v处分成两半。我们需要把v旋转到根节点位置，这样它的左子树就是我们要分出来的一半。然后将v的左子树赋值为空，这样我们就分出了两个新的Splay树。

下面是Split操作的代码实现：

def split(v):
    access(v)
    if not v.left:
        return None, v
    u = v.left
    while u.right:
        u = u.right
    splay(u)
    v.left = None
    u.parent = None
    update(v)
    return u, v

这段代码首先将v旋转到根节点位置，然后返回它的左子树和右子树。下面我们需要找到v的左子树中最右边的节点u，将它旋转到根节点位置，并且从树中移除它和它的父节点之间的边。这样我们就得到了两棵新的Splay树。这段代码的时间复杂度为O(logN)。

Join

Join操作是Split操作的逆操作。它接受两棵Splay树u和v作为输入，然后将它们合并成一棵新的Splay树。

def join(u, v):
    if u is None:
        return v
    if v is None:
        return u
    while u.right:
        u = u.right
    splay(u)
    u.right = v
    v.parent = u
    update(u)
    return u

Join操作的实现非常简单。首先我们需要找到u中最右边的节点x，将其旋转到根节点位置。然后将v赋值给x的右儿子，并且更新树的信息。这段代码的时间复杂度为O(logN)。

总结

Splay树是一种自适应的平衡树，它能够在O(logN)的时间复杂度内完成插入、删除和查找操作。Splay树的代码实现非常简单，易于调试和理解。Splay树在实际应用中广泛应用于各种问题中，比如图的连通性问题、路径问题、分治问题等。没学过平衡树的同学可以选择学习AVL树、红黑树等基本平衡树，再来学习Splay树。