[ACM]Link-Cut Tree实现动态树初探
2024-08-29 23:25:07
动态树问题是指的一类问题，而不是具体指的某一种数据结构。它主要维护一个包含若干有根树的森林，实现对森林的修改和查询等。
实现动态树的数据结构据说主要有4种，Link-Cut Tree是其中的一种。Link-Cut Tree可以看作是所求森林的一个映射，二者的映射关系将在后面讲述。
先说Link-Cut Tree支持的基本操作包含：
1.(access)Link-Cut Tree的核心操作，后面的操作都需要access这个操作的支持。
2.(make)在森林中建立一棵树。
3.(findroot)查询森林中某一棵树的根。
4.(cut)将某个节点从当前的树中分离，也就是一棵树分成两棵树。
5.(link)将2棵根不相同的树合并，也就是把两棵树合并成一棵树。
通过上述基本操作，就能够实现动态树的一些基本问题。需要注意的是，Link-Cut Tree只实现了节点到根的操作，不过我们可以通过修改基本操作实现一些点到点的操作，如求LCA，具体过程会在后文中讲述。
再来说说Link-Cut Tree的数据组织，在说Link-Cut Tree的数据组织之前应该先细说一下Link-Cut Tree的核心操作access(u)，这样有助于理解。
access(u)是访问u节点操作(从u访问到根)，实际上是寻找u节点到根节点的路径。如果只是简单的向上回溯寻根，那么遇到链很长的树时，时间复杂度将会退化成线性。Link-Cut Tree采用伸展树这种数据结构，将向上访问的父节点加入伸展树中
最新文章
- Redis & Python/Django 简单用户登陆
- Visual Studio图片注释image-comments扩展
- myBatis 实现用户表增删查改操作<方法1 没有使用接口的>（最终版）
- Java API —— Collections类
- 自定义控件ViewPagae<
- Java开发所需架包官方下载
- NET Core，Ubuntu运行
- HDU 4857 （反向拓扑排序 + 优先队列）
- Python的数据库操作
- Python开发【第十篇】：Redis
- lua 日期的一些函数
- sshd服务
- Spark基本架构及原理
- 循环取到json中的字段数据，加到html中
- .NetCore使用Swagger进行单版本或多版本控制处理
- django中admin的使用
- sudo非交互式输入密码
- c和c++的强制类型转换
- 5种样式实现div容器中三图摆放实例对比说明
- WPF关于改变ListBoxItem的颜色的注意事项以及如何找到ListBox中的ItemsPanel