BST(4) - 替罪羊树（SG）

Algorithm

January 29, 2023

基本概念

替罪羊树（Scapegoat Tree）初始是在 1989 年由 Arne Andersson 发明，而在 1993 年 Igal Galperin and Ronald L. Rivest 正式提出这个概念。

它是说不用每次修改树结构后都进行重平衡的操作，而是当检测到树的不平衡程度达到阈值时直接重构以某个节点为根的树。

搜/插/删的平均时间复杂度与其他自平衡二叉搜索树一样，都是 $O(\text{log}\ \text{n})$ ，但是由于重构的存在，插/删的最坏时间复杂度为 $O(\text{n})$ 。

它使用一个 $\alpha$ 因子衡量平衡性，$ 0.5 \lt \alpha \lt 1$ ，最终维护一个宽松的 $\alpha\text{-height}$ 平衡。

基础定义

共同结构

impl_tree!(
    /// Scapegoat Tree
    SG
    {
        cnt: usize,
        /// nodes count including marked
        max_cnt: usize,
        alpha: f32
    }
);
impl_node!();
impl_node_!({});

平衡校验

impl_balance_validation!(
    SG ->
    fn balance_validation(&self) {}
);

由于不存在严格的平衡，就不进行平衡校验了。

重平衡

重构

impl_flatten_cleanup!();
impl_build_cleanup!();

/// impl SG

/// Rebuild at p, return new root
fn rebuild_at(&mut self, p: Node<K, V>) -> Node<K, V> {
    bst_build!(&bst_flatten!(p))
}

/// ...

插入重平衡

插入的时候，从插入的节点开始向上检查，找到第一个不平衡的节点，在该节点上进行重构。

\[\begin{array}{l} \texttt{size}\text{(left)} &\leqslant\ α*\texttt{size}\text{(node)}\\ \texttt{size}\text{(right)} &\leqslant\ α*\texttt{size}\text{(node)} \end{array}\]

impl<K, V> Node<K, V> {
    fn size(&self) -> usize {
        if self.is_some() {
            1 + left!(self).size() + right!(self).size()
        }
        else {
            0
        }
    }
}


// impl SG

fn insert_retracing(&mut self, ent: Node<K, V>)
{
    let mut p = ent;
    let mut size_self = 1;

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

    while pp.is_some() {
        let p_dir = index_of_child!(pp, p);

        let sib = child!(pp, p_dir.rev());
        let size_sib = sib.size();

        let size_max = max(size_self, size_sib);

        size_self += size_sib + 1;

        if size_max as f32 / size_self 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();
    }

}

// ...

删除重平衡

删除的时候，直接考虑最大节点数与现有节点数的关系。

\[\text{NodeCount} \leqslant α*\text{MaxNodeCount}\]

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

重构后需要重置最大节点数为当前结点数。

总装

impl<K: Ord, V> SG <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 insert(&mut self, k: K, v: V) -> Option<V>
    {
        let z = node!( BST { k, v });

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

        if popped.is_none() {
            self.cnt += 1;
            self.max_cnt = max(self.cnt, self.max_cnt);
        }

        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!(self.root, k);

        if z.is_none() {
            None
        }
        else {
            bst_delete!(self, z);
            self.cnt -= 1;

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

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

原始替罪羊树本身理论最坏时间复杂度不好，实际性能测试也不好，呃应该是相当相当差。

它的优势是保持平均的理论时间复杂度 $O(\text{log}\ \text{n})$ 情况下，由于没有额外字段，在考虑到数据对齐的情况下，每个节点可以节省多至 $1/3$ 的内存。

但是实际运行实在是太太太太慢了！两块儿最慢，一个是树的重构，一个是插入时动态计算节点大小，这么一看，所谓没有额外字段根本没有意义，因为省略了 size 字段严重地拖累了运行时间。

接下来会在本篇基础上加入 size 字段，和惰性删除的特性，介绍 LSG （惰性替罪羊树）。