BST(3) - 伸展树（Splay Tree）

Algorithm

January 30, 2023

基本概念

伸缩树（Splay Tree）是 Daniel Sleator and Robert Tarjan 在 1985 年提出，它的想法就是一个，把最近访问的节点 roll 到根节点。

它的性质与 CPU 缓存机制非常契合，又不需要存储额外字段，常用于缓存和垃圾回收器的实现。

但是这样的性质也导致

查询的时候也会修改自身的结构，而一般默认查询是个只读的操作，这可能会带来些范式上意想不到的麻烦；
这不是很“体面“的平衡方法，依赖于数据访问的有一定的随机性，顺序访问会造成数据结构蜕化为链表（前一个根节点总是成为当前根节点的右子树）

基础定义

共同结构

impl_node!();
impl_node_!({});
def_tree!(Splay {});
impl_tree_debug!(Splay);

基础操作

Splay

Splay树 最基础的操作当然就是 Splay 操作，就是把树中的一个节点旋转到根。

// impl Splay

fn splay(&mut self, x: &Node<K, V>)
{
    let mut p = paren!(x).upgrade();

    while p.is_some() {
        rotate!(self, p, index_of_child!(p, x).rev());
        p = paren!(x).upgrade();
    }
}

// ...

Split

给定树中一个节点 x ，把树分为比 x 小（包含 x ）和比 x 大的两部分。方法是把 x 旋转到根，然后分出 x 的右子树和 x 的其余部分。

需要注意的是分割的时候需要断开连接。

// impl Splay

fn split(&mut self, x: Node<K, V>) -> (Node<K, V>, Node<K, V>) {
    self.splay(&x);

    let x_right = right!(x);
    disconn!(x, x_right);

    (x.to_owned(), x_right)
}

// ...

Join

给两个节点，把节点代表的子树合并为一棵完整的树。能够合并前提是这两棵子树其中一棵的最大值小于另一棵的最小值，方法是把较小子树的最大值 splay （最大值节点的右子树为空），然后把另一棵较大的子树放到根节点的右子树位置。

// impl Splay

fn join(&mut self, trees: (Node<K, V>, Node<K, V>))
{
    let (s, l) = trees;

    if s.is_some() {
        let s_max = bst_maximum!(s);

        self.splay(&s_max);
        self.root = s_max.clone(); //  s maybe not root node
        conn_right!(s_max, l);
    }
    else {
        self.root = l;
    }
}

// ...

注意，对子树 Splay 的时候不会更新所属母树的根节点（左子树的根不一定是母树的根），需要手动保证树的根节点为左子树的根节点。

总装

搜索

找到节点后额外执行 Splay 操作。在 Rust 实现里，如 mut_self 这个宏所示，我们使用一个 tricky 的方法绕过可变性检查。

// impl Splay

/// Hack method convert self to self_mut
macro_rules! mut_self {
    ($self: ident) => {
         unsafe { &mut *($self as *const Self as *mut Self) }
    };
}


pub fn get<Q>(&self, k: &Q) -> Option<&V>
where K: Borrow<Q>, Q: Ord + ?Sized
{
    let x = bst_search!(self.root, k);

    if x.is_some() {
        mut_self!(self).splay(&x);
        Some(val!(x))
    }
    else {
        None
    }
}

pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
where K: Borrow<Q>, Q: Ord + ?Sized
{
    let x = bst_search!(self.root, k);

    if x.is_some() {
        mut_self!(self).splay(&x);
        Some(val_mut!(x))
    }
    else {
        None
    }
}

// ...

插入

我们这里的插入实现

// impl Splay

pub fn insert(&mut self, k: K, v: V) -> Option<V>
{
    let z = node!( BST { k, v });

    /* modify a little bst_insert */

    use std::cmp::Ordering::*;

    let mut y = Node::none();
    let mut x = self.root.clone();

    while !x.is_none() {
        y = x.clone();

        match key!(z).cmp(key!(x)) {
            Less => {
                x = left!(x);
            }
            Equal => {
                break;
            }
            Greater => {
                x = right!(x);
            }
        }
    }

    let mut popped = None;
    let mut splay_at = z.clone();

    if y.is_none() {
        self.root = z;
    } else {
        match key!(z).cmp(key!(y)) {
            Less => {
                conn_left!(y, z);
            }
            Equal => {
                popped = Some(y.replace_val(z));
                splay_at = y;
            },
            Greater => {
                conn_right!(y, z);
            }
        }
    }

    self.splay(&splay_at);

    popped
}

// ...

删除

找到搜索节点后，（如果节点存在）Split 该节点，此时左子树的根节点应该就是要被删除的节点，删掉之后，把左子树的左孩子（Split 得到的左子树的右孩子为空）和右子树 Join 。

// impl Splay

pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
where K: Borrow<Q> + Debug, Q: Ord + ?Sized, V: Debug
{
    let z = bst_search!(self.root, k);

    if z.is_none() {
        None
    }
    else {
        let (s, l) = self.split(z);

        let s_left = left!(s);
        disconn!(s, s_left);

        self.join((s_left, l));

        Some(unwrap_into!(s).into_value())
    }
}

// ...