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

相关文章

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Spring Boot 整合 Apache Flink 的详细过程

《SpringBoot整合ApacheFlink的详细过程》ApacheFlink是一个高性能的分布式流处理框架,而SpringBoot提供了快速构建企业级应用的能力,下面给大家介绍Spri... 目录Spring Boot 整合 Apache Flink 教程一、背景与目标二、环境准备三、创建项目 & 添

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

pytest+allure环境搭建+自动化实践过程

《pytest+allure环境搭建+自动化实践过程》:本文主要介绍pytest+allure环境搭建+自动化实践过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录一、pytest下载安装1.1、安装pytest1.2、检测是否安装成功二、allure下载安装2.

Pytorch介绍与安装过程

《Pytorch介绍与安装过程》PyTorch因其直观的设计、卓越的灵活性以及强大的动态计算图功能,迅速在学术界和工业界获得了广泛认可,成为当前深度学习研究和开发的主流工具之一,本文给大家介绍Pyto... 目录1、Pytorch介绍1.1、核心理念1.2、核心组件与功能1.3、适用场景与优势总结1.4、优

Redis指南及6.2.x版本安装过程

《Redis指南及6.2.x版本安装过程》Redis是完全开源免费的,遵守BSD协议,是一个高性能(NOSQL)的key-value数据库,Redis是一个开源的使用ANSIC语言编写、支持网络、... 目录概述Redis特点Redis应用场景缓存缓存分布式会话分布式锁社交网络最新列表Redis各版本介绍旧

SpringBoot整合Sa-Token实现RBAC权限模型的过程解析

《SpringBoot整合Sa-Token实现RBAC权限模型的过程解析》:本文主要介绍SpringBoot整合Sa-Token实现RBAC权限模型的过程解析,本文给大家介绍的非常详细,对大家的学... 目录前言一、基础概念1.1 RBAC模型核心概念1.2 Sa-Token核心功能1.3 环境准备二、表结

Jvm sandbox mock机制的实践过程

《Jvmsandboxmock机制的实践过程》:本文主要介绍Jvmsandboxmock机制的实践过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、背景二、定义一个损坏的钟1、 Springboot工程中创建一个Clock类2、 添加一个Controller

python多线程并发测试过程

《python多线程并发测试过程》:本文主要介绍python多线程并发测试过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、并发与并行?二、同步与异步的概念?三、线程与进程的区别?需求1:多线程执行不同任务需求2:多线程执行相同任务总结一、并发与并行?1、

MybatisPlus3.3.1整合clickhouse的过程

《MybatisPlus3.3.1整合clickhouse的过程》:本文主要介绍MybatisPlus3.3.1整合clickhouse的过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定... 前言ClickHouse是俄罗斯Yandex发布的一款数据分析型数据库支持sql语法,详情可以访问官网,