【平衡树】splay伸展树

2023-10-05 10:56
文章标签 平衡 splay 伸展

本文主要是介绍【平衡树】splay伸展树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.定义

 伸展树（Splay Tree）是一种自调整二叉搜索树，它通过不断进行伸展（splay）操作，将最近访问的节点移动到树的根节点，以提高对这些节点的访问效率。伸展树的主要特点是在插入、查找和删除操作时，都会执行伸展操作，使得最近访问的节点位于根节点，从而实现了一种局部性原理，即频繁访问的节点更容易被快速访问。

伸展树的基本伸展操作有三种：

  1. 伸展到根（Splay to Root）：将某个节点x伸展到树的根节点，通过一系列旋转操作实现，使得x成为新的根节点。

  2. 伸展到左子树的最右节点（Splay to Right Child's Leftmost Descendant）：将某个节点x伸展到其左子树的最右节点，同样通过一系列旋转操作实现。

  3. 伸展到右子树的最左节点（Splay to Left Child's Rightmost Descendant）：将某个节点x伸展到其右子树的最左节点，同样通过一系列旋转操作实现。

伸展树的操作包括插入、查找和删除。在每次操作之后，都会对相关的节点进行伸展，以保持树的平衡性和局部性原理。这种自调整性质使得伸展树在一般情况下表现出良好的性能，但最坏情况下的性能可能较差，因为它不保证平衡。

总之，伸展树是一种简单而有效的自平衡二叉搜索树，适用于需要频繁访问最近使用节点的场景。在实际应用中，可以根据具体需求选择合适的自平衡数据结构，如AVL树、红黑树等。

二.数据存储方式  && main函数

struct node{int val,cnt; //它的值 ,值有几个 int fa,son[2]; // 它的father和它的两个sonint siz; //它的子树个数 （即<=它的数有几个） 
}tree[maxn];
int main(){insert(-2147483647);insert(+2147483647);scanf("%d",&n);int ops,x;for(int i=1;i<=n;i++){scanf("%d%d",&ops,&x);if(ops==1) insert(x);else if(ops==2) del(x);else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);else if(ops==4) printf("%d\n",kth(x+1));else if(ops==5) printf("%d\n",tree[pre(x)].val);else printf("%d\n",tree[nxt(x)].val);}return 0;
}

三. insert

void insert(int x){int u=root,fa=0;while(u && tree[u].val!=x){fa=u;u=tree[u].son[x>tree[u].val];}//已经有这个数字 if(u){tree[u].cnt++;}else{u=++cnt;if(fa){tree[fa].son[x>tree[fa].val]=u;}tree[u].fa=fa;tree[u].son[0]=tree[u].son[1]=0;tree[u].val=x;tree[u].cnt=tree[u].siz=1;} splay(u,0);
}

