Splay Tree学习过程

2024-05-15 08:58
文章标签 学习 过程 tree splay

本文主要是介绍Splay Tree学习过程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我把学习经历贴上来(包括看过那些论文,参考过哪些 博客)

http://en.wikipedia.org/wiki/Splay_tree

http://www.link.cs.cmu.edu/splay/  demo

http://www.artofproblemsolving.com/blog/54268 zkw大神

https://www.youtube.com/watch?v=nKZWL9hbcI4 动画演示

伸展树是什么,有什么用,如何实现?

(1)伸展树是什么?

伸展树是一种自适应的平衡二叉树,主要支持的操作是动态维护一个有序表, 从而支持字典, 前驱, 后继, 中序遍历, 优先队列等等多种操作(摘自http://www.artofproblemsolving.com/blog/54268)他支持二叉树的所有操作,并且摊还之后时间复杂度都为对数。但是并不保证某次操作都在对数时间内。

(2)伸展树有什么用?

白书里介绍了可分裂合并序列的一个典型应用时文本编辑器。因为文本需要在任意位置插入和删除字符,但是数组不能实现快速插入,链表不能快速定位。所以数组和链表这时都无用武之地。虽然两者结合起来,形成链式数组在实际运用中比较普遍。但是伸展树也不失为一个选择。(2014/8/11)

(3)如何实现?

首先我们要向伸展树的每个节点要维护哪些信息。要维护哪些信息,我们从他的基本操作入手。记得04年国家集训队论文杨思雨一文《伸展树的基本操作与应用》中给出9中基本操作,我们分析这九种操作然后确立维护哪些信息。

首先记住splay tree也是一种二叉查找树,所以维护的关键字是有序的。

操作1: 查找关键字X

       这根普通的二叉查找树没什么区别,我们只要从根节点出发,如果当前节点比要查找的关键字大,则查找右子树,如果比当前节点小,则查找左子树。如果等于那么返回当前节点。

操作2:求最大值

       因为是二叉查找树,所以最右边的叶子节点就是最大值。

操作3:求最小值

       因为是二叉查找树,所以最左边的叶子节点就是最小值。

操作4:求前驱

        这里我们如果对每个保存其父节点的,那么这操作就会简单许多。

操作5:求后继

        同理。

这里求前驱和后继要注意一下:

操作6:在介绍插入,删除操作之前,由于要维护树的平衡,所以我们还是先将旋转操作。

其实,旋转操作很好理解的,总共有六种,但是是对称的,所以知道三种,其他三种也就知道了。

1:如果要旋转的节点x的父节点是根节点,那么只要将父节点绕着x节点顺时针旋转一次就好

2:

操作6:插入操作X

      首先按照正常的二叉查找树的操作插入X,然后







这篇关于Splay Tree学习过程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/991383

相关文章

Java进程异常故障定位及排查过程

《Java进程异常故障定位及排查过程》:本文主要介绍Java进程异常故障定位及排查过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、故障发现与初步判断1. 监控系统告警2. 日志初步分析二、核心排查工具与步骤1. 进程状态检查2. CPU 飙升问题3. 内存

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

MySQL中的InnoDB单表访问过程

《MySQL中的InnoDB单表访问过程》:本文主要介绍MySQL中的InnoDB单表访问过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、访问类型【1】const【2】ref【3】ref_or_null【4】range【5】index【6】

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

Navicat数据表的数据添加,删除及使用sql完成数据的添加过程

《Navicat数据表的数据添加,删除及使用sql完成数据的添加过程》:本文主要介绍Navicat数据表的数据添加,删除及使用sql完成数据的添加过程,具有很好的参考价值,希望对大家有所帮助,如有... 目录Navicat数据表数据添加,删除及使用sql完成数据添加选中操作的表则出现如下界面,查看左下角从左

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现