BST(5) - 树堆（Treep）

Algorithm

February 02, 2023

基本概念

树堆的概念首次是由 Raimund Seidel and Cecilia R. Aragon 在 1989 年提出，它意思是节点用两个属性分别维护了二叉搜索树的性质和堆的性质。从二叉搜索树的角度看，可以类比前面的 Splay树，Splay 平衡性好要依赖于输入的数据具有随机性，而树堆干脆利用随机生成的权重来手动制造这种随机性。实质上都是通过随机化的输入来达到树结构的平衡。

基础定义

共同结构

def_attr_macro!(w);

impl_node!();
impl_node_!({ w: usize });
def_tree!(Treap { improve_search: bool });
impl_tree_debug!(Treap);

impl_rotate_cleanup!(Treap);

堆校验

impl_balance_validation!(Treap);

impl<K, V> Node<K, V> {
    /// Validate MaxHeap
    #[cfg(test)]
    fn balance_validation(&self) {
        let left = left!(self);
        let right = right!(self);

        if left.is_some() {
            debug_assert!(w!(self) >= w!(left));
            left.balance_validation();
        }

        if right.is_some() {
            debug_assert!(w!(self) >= w!(right));
            right.balance_validation();
        }
    }
}

基本操作

树堆基本操作有两种方式，就像讲到一般二叉搜索树的基础方法时，一种是展开型，一种是递归型。在常见的树堆的文章里介绍得是递归型的方法，依靠 Split 和 Join 这两个基础型方法（这两个方法本身也是递归实现的）。

我们这里介绍展开型的实现方法，而这种方法就像一般堆的实现一样，依赖 Sift-up 和 Sift-down 操作来维护堆修改后的性质，而这两个操作背后又通过树的旋转实现。树的旋转不仅保持了二叉搜索树的性质，也保留了既有的堆的权重大小关系。

Sift-up

把一个权重较大的节点试着向上提升，直到符合堆的性质。

// impl Treap

fn siftup(&mut self, x: Node<K, V>) {

    let mut p = paren!(x).upgrade();

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

// ...

Sift-down

把权重较小的节点向下沉，直到符合堆的性质。选择左右孩子中权重最大的那一个，把它旋转到根，如此反复直到堆的性质得到维护。

// impl Treap

/// rotate down if MaxHeap violation
fn siftdown(&mut self, x: Node<K, V>) {

    loop {
        let left = left!(x);
        let right = right!(x);

        let mut max_w = w!(x);
        let mut max_child = None;

        if left.is_some() && w!(left) > max_w {
            max_w = w!(left);
            max_child = Some(Left);
        }

        if right.is_some() && w!(right) > max_w {
            max_child = Some(Right);
        }

        if let Some(child_dir) = max_child {
            rotate!(self, x, child_dir.rev());
        }
        else {
            break;
        }

    }
}

// ...

搜索

和一般的二叉搜索树的搜索方法没什么不同。唯一特别的是两位原作者建议可以在搜索的时候给经常访问的节点更高的权重，来加快搜索效率。这样就结合了伸缩树的特点，但是没有那么直接，没有访问一次就直接提到根。我们实现这个做法是采用了 wiki 上建议，每次访问给一个随机数，当超过当前节点的权重时，就赋予这个权重然后 Sift-up 。

// impl Treap

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() {
        if self.improve_search {
            self.aragon_seidel_search_suggestion(x.clone());
        }

        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() {
        if self.improve_search {
            self.aragon_seidel_search_suggestion(x.clone());
        }

        Some(val_mut!(x))
    }
    else {
        None
    }
}


/// https://en.wikipedia.org/wiki/Treap
fn aragon_seidel_search_suggestion(&self, x: Node<K, V>) {
    let neww = random();

    if neww > w!(x) {
        w!(x, neww);
        mut_self!(self).siftup(x);
    }
}

// ...

插入

使用 Sift-up 修复新节点插入时可能造成的对堆的性质的破坏

// impl Treap

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

    let popped = bst_insert!(self, z.clone());

    if popped.is_none() {
        self.siftup(z);
    }

    popped
}

// ...

删除

和标准的二叉搜索树的删除方法一致。有一点需要额外调整，就是当被删除的节点左右孩子都不为空的时候。这时候 y 与 y.left , y.right

的权重大小关系就不确定了，需要对 y 进行 Sift-down 操作。

// impl Treap

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 {
        if left!(z).is_none() {
            subtree_shift!(self, z, right!(z));
        } else if right!(z).is_none() {
            subtree_shift!(self, z, left!(z));
        } else {
            /* case-1       case-2

                    z            z
                    \            \
                    y            z.right
                                /
                                / (left-most)
                                y
                                \
                                y.right
                */

            let y = bst_successor!(z);

            if !right!(z).rc_eq(&y) {
                subtree_shift!(self, y, right!(y));
                conn_right!(y, right!(z));
            }
            subtree_shift!(self, z, y);
            conn_left!(y, left!(z));

            /* Only y and y.left and maybe y.right violate weight */
            self.siftdown(y);
        }

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

// ...

创建

/// impl Treap

pub fn new() -> Self {
    Self {
        root: Node::none(),
        improve_search: false
    }
}

pub fn improve_search(mut self) -> Self {
    self.improve_search = true;
    self
}

// ...

总结

树堆是一个相对来讲容易理解，实现简单（相对红黑树家族），性能表现令人满意的二叉搜索树的数据结构。