四.splay

  • 若共线要先转一下父节点，再转x
  • 不共线，转两下x即可
  • 重复上面操作，直到到达目标 
    void splay(int x,int goal){while(tree[x].fa!=goal){int fa=tree[x].fa,gfa=tree[fa].fa;if(gfa!=goal){//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 ((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);}	rotate(x);}if(goal==0) root=x;
}

五.rotate

注意：这边使用了异或和判断孩子的功能，固左转和右转通用

void updata(int x){tree[x].siz=tree[ tree[x].son[0] ].siz+tree[ tree[x].son[1] ].siz+tree[x].cnt;
}
void rotate(int x){//预处理 int fa=tree[x].fa,gfa=tree[fa].fa;int k=(tree[fa].son[1]==x); //左右孩子 //继承fa为gfa的孩子tree[gfa].son[ tree[gfa].son[1]==fa ] = x;tree[x].fa=gfa;//调整fa的son，即找人代替x为fa的k儿子 tree[fa].son[k]=tree[x].son[k^1];tree[ tree[x].son[k^1] ].fa = fa;//风水轮流转，爸爸成儿子tree[x].son[k^1]=fa;tree[fa].fa=x; //fa和x子树有变动，要更新 updata(fa);updata(x);
}

六.前驱后继

int pre(int x){Find(x);if(tree[root].val<x) return root; //特判//左子树中找最右的点int u=tree[root].son[0];while(tree[u].son[1]) u=tree[u].son[1];return u; 
}
int nxt(int x){Find(x);if(tree[root].val>x) return root; //特判 //右子树中找最左的点int u=tree[root].son[1];while(tree[u].son[0]) u=tree[u].son[0];return u; 	
}

七.delete

void del(int x){int p=pre(x),s=nxt(x);splay(p,0);splay(s,p);int del=tree[s].son[0];if(tree[del].cnt>1){tree[del].cnt--;//存在多个这个数字，直接减去一个 splay(del,0);}else{tree[s].son[0]=0;//清除掉节点 }   
}

八.查排名

int kth(int x){int u=root;if(tree[u].siz<x) return false;while(1){int y=tree[u].son[0];if(x>tree[y].siz+tree[u].cnt){	//排在u的后面 x-=tree[y].siz+tree[u].cnt;u=tree[u].son[1];}else if(tree[y].siz>=x){  //在u的前面 u=y;}else{return tree[u].val;}}
}

九.查排第几

将其变成根，看看左子树有多少个即可

十.AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n;
int root,cnt;
struct node{int val,cnt; //它的值 ,值有几个 int fa,son[2]; // 它的father和它的两个sonint siz; //它的子树个数 （即<=它的数有几个） 
}tree[maxn];
void updata(int x){tree[x].siz=tree[ tree[x].son[0] ].siz+tree[ tree[x].son[1] ].siz+tree[x].cnt;
}
void rotate(int x){//预处理 int fa=tree[x].fa,gfa=tree[fa].fa;int k=(tree[fa].son[1]==x); //左右孩子 //继承fa为gfa的孩子tree[gfa].son[ tree[gfa].son[1]==fa ] = x;tree[x].fa=gfa;//调整fa的son，即找人代替x为fa的k儿子 tree[fa].son[k]=tree[x].son[k^1];tree[ tree[x].son[k^1] ].fa = fa;//风水轮流转，爸爸成儿子tree[x].son[k^1]=fa;tree[fa].fa=x; //fa和x子树有变动，要更新 updata(fa);updata(x);
}
void splay(int x,int goal){while(tree[x].fa!=goal){int fa=tree[x].fa,gfa=tree[fa].fa;if(gfa!=goal){//同ture意思是都为左孩子,异或为0；同false都为右孩子，异或为0 ((tree[fa].son[0]==x)^(tree[gfa].son[0]==fa))==0 ? rotate(fa) : rotate(x);}	rotate(x);}if(goal==0) root=x;
}
void insert(int x){int u=root,fa=0;while(u && tree[u].val!=x){fa=u;u=tree[u].son[x>tree[u].val];}//已经有这个数字 if(u){tree[u].cnt++;}else{u=++cnt;if(fa){tree[fa].son[x>tree[fa].val]=u;}tree[u].fa=fa;tree[u].son[0]=tree[u].son[1]=0;tree[u].val=x;tree[u].cnt=tree[u].siz=1;} splay(u,0);
}
void Find(int x){int u=root;if(!u) return;//若x不存在，则u一定有误差，但在pre or nxt函数中已经特判了 while(tree[u].son[x>tree[u].val] && x!=tree[u].val){u=tree[u].son[x>tree[u].val];}splay(u,0);
}
int pre(int x){Find(x);if(tree[root].val<x) return root; //特判//左子树中找最右的点int u=tree[root].son[0];while(tree[u].son[1]) u=tree[u].son[1];return u; 
}
int nxt(int x){Find(x);if(tree[root].val>x) return root; //特判 //右子树中找最左的点int u=tree[root].son[1];while(tree[u].son[0]) u=tree[u].son[0];return u; 	
}
void del(int x){int p=pre(x),s=nxt(x);splay(p,0);splay(s,p);int del=tree[s].son[0];if(tree[del].cnt>1){tree[del].cnt--;//存在多个这个数字，直接减去一个 splay(del,0);}else{tree[s].son[0]=0;//清除掉节点 }   
}
int kth(int x){int u=root;if(tree[u].siz<x) return false;while(1){int y=tree[u].son[0];if(x>tree[y].siz+tree[u].cnt){	//排在u的后面 x-=tree[y].siz+tree[u].cnt;u=tree[u].son[1];}else if(tree[y].siz>=x){  //在u的前面 u=y;}else{return tree[u].val;}}
}
int main(){insert(-2147483647);insert(+2147483647);scanf("%d",&n);int ops,x;for(int i=1;i<=n;i++){scanf("%d%d",&ops,&x);if(ops==1) insert(x);else if(ops==2) del(x);else if(ops==3) Find(x),printf("%d\n",tree[tree[root].son[0]].siz);else if(ops==4) printf("%d\n",kth(x+1));else if(ops==5) printf("%d\n",tree[pre(x)].val);else printf("%d\n",tree[nxt(x)].val);}return 0;
}

这篇关于【平衡树】splay伸展树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/4517。

相关文章

写给大数据开发：你真的“慢“了吗？揭秘技术与职场的平衡艺术

写给大数据开发：你真的“慢“了吗？揭秘技术与职场的平衡艺术

你是否曾经在深夜里，面对着一个棘手的数据处理问题，感到无比沮丧？或者在一次重要的项目汇报中，突然语塞，无法清晰地表达你的技术方案？作为一名大数据开发者，这些场景可能再熟悉不过。但别担心，因为你并不孤单。让我们一起探讨如何在这个瞬息万变的行业中，既磨练技术利刃，又培养职场软实力。 目录 技术与时间的赛跑1. 长远视角的重要性2. 复利效应在技能学习中的应用 跨界思维：数据结构教我们的职场智
阅读更多...
代码随想录 -- 二叉树 -- 平衡二叉树

代码随想录 -- 二叉树 -- 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode） 思路：仍然是递归调用 1. 定义一个递归函数 count 用来计算二叉树的层数 2. isBalanced 函数：如果传入根节点为空返回真；如果根节点 | 左子树的层数 - 右子树的层数 | 大于1，返回假；最后返回根节点左子树、右子树是否是平衡二叉树。 class Solution(object):def count(self,root
阅读更多...
构建STM32智能平衡车项目：PID控制算法与蓝牙通信技术

构建STM32智能平衡车项目：PID控制算法与蓝牙通信技术

一、项目概述 项目目标和用途 本项目旨在设计和实现一款基于STM32单片机的平衡车。平衡车是一种新型的个人交通工具，广泛应用于短途出行、休闲娱乐等场景。通过本项目，我们希望能够实现一款具备良好稳定性和操控性的平衡车，能够在不同的地形上自如行驶。 解决的问题和带来的价值 平衡车的核心问题在于如何保持其平衡。传统的平衡车往往依赖于复杂的控制算法和高精度的传感器。通过本项目，我们将利用STM32
阅读更多...
二叉搜索树、平衡二叉树、B树、B+树、B*树

二叉搜索树、平衡二叉树、B树、B+树、B*树

二叉查找树 二叉查找树，由于不平衡，如果连续插入的数据是有顺序的、会导致如下图B的所示，此时搜索会退化到O(N)　　 二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树： （1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2） 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3） 任
阅读更多...
Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers

Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers

对应POJ 题目：点击打开链接 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 72765 Accepted: 22465Case Time Limit: 2000MS Description You have N integers, A1
阅读更多...
Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain

Splay树（区间添加删除 | 区间翻转）——HDU 3487 Play with Chain

对应HDU题目：点击打开链接 Play with Chain Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4571    Accepted Submission(s): 1859 Problem Descript
阅读更多...
【C++】【数据结构】一步一步写平衡二叉树[AVL]

【C++】【数据结构】一步一步写平衡二叉树[AVL]

转载：有修正，原作者存在一些错误，这里进行了更正。/* 平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体第一个引入平衡概念的二叉树。特点：对于每一个结点，它的左右子树的高度之差不能超过1，若插入或删除一个节点之后使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决的了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度
阅读更多...
数据结构（13）——平衡二叉树（红黑树）

数据结构（13）——平衡二叉树（红黑树）

欢迎来到博主的专栏——数据结构 博主ID：代码小号 文章目录 红黑树红黑树节点之间的关系红黑树的插入uncle节点为红色uncle节点是黑色或者没有uncle节点 红黑树 平衡二叉树最出名的除了AVL树之外就是红黑树（RBTree），所谓红黑树，即拥有以下特性的平衡二叉树 （1）每个节点要么是红色，要么是黑色 （2）根节点必须是黑色 （3）红色节点的子节点必须是黑色 （
阅读更多...
C语言《智能自平衡小车，实现平衡功能的基础上，加入了超声波避障、超声波跟随、蓝牙遥控等功能》+源代码+文档说明

C语言《智能自平衡小车，实现平衡功能的基础上，加入了超声波避障、超声波跟随、蓝牙遥控等功能》+源代码+文档说明

文章目录 源代码下载地址项目介绍项目功能 项目备注源代码下载地址 源代码下载地址 点击这里下载源码 项目介绍 C语言《智能自平衡小车，实现平衡功能的基础上，加入了超声波避障、超声波跟随、蓝牙遥控等功能》+源代码+文档说明 项目功能 为了实现小车功能，小车硬件主要包括： 控制核心板带编码器的直流电机车架12V 1900mah锂电池 项目备注 1、该资源内项目代码都经过
阅读更多...
数据结构-高层数据结构：映射/字典（Map）【有序字典：基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典：基于哈希表】

数据结构-高层数据结构：映射/字典（Map）【有序字典：基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典：基于哈希表】

Map.java package map;/*** 映射*/public interface Map<K,V> {/*** 添加元素** @param key* @param value* @return void*/void add(K key,V value);/*** 删除元素** @param key* @return V*/V remove(K key);/*** 查看是
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2