13 个版本

0.3.3	2024年2月7日
0.3.2	2023年11月6日
0.2.4	2023年11月4日
0.2.1	2023年10月19日
0.1.3	2023年10月13日

#224 在数据结构

每月125 次下载

Apache-2.0

52KB
870 行

lctree

Rust 实现 Link-cut tree：在以下操作下维护动态树森林的自平衡数据结构，这些操作的平均时间复杂度为 O(logn)

link(v, w)：在节点 v 和 w 之间创建边。
cut(v, w)：移除节点 v 和 w 之间的边。
connected(v, w)：如果节点 v 和 w 在同一棵树中，则返回 true。
path(v, w)：在节点 v 和 w 之间的路径上进行计算。

使用方法

此示例展示了如何链接和剪切边

use lctree::LinkCutTree;

fn main() {
    // We form a link-cut tree for the following forest:
    // (the numbers in parentheses are the weights of the nodes):
    //            a(9)
    //           /    \
    //         b(1)    e(2)
    //        /   \      \
    //      c(8)  d(10)   f(4)
    let mut lctree = LinkCutTree::default();
    let a = lctree.make_tree(9.);
    let b = lctree.make_tree(1.);
    let c = lctree.make_tree(8.);
    let d = lctree.make_tree(10.);
    let e = lctree.make_tree(2.);
    let f = lctree.make_tree(4.);

    lctree.link(b, a);
    lctree.link(c, b);
    lctree.link(d, b);
    lctree.link(e, a);
    lctree.link(f, e);

    // Checking connectivity:
    assert!(lctree.connected(c, f)); // connected

    // Path aggregation:
    // We find the node with max weight on the path between c to f,
    // where a has the maximum weight of 9.0:
    let heaviest_node = lctree.path(c, f);
    assert_eq!(heaviest_node.idx, a);
    assert_eq!(heaviest_node.weight, 9.0);

    // We cut node e from its parent a:
    lctree.cut(e, a);

    // The forest should now look like this:
    //            a(9)
    //           /    
    //         b(1)      e(2)
    //        /   \        \
    //      c(8)  d(10)    f(4)

    // We check connectivity again:
    assert!(!lctree.connected(c, f)); // not connected anymore
}

高级用法包括路径操作

常见路径聚合

可以在两个节点之间的路径上执行各种计算，例如 findmax、findmin 或 findsum

use lctree::{LinkCutTree, FindMax, FindMin, FindSum};

fn main() {
    // We form a link-cut tree from the following rooted tree
    // (the numbers in parentheses are the weights of the nodes):
    //           a(9)
    //           /  \
    //         b(1)  e(2)
    //        /   \    \
    //      c(8)  d(10)  f(4)

    // Use FindMax, FindMin or FindSum, depending on your usage:
    let mut lctree: LinkCutTree<FindSum> = lctree::LinkCutTree::new();
    let a = lctree.make_tree(9.);
    let b = lctree.make_tree(1.);
    let c = lctree.make_tree(8.);
    let d = lctree.make_tree(10.);
    let e = lctree.make_tree(2.);
    let f = lctree.make_tree(4.);

    lctree.link(b, a);
    lctree.link(c, b);
    lctree.link(d, b);
    lctree.link(e, a);
    lctree.link(f, e);

    // We find the sum of the weights on the path between c to f,
    let result = lctree.path(c, f);
    assert_eq!(result.sum, 8. + 1. + 9. + 2. + 4.);
}

自定义路径聚合函数

可以通过使用 Path 特性来定义自定义路径聚合函数

use lctree::{LinkCutTree, Path};

#[derive(Copy, Clone)]
pub struct FindXor {
    pub xor: u64,
}

impl Path for FindXor {
    fn default(weight: f64, _: usize) -> Self {
        FindXor {
            xor: weight as u64,
        }
    }

    fn aggregate(&mut self, other: Self) {
        self.xor ^= other.xor;
    }
}

fn main() {
    // We form a link-cut tree from the following rooted tree
    // (the numbers in parentheses are the weights of the nodes):
    //           a(9)
    //           /  \
    //         b(1)  e(2)
    //        /   \    \
    //      c(8)  d(10)  f(4)
    let mut lctree: LinkCutTree<FindXor> = LinkCutTree::new();
    let a = lctree.make_tree(9.);
    let b = lctree.make_tree(1.);
    let c = lctree.make_tree(8.);
    let d = lctree.make_tree(10.);
    let e = lctree.make_tree(2.);
    let f = lctree.make_tree(4.);

    lctree.link(b, a);
    lctree.link(c, b);
    lctree.link(d, b);
    lctree.link(e, a);
    lctree.link(f, e);

    // We find the xor of the weights on the path between c to f,
    let result = lctree.path(c, f);
    assert_eq!(result.xor, 8 ^ 1 ^ 9 ^ 2 ^ 4);
}

基准测试

执行多种随机操作（link(v, w)，cut(v, w)，connected(v, w)或findmax(v, w)）的总运行时间，这些操作在大小不同的森林上进行（检查基准测试详情这里）。

节点数量	操作	lctree	暴力搜索
100	10K	4.8161 毫秒	18.013 毫秒
200	20K	11.091 毫秒	69.855 毫秒
500	50K	31.623 毫秒	429.53 毫秒
1000	100K	68.649 毫秒	1.8746 秒
5000	500K	445.83 毫秒	46.854 秒
10K	1M	964.64 毫秒	183.24 秒

鸣谢

此crate应用了以下来源的核心概念和思想

"动态树的数据结构"由D. Sleator和R. E. TarJan所著（在STOC '81中发表）。
作者D. Sleator的链接-剪切树源代码。
麻省理工学院关于动态图的讲座：讲座，笔记，以及源代码。
关于根树、重根和splay操作概念的有帮助的博客文章：根树，重根和splay操作。

许可协议

本项目根据Apache License, Version 2.0许可 - 有关详细信息，请参阅LICENSE.md文件。

贡献

除非您明确表示，否则根据Apache-2.0许可定义，您有意提交以包含在作品中的任何贡献，都应按照上述许可，不附加任何额外条款或条件。