BST(4.1) - 惰性替罪羊树（LSG）

Algorithm

January 29, 2023

基本概念

替罪羊树 的基本概念前文已经介绍过，这里主要做两个变化，一个是增加 size 字段来省略动态计算 size 的时间，另一个是使用惰性删除。

由于重构的存在，替罪羊树本来就很适合使用惰性删除的方法。

基础定义

共同结构

def_tree!(
    /// Lazy Scapegoat Tree
    LSG
    {
        cnt: usize,
        /// nodes count including marked
        max_cnt: usize,
        alpha: f32
    }
);
impl_tree_debug!(LSG);

impl_node!();
impl_node_!({ size: usize, deleted: bool });
impl_balance_validation!(LSG ->
    #[cfg(test)]
    fn balance_validation(&mut self) {
        self.root.validate_balance(self.alpha);
    }
);

搜/插/删时的小变化

搜索

惰性搜索，如果找出的节点已被删除标记，那么仍然返回 None 。

插入

惰性插入，当节点已存在时，用插入的节点的值替换既有节点的值（实现上注意手动管理内存的问题），如果节点已被标记删除，还要取消标记，并且给当前数量节点数 +1 。

删除

惰性删除，删除节点时返回值，标记删除，但仍然保留节点（实现上注意手动管理内存的问题）。

重平衡

重构

重构的时候清除被标记删除的节点

// impl LSG

fn rebuild_at(&mut self, p: Node<K, V>) -> Node<K, V> {
    let mut part_nodes: Vec<Node<K, V>> = vec![];
    let mut dead_nodes = 0;

    for x in bst_flatten!(p) {
        if !deleted!(x) {
            part_nodes.push(x);
        }
        else {
            dead_nodes += 1;
        }
    }
    self.max_cnt -= dead_nodes;

    bst_build!(&part_nodes[..])
}

// ...

插入重平衡

impl_flatten_cleanup!(
    fn flatten_cleanup(&self) {
        if self.is_some() {
            size!(self, 1)
        }
    }
);
impl_build_cleanup!(
    fn build_cleanup(&self) {
        self.update_size()
    }
);


// impl Node

fn update_size(&self) {
    if self.is_some() {
        size!(
            self,
            1 + left!(self).size() + right!(self).size()
        );
    }
}

// ...


// impl LSG

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

    while pp.is_some() {
        pp.update_size();

        let p_dir = index_of_child!(pp, p);
        let sib = child!(pp, p_dir.rev());

        let size_max = std::cmp::max(sib.size(), p.size());

        if size_max as f32 / pp.size() as f32 > self.alpha {
            p = self.rebuild_at(p);

            if pp.is_none() {
                self.root = p;
            }
            else {
				conn_child!(pp, p, p_dir);
            }

            break;
        }

        p = pp;
        pp = paren!(p).upgrade();
    }

}

// ...

总装

impl<K: Ord, V> LSG <K, V> {

    ////////////////////////////////////////////////////////////////////////////
    /// Public API

    pub fn new(alpha: f32) -> Self {
        assert!(alpha <= 1.0 && alpha >= 0.5, "bad alpha {alpha}");

        Self {
            root: Node::none(),
            alpha,
            cnt: 0,
            max_cnt: 0
        }
    }


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

        if x.is_some() {
            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!(lazy | self.root, k);

        if x.is_some() {
            Some(val_mut!(x))
        }
        else {
            None
        }
    }


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

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

        self.insert_retracing(z);

        popped
    }


    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
    where K: Borrow<Q> + Debug, Q: Ord + ?Sized, V: Debug
    {

        let z = bst_search!(lazy | self.root, k);

        if z.is_none() {
            None
        }
        else {
            let popped = bst_delete!(lazy | z);
            self.cnt -= 1;

            if self.cnt as f32 * self.alpha <= self.max_cnt as f32 {
                self.root = self.rebuild_at(self.root.clone());
                self.max_cnt = self.cnt;
            }

            Some(popped)
        }
    }
}

省去了插入时巨慢的动态计算 size 的过程，但还是很慢，而且这样也不省内存了，真的是没什么用呐，替罪羊树。