《DSAA》 12.1 自顶向下伸展树

2024-02-23 13:48

文章标签 自顶向下伸展 12.1 dsaa

本文主要是介绍《DSAA》 12.1 自顶向下伸展树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在许多应用中，当一个节点被访问后，马上就很可能再次被访问到，研究表明这种情况比人们预料的要频繁的多。所以伸展树的基本想法是：当一个节点被访问后，它就要通过一系列的旋转被放到根上。

自顶向下伸展树的搜索方式非常独特，它实际上是一个拆了又装的过程,这个过程被称为伸展：

最开始先新建两颗空树：L树和R树，用于缓存。在从原树自顶向下搜索时，每一次迭代都将父节点以上的部分拆除，视情况接到两旁的L树或R树上，直到搜索结束，这时用L树和R树接到到根上，而把根上原来的左右子树分别接到L树和R树上，处理完毕。

此时的树根就是所要寻找的节点，或者是一个最接近的节点。

值得一提的是：由于伸展树的特性，它的删除操作比其他的二叉搜索树要容易得多，因为搜索的结果使要删除的节点挪到了根上，之后的操作很巧妙：在左子树中反过来搜索根，这样做的结果是左儿子的右子树因为旋转而消失了，于是可以把根的右子树接到左儿子上，根自然被删除。

关于自顶向下伸展树的操作，原书中给出了很简洁漂亮的实现，由上面的例子可见一斑。

以下演示是一颗树的逐节点删除过程，用的是后文红黑树用的例子，对照一下这两种树的运行也很有趣：

这篇关于《DSAA》 12.1 自顶向下伸展树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/738848。 23002807@qq.com

相关文章

【C++ Primer Plus习题】12.1

【C++ Primer Plus习题】12.1

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "Cow.h"using namespace std;int main(){Cow c1;Cow c2("老母牛", "喝奶"

阅读更多...

[E二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

[E二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

文章目录 1. 题目来源2. 题目解析 1. 题目来源链接：104. 二叉树的最大深度题单：链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA） §2.2 自顶向下 DFS 2. 题目解析思路：很基础的 dfs 题目哈，使用 bfs 也能做，体会一下两者的区别。自顶向下、自底向上都可以处理这个题目。时间复杂度： O ( n

阅读更多...

[M二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

[M二叉树] lc104. 二叉树的最大深度(dfs+自顶向下)

文章目录 1. 题目来源2. 题目解析 1. 题目来源链接：104. 二叉树的最大深度题单：链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA） §2.2 自顶向下 DFS 2. 题目解析思路：很基础的 dfs 题目哈，使用 bfs 也能做，体会一下两者的区别。自顶向下、自底向上都可以处理这个题目。时间复杂度： O ( n

阅读更多...

树学习 ---------伸展树（splay Tree）

树学习 ---------伸展树（splay Tree）

一、简介：伸展树，或者叫自适应查找树，是一种用于保存有序集合的简单高效的数据结构。伸展树实质上是一个二叉查找树。允许查找，插入，删除，删除最小，删除最大，分割，合并等许多操作，这些操作的时间复杂度为O(logN)。由于伸展树可以适应需求序列，因此他们的性能在实际应用中更优秀。

阅读更多...

ubuntu16.04怎样才能安装 wxpython 2.8.12.1

ubuntu16.04怎样才能安装 wxpython 2.8.12.1

使用sudo apt install python-wxgtk2.8 根本找不到包关于RIDE需要wxpython 16.04里面需要做如下才能安装 wxpython 2.8.12.1 echo "deb http://cz.archive.ubuntu.com/ubuntu trusty main universe" | sudo tee /etc/apt/sources.list.d

阅读更多...

伸展树(数据结构篇)

伸展树(数据结构篇)

数据结构之伸展树伸展树概念：伸展树是一颗对任意一个节点被访问后，就经过一系列的AVL树的旋转操作将该节点放到根上的特殊二叉查找树。伸展树能保证对树操作M次的时间复杂度为O(MlogN)，而当一个查找树的一个节点刚好处于查找树最坏的情形，我们每次访问都需要按照最坏情形的时间计算，这将耗费O(M*N)的时间，伸展树就是要将访问的节点进行移动，使它不一直存在一个地方，避免了多次操作最坏情形的

阅读更多...

oracle 12.1 rac to rac adg（maa）搭建保姆级教程

oracle 12.1 rac to rac adg（maa）搭建保姆级教程

目录资源配置一、主库集群操作 1.主库增加standbylog 2.主库开启force logging及归档 3.主库配置参数 4.生成参数文件并将参数文件、密码文件拷贝至备库 4.1参数文件处理 4.2密码文件处理二、备库操作 1.备库修改参数文件 1.1创建adump目录并在参数文件修改（两节点均创建） 1.2增加dg相关参数 1.3备库asm创建目录结构

阅读更多...

wikioi 1396 伸展树（两个模板）

wikioi 1396 伸展树（两个模板）

题目描述 Description Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就

阅读更多...

编译原理|第四章自顶向下语法分析方法——知识点总结

编译原理|第四章自顶向下语法分析方法——知识点总结

1.什么是FIRST、FOLLOW、SELECT集合? FIRST：A可以推出的所有式子的“第一个”非终结符！ FOLLOW：3个求解规则 1.主程序Beginadvance;E;end2.E过程Procedure EBeginT;E';end3.E'过程Procedure EBeginif sym = '+' thenbeginadvance;E;ende

阅读更多...

12.1 抵达鱼人岛

12.1 抵达鱼人岛

现在我们要进入TCP协议中最复杂也是最关键的部分——拥塞控制。如果TCP是一个巨人，我们之前所研究的只是这个巨人的外形、肌肉和骨骼，拥塞控制是他的内脏，是真正决定其生机与活力的部分；若把TCP探秘之旅比作海贼王（航海王）中Monkey·D·Luffy一伙的冒险旅程，那么之前的探索只是伟大航路（Grand Line）的前半段——乐园。我们现在是Grad Line的中点——鱼人岛，即将进入更加新奇、更

阅读更多...