• AVL树、红黑树、树堆、Splay

    在看了数据结构书上的一些内容之后，涉及到了红黑树、AVL树以及树堆的一些点，然后自己也不理解，就学习一下并写博客记录一下。

    目录

    一、树的一些简单知识

    1. 什么是树？

    2. 什么是二叉树？

    3. 什么是满二叉树？

    4. 什么是完全二叉树？

    二、红黑树

    1. 为什么有了AVL树还需要红黑树？

    2. 红黑树的规则

    3. 红黑树的应用

    4. 红黑树的左旋

    5. 红黑树的右旋

    6. 红黑树新增节点

    6.1 父亲为祖父的左儿子

     ​编辑

    6.2父亲为祖父的右儿子

     6.3 代码实现

     7. 删除节点

    7.1 自己为父亲节点的左儿子

    7.2 自己为父亲节点的右儿子

    7.3 代码实现

    三、树堆

    1. 什么是树堆？

    2. 旋转式Treap

    2.1 旋转式Treap结构与基本操作

    3. 无旋式Treap

    3.1 什么是无旋式Treap?

    3.2 无旋式结构和基本操作

    四、AVL树

    1. AVL树的性质

    2.为什么平衡二叉树是二叉搜索树？

    3.平衡因子与最小不平衡子树

    4. 平衡二叉树的左旋与右旋

    4.1右旋

    4.2 左旋

    4.3 先左旋再右旋

     4.4先右旋再左旋

    五、Splay树

    1. 什么是查找频率最高的节点？

    2. 怎么实现把每次查找的点搬到根节点上面去？

    3. Splay的基本操作

    3.1 我们要把一个点挪到根，那我们首先要知道怎么让一个点挪到它的父节点

    一、树的一些简单知识

    1. 什么是树？

     ①树有且仅有一个根节点

      ②当n>1时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个树，并称为跟的子树

    2. 什么是二叉树？

    二叉树，顾名思义就是每个节点只有两个子节点的树（最多）

    3. 什么是满二叉树？

    所有非叶子节点都存在子节点且所有的子节点都在同一层

    4. 什么是完全二叉树？

    完全二叉树指的是对一个有n个节点的二叉树，按照层级顺序编号。如果这棵树所有节点和同样深度的满二叉树的编号为1到n的节点位置一样，则这个树称为完全二叉树。

    二、红黑树

    1. 为什么有了AVL树还需要红黑树？

    • AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡
    • 在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣
    • 红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，整体性能优于AVL
    • 红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
    • 红黑树的红黑规则，保证最坏的情况下，也能在O ( logN ) 时间内解决
       

    2. 红黑树的规则

    在这里插入图片描述

    • 节点不是黑色，就是红色（非黑即红）
    • 根节点为黑色
    • 叶节点为黑色（叶节点是指末梢的空节点 Nil或Null）
    • 一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）
    • 每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）

    一些简单的说明

    • 约束4和5，保证了红黑树的大致平衡：根到叶子的所有路径中，最长路径不会超过最短路径的2倍。
    • 使得红黑树在最坏的情况下，也能有O ( logN ) 的查找效率
    • 黑色高度为3时，最短路径：黑色→ 黑色→ 黑色，最长路径：黑色→ 红色→ 黑色 → 红色 →  黑色
    • 最短路径的长度为2（不算Nil的叶子节点），最长路径为4
    • 关于叶子节点：Java实现中，null代表空节点，无法看到黑色的空节点，反而能看到传统的红色叶子节点
    • 默认新插入的节点为红色：因为父节点为黑色的概率较大，插入新节点为红色，可以避免颜色冲突

    3. 红黑树的应用

    • Java中，TreeMap、TreeSet都使用红黑树作为底层数据结构
    • JDK 1.8开始，HashMap也引入了红黑树：当冲突的链表长度超过8时，自动转为红黑树
    • Linux底层的CFS进程调度算法中，vruntime使用红黑树进行存储。
    • 多路复用技术的Epoll，其核心结构是红黑树 + 双向链表。

    4. 红黑树的左旋

    在这里插入图片描述

    5. 红黑树的右旋

     在这里插入图片描述

    6. 红黑树新增节点

    一些规则：

    • 新插入的节点默认为红色，原因：插入黑色节点会影响黑色高度，对红黑树的影响更大；
    • 新增节点x时，循环的依据： x != null && x != root && x.parent.color == RED，即节点非空、不是整棵树的根节点（保证存在父节点）且父节点为红色（违反红黑规则4，需要调整）
    • 完成循环调整后，需要将整棵树的根节点设为黑色，以满足红黑规则1；同时，根节点设为黑色，不会影响从根节点开始的所有路径的黑色高度

    6.1 父亲为祖父的左儿子

    情况一：父亲和叔叔都是红色

    • 当父亲为祖父的左儿子，父亲和叔叔都是红色时：
      （1）将父亲和叔叔改成黑色，以满足红黑规则4
      （2）父亲和叔叔变成黑色了，黑色高度变化，需要将祖父变成红色，以满足红黑规则5
      （3）从祖父开始，继续调整

    在这里插入图片描述

     情况二：叔叔为黑色，自己为父亲的左儿子

    • 父亲为祖父的左儿子，叔叔为黑色，自己是父亲的左儿子
      （1）父亲变成黑色，祖父变成红色（右子树的黑色高度变低）
      （2）对祖父进行右旋，让父节点成为新的祖父，以恢复右子树的黑色高度
      （3）不满足循环条件，退出循环

     

    情况三：叔叔为黑色，自己为父亲节点的右子树

    • 父亲为祖父的左儿子，叔叔为黑色，自己是父亲的右儿子
      （1）父亲成为新的x，对父亲进行左旋操作，构造情况二的初始状态
      （2）按照情况二，对新的x（原父亲）进行处理

    6.2父亲为祖父的右儿子

     情况一：父亲和叔叔都是红色

    • 父亲为祖父的右儿子，父亲和叔叔都是红色
      （1）将父亲和叔叔都变成黑色，以保证红黑规则4
      （2）将祖父变成红色，以保证红色规则5（相同的黑色高度）
      （3）从祖父开始，继续调整

    情况二：叔叔为黑色，自己是父亲的右儿子

    • 父亲为祖父的右儿子，叔叔为黑色，自己是父亲的右儿子
      （1）父亲变成黑色，祖父变成红色（左子树的黑色高度降低）
      （2）对祖父进行左旋操作，以恢复左子树的黑色高度
      （3）不满足循环条件，退出循环

    情况三：叔叔为黑色，自己为父亲节点的左儿子

    • 父亲是祖父的右儿子，叔叔为黑色，自己是父亲的左儿子
      （1）父节点成为新的X，对父亲进行右旋操作，构造情况二的初始情况
      （2）按照情况二，对新的x（原父节点）进行处理

    在这里插入图片描述

     6.3 代码实现

    1. public void fixAfterInsert(RedBlackTreeNode x) {
    2.     // 新插入的节点，默认为红色
    3.     x.color = RED;
    4.  
    5.     // p不为null、不是整棵树的根节点、父亲为红色，需要调整
    6.     while (x != null && this.root != x && x.parent.color == RED) {
    7.         // 父亲是祖父的左儿子
    8.         if (parentOf(x) == parentOf(parentOf(x)).left) {
    9.             // 父亲和叔叔都是红色
    10.             RedBlackTreeNode uncle = parentOf(parentOf(x)).right;
    11.             if (uncle.color == RED) {
    12.                 // 父亲和叔叔都变成黑色
    13.                 parentOf(x).color = BLACK;
    14.                 uncle.color = BLACK;
    15.                 // 祖父变成红色，继续从祖父开始进行调整
    16.                 parentOf(parentOf(x)).color = RED;
    17.                 x = parentOf(parentOf(x));
    18.             } else { // 叔叔为黑色
    19.                 // 自己是父亲的右儿子，需要对父亲左旋
    20.                 if (x == parentOf(x).right) {
    21.                     x = parentOf(x);
    22.                     leftRotate(x);
    23.                 }
    24.                 // 自己是父亲的左儿子，变色后右旋，保持黑色高度
    25.                 parentOf(x).color = BLACK;
    26.                 parentOf(parentOf(x)).color = RED;
    27.                 rightRotate(parentOf(parentOf(x)));
    28.             }
    29.         } else { //父亲是祖父的右儿子
    30.             RedBlackTreeNode uncle = parentOf(parentOf(x)).left;
    31.             // 父亲和叔叔都是红色
    32.             if (uncle.color == RED) {
    33.                 // 叔叔和父亲变成黑色
    34.                 parentOf(x).color = BLACK;
    35.                 uncle.color = BLACK;
    36.                 // 祖父变为红色，从祖父开始继续调整
    37.                 parentOf(parentOf(x)).color = RED;
    38.                 x = parentOf(parentOf(x));
    39.             } else {
    40.                 // 自己是父亲的左儿子，以父亲为中心右旋
    41.                 if (parentOf(x).left == x) {
    42.                     x = parentOf(x);
    43.                     rightRotate(x);
    44.                 }
    45.                 // 自己是父亲的右儿子，变色后左旋，保持黑色高度
    46.                 parentOf(x).color = BLACK;
    47.                 parentOf(parentOf(x)).color = RED;
    48.                 leftRotate(parentOf(parentOf(x)));
    49.             }
    50.         }
    51.     }
    52.  
    53.     // 最后将根节点置为黑色，以满足红黑规则1，又不会破坏规则5
    54.     this.root.color = BLACK;
    55. }
    56.  
    57. private static RedBlackTreeNode parentOf(RedBlackTreeNode p) {
    58.     return (p == null ? null : p.parent);
    59. }

     7. 删除节点

    一些规则：

    • 删除节点时，通过节点替换实现删除
    • 假设替换节点为x，需要在x替换被删节点后，从x开始进行调整
    • 调整操作，循环的依据： x != root && x.color == BLACK，即替换节点不能为整棵树的根节点，替换节点的颜色为黑色（改变了红黑高度）
    • 完成循环调整后，需要将x设为黑色，结束调整

    7.1 自己为父亲节点的左儿子

    情况一：兄弟为红色

    • 此时，自己为黑色、兄弟为红色、父节点为黑色（满足红黑规则4）
      （1）将兄弟变成黑色，父节点变成红色；这时，以父节点为起点的左子树黑色高度降低
      （2）对父节点进行左旋，以恢复左子树黑色高度；同时，兄弟的左孩子成为新的兄弟

    情况二：兄弟为黑色，左右侄子也是黑色

    • 此时，自己和兄弟都是黑色，父节点为黑色或红色；兄弟的两个儿子，都是黑色
      （1）将兄弟变成为红色，x指向父节点，继续进行调整

    在这里插入图片描述

     情况三：兄弟为黑色，右侄子为黑色

     此时，自己和兄弟均为黑色，父节点为红色或黑色；右侄子为黑色、左侄子为红色；
    （1）将左侄子变成黑色，兄弟变为红色；这时，以兄弟为起点的右子树黑色高度降低
    （2）将兄弟节点右旋，以恢复右子树的黑色高度；这时，左侄子将成为新的右兄弟
    此时，兄弟的右儿子为红色，满足情况4；继续按照情况4，对节点x进行调整
    在这里插入图片描述

    情况四：兄弟为黑色，右侄子为红色

    • 此时，自己和兄弟都是黑色，父节点为红色或黑色；右侄子为红色，左侄子为黑色或红色
      （1）兄弟颜色改成与父节点一致，右侄子和父节点都变成黑色
      （2）为了保证父节点变为黑色后，不影响所有路径的黑色高度，需要将父节点左旋（兄弟节点上提）
      （3）x指向根节点，结束循环

    7.2 自己为父亲节点的右儿子

    情况一：兄弟是红色节点

    此时，兄弟是红色节点，父节点必为黑色；若兄弟有左右儿子，左右儿子必为黑色（满足红黑规则4）
    （1）将兄弟变成黑色节点，父节点变成红色；这时，以父节点为起点的右子树黑色高度降低
    （2）将父节点右旋，以恢复右子树的黑色高度；这时，兄弟的右孩子成为新的兄弟

    此时，自己和兄弟都是黑色，将满足情况2、3和4、4

    在这里插入图片描述
    情况二：兄弟是黑色，左右侄子也是黑色 

    此时，自己和兄弟是黑色，父节点可以为红色或黑色
    （1）将兄弟变成红色，x指向父节点，继续对父节点进行调整
    在这里插入图片描述

    情况三：兄弟为黑色，左侄子为黑色

    此时，自己和兄弟均为黑色，父节点为黑色或红色；左侄子为黑色，右侄子为红色
    （1）将右侄子变成黑色，兄弟变成红色；这是，以兄弟为起点的左子树黑色高度降低
    （2）将兄弟左旋，以恢复左子树的黑色高度；这时，右侄子成为新的兄弟
    此时，将满足情况4，可以按照情况4，继续进行调整
    在这里插入图片描述

    情况四：兄弟为黑色，左侄子为红色

    此时，自己和兄弟均为黑色，父节点为红色或黑色；左侄子为红色，右侄子为红色或黑色
    （1）将兄弟变成与父节点一样的颜色，左侄子和父节点变成黑色
    （2）为了保证父节点变成黑色，不会影响所有路径的黑色高度，需要将父节点右旋（兄弟上提）
    （3）x指向根节点，退出循环
    在这里插入图片描述

    7.3 代码实现

    1. public void fixAfterDeletion(RedBlackTreeNode x) {
    2.     // x不是根节点且颜色为黑色，开始循环调整
    3.     while (x != root && x.color == BLACK) {
    4.         // x是父亲的左儿子
    5.         if (x == parentOf(x).left) {
    6.             RedBlackTreeNode brother = parentOf(x).right;
    7.             // 兄弟为红色
    8.             if (brother.color == RED) {
    9.                 // 兄弟变成黑色，父节点变成红色
    10.                 brother.color = BLACK;
    11.                 parentOf(x).color = RED;
    12.                 // 父节点左旋，恢复左子树的黑色高度
    13.                 leftRotate(parentOf(x));
    14.                 // 更新兄弟
    15.                 brother = parentOf(x).right;
    16.             }
    17.  
    18.             // 兄弟为黑色，左右侄子为黑色
    19.             if (brother.left.color == BLACK && brother.right.color == BLACK) {
    20.                 // 兄弟变成红色
    21.                 brother.color = RED;
    22.                 // 从父节点开始继续调整
    23.                 x = parentOf(x);
    24.             } else {
    25.                 // 右侄子为黑色（左侄子为红色）
    26.                 if (brother.right.color == BLACK) {
    27.                     // 左侄子变为黑色，兄弟变成红色
    28.                     brother.left.color = BLACK;
    29.                     brother.color = RED;
    30.                     // 兄弟右旋，恢复右子树黑色高度
    31.                     rightRotate(brother);
    32.                     // 左侄子成为新的兄弟
    33.                     brother = parentOf(x).right;
    34.                 }
    35.                 // 右侄子为红色，兄弟变成父节点颜色
    36.                 brother.color = parentOf(x).color;
    37.                 // 父节点和右侄子变成黑色
    38.                 parentOf(x).color = BLACK;
    39.                 brother.right.color = BLACK;
    40.                 // 父节点左旋
    41.                 leftRotate(parentOf(x));
    42.                 // x指向根节点
    43.                 x = root;
    44.             }
    45.         } else {
    46.             RedBlackTreeNode brother = parentOf(x).left;
    47.             // 兄弟为红色
    48.             if (brother.color == RED) {
    49.                 // 兄弟变黑色，父亲变红色
    50.                 brother.color = BLACK;
    51.                 parentOf(x).color = RED;
    52.                 // 父亲右旋，恢复红黑色高度
    53.                 rightRotate(parentOf(x));
    54.                 // 更新兄弟为右侄子
    55.                 brother = parentOf(x).left;
    56.             }
    57.  
    58.             // 兄弟的左右儿子为黑色
    59.             if (brother.left.color == BLACK && brother.right.color == BLACK) {
    60.                 // 兄弟变为红色
    61.                 brother.color = RED;
    62.                 // x指向父节点，继续进行调整
    63.                 x = parentOf(x);
    64.             } else {
    65.                 // 左侄子为黑色(右侄子为红色)
    66.                 if (brother.left.color == BLACK) {
    67.                     // 右侄子变黑色，兄弟变红色
    68.                     brother.right.color = BLACK;
    69.                     brother.color = RED;
    70.                     // 对兄弟左旋
    71.                     leftRotate(brother);
    72.                     // 右侄子成为新的兄弟
    73.                     brother = parentOf(x).left;
    74.                 }
    75.  
    76.                 // 左侄子为红色，兄弟改为父节点颜色
    77.                 brother.color = parentOf(x).color;
    78.                 // 父节点和左侄子变成黑色
    79.                 brother.left.color = BLACK;
    80.                 parentOf(x).color = BLACK;
    81.                 // 兄弟节点上提(右旋父节点)
    82.                 rightRotate(parentOf(x));
    83.                 // x指向根节点
    84.                 x = root;
    85.             }
    86.  
    87.         }
    88.     }
    89.     // 更新x为黑色
    90.     x.color = BLACK;
    91. }

     参考文章：红黑树详解_晓之木初的博客-CSDN博客_红黑树

    三、树堆

    1. 什么是树堆？

    • Treap(树堆)是一种弱平衡的搜索树，顾名思义，Treap就是由Tree和Heap(树和堆)两种数据结构组合而成的数据结构。
    • Treap的每个节点上要额外储存一个值priority，代表每个节点的优先级。因此对于每个节点，不仅要满足二叉搜索树的基本性质，还需额外满足父节点的priority大于（或者小于）两个子节点的priority。实际上，这个priorioty值又被称为"修正值"。【因为满足堆的条件，堆存在大根堆和小根堆】
    • 但由于priority是随机生成的，因此我们一般认为Treap是“期望平衡”的。
    • 我们一般将Treap分为两类：①.旋转式Treap；②.无旋式Treap。我们根据这两种分类对Treap进行详解。

    2. 旋转式Treap

    旋转式Treap不支持区间操作，但是相比于无旋式Treap效率要高一些。

    它的基本操作有“左旋”、“右旋”

    2.1 旋转式Treap结构与基本操作

    首先来看一个合法的Treap

    从图中我们可以看到此处满足小根堆的情况

    【图片来自数据结构-Treap(树堆) 详解_HeartFireY的博客-CSDN博客_treap】

     我们现在假设执行插入操作，节点键值key=7，随机生成priority值为7。

    我们按照二叉搜索树的方式进行插入【按照Key值大小放在左边还是右边】

    显然，并不满足堆的条件

    1. 右旋操作

    当我们发现当前节点左儿子的priority小于自身priority的时候，我们可以通过右旋操作解决问题。我们首先通过上面的样例来理解右旋操作的原理：

    对于新插入的节点，我们检索其根节点，发现根节点左儿子的priority小于自身priority，因此执行右旋操作
    在这里插入图片描述

     我们将左字节点提到根节点作为新的根，原根节点右旋至新根节点的右子节点。

    旋转完之后的情况如下：

    在这里插入图片描述

    此时还是不满足堆，这个时候可以发现是根节点的左子树的右子树不满足情况，我们将其进行左旋

    在这里插入图片描述

    3. 无旋式Treap

    3.1 什么是无旋式Treap?

    • 无旋式Treap，即无旋转操作的Treap，他有两种核心操作：分裂、合并。也正是其操作方式的特性使其具有支持维护序列和可持久化等特性。因此我们可以用封装的无旋式Treap实现类似C++STL中set的效果。
    • 优点：支持可持久化，操作种类多(支持区间操作)
    • 缺点：相比于Splay要慢很多，且相比于旋转式Treap也要慢一些。

    3.2 无旋式结构和基本操作

    还是根据上面的案例进行讲解

    在这里插入图片描述

    1. 分裂操作

    对无旋式Treap执行分裂操作有两种含义，即按照权值进行分裂或按照排名进行分裂。我们首先来讲解按照权值分裂：

    所谓按照权值分裂即：将根指针指向的Treap分裂为两个Treap，第一个Treap所有节点的权值小于等于给定key值，第二个Treap所有节点的权值大于等于给定k e y keykey值。

    定义操作pair split(node *root, int key)为分裂操作，其中u uu为根指针，k e y keykey为给定键值。

    那么操作的大致思路如下：

    判断root所指向的节点是否为空；

    将当前root节点所指向的值与给定的key值进行比较：

    • 如果root → val > key ，则说明root所指向的节点及其右子树全部属于第二个Treap，同时向左子树继续分裂；
    • 如果root→val≤key，则说明root所指向的节点及其左子树全部属于第一个Treap，同时向右子树继续分裂。

    根据上述两个条件判断递归向左子树分裂or右子树分裂，并继续递归分裂子树，待子树分裂完成后按刚刚的判断情况连接 的左子树或右子树到递归分裂所得的子树中。

    我们通过具体的例子来理解这个操作：以样例所示Treap为例，指定key=7进行分裂。
    在这里插入图片描述

    第一次：root→val=11>key，因此可以判断当前root指向的节点及右子树应该属于第二个Treap，向左子树分裂；

    第二次：root→val=6≤key，因此可以判断当前root指向的节点及其左子树全部属于第一个Treap，向右子树分裂；

    第三次，root→val=8>key，因此可以判断当前root指向的节点及其右子树全部属于第二个Treap，此时分裂到叶子节点，无法继续分裂，分裂操作到此终止。

    最终，上述二叉树分裂为两棵二叉树：
    在这里插入图片描述

     2. 合并操作

    必须满足u中所有结点的关键值小于等于v中所有结点的关键值。因为两个Treap已经有序，我们只需要考虑priority来决定哪个 Treap 应与另一个Treap的儿子合并。

    定义操作node *merge(node *u, node *v)，其中u和v均为待合并的树根指针。

    那么操作的大致思路如下：

    指针判空：如果u指针为空，则返回v；如果v指针为空，则返回u指针；
    若 u 的根结点的priority 小于 v 的，那么 u 即为新根结点，v 应与 u 的右子树合并；反之，则 v 作为新根结点，然后让 u 与 v 的左子树合并。
    不难发现，这样合并所得的树依然满足priority 的大根堆性质。

    我们依然通过样例来对这个过程进行展示：在先前的分裂操作中，我们得到了两棵子树，设其根节点指针分别为u、v。

    在这里插入图片描述

    函数入口node * new_tree = merge(u, v);

    第一次，①.判断u和v均为非空指针 ②u指向节点的priority=12，v vv指向节点的priority=6，则v vv应该作为新根节点，u与v的左子树执行合并，执行merge(u, v -> lc)；

    第二次，①.判断u和v均为非空指针 ②u指向节点的priority=12，v vv指向节点的priority=18，则u uu应该作为新根节点，v与u的右子树执行合并，执行merge(u -> rc, v)；

    第三次，①.判断u为空指针，则返回v指针，此后逐层返回。

    如此，两个树就重新合并在了一起。
    在这里插入图片描述

    四、AVL树

    1. AVL树的性质

    1. 可以是一棵空树
    2. 左子树和右子树高度之差的绝对值不超过1（左右子树的高度差可以为0、1和 -1）
    3. 左子树和右子树均为平衡二叉树

    2.为什么平衡二叉树是二叉搜索树？

    之前学习二叉搜索树的时候，最坏的时间复杂度为O(n)，如果二叉搜索树尽可能的平衡，它的时间复杂度就会转换为O(logN)，这就是平衡二叉树是基于二叉搜索树提出来的原因

    3.平衡因子与最小不平衡子树

    平衡因子：在AVL树中，要求树之间的高度差不超过1，所以平衡因子<=1

    最小不平衡子树：导致树变成不平衡的条件

    4. 平衡二叉树的左旋与右旋

    4.1右旋

    使用场景：LL

    实现过程：

    ①将58作为根节点抽出来

    ②把根节点的左子树向上移动，根节点顺势成为其左子树的右子树

    ③此时根节点会和左子树的原来的右子树冲突，将左子树的原来的右子树变为现在根节点的左子树即可

     新插入节点37的插入位置：根节点58的左儿子的左子树上，这种情况称为LL

    4.2 左旋

    使用场景：RR

    实现过程：

    ①将根节点向左下方移动

    ②将根节点的右子树向左上方移动变为其根节点

    ③将现在根节点（15）原来的左子树（13）变为原来根节点（12）的右子树并将原来的根节点变为现在的根节点的左子树

    新插入节点18的位置：根节点12的右儿子的右子树，这种情况称为RR

    4.3 先左旋再右旋

    使用场景：LR

    实现过程：

    ①将根节点的左子树整体进行左旋

    ②将树整体进行右旋

    新的节点插入在左子树的右子树上称为LR

     4.4先右旋再左旋

    使用场景：RL

    ①将右子树右旋

    ②整棵树左旋

     新插入的节点在右子树的左子树上称为RL

    五、Splay树

    splay树是平衡树的一种，中文叫做伸展树

    它的主要思想是：对于查找频率较高的节点，使其处于离根节点相对较近的节点。

    1. 什么是查找频率最高的节点？

    你可以认为每次被查找的点查找频率相对较高，说白了就是你把每次查找到的点搬到根节点去

    当然你也可以每次查找之后随机一个点作为根，于是Treaplay这种数据结构就诞生啦

    2. 怎么实现把每次查找的点搬到根节点上面去？

    这是Splay需要解决的问题

    3. Splay的基本操作

    splay规定：每访问一个节点后都要强制将其旋转到根节点

    3.1 我们要把一个点挪到根，那我们首先要知道怎么让一个点挪到它的父节点

    情况一：当X为Y的左孩子

     这个时候，我们让X成为Y的父亲节点，其实就类似于AVL树的右旋，操作后结果如下所示

     情况二：X是Y的右孩子

    类似于AVL的左旋 

     情况三：当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。

    当x和p同为左孩子时，依次将p和x右旋；

    情况四：当p不是根节点，且x和p同为左孩子或右孩子时进行Zig-Zig操作。

    当x和p同为右孩子时，依次将p和x左旋。

    情况五：当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。

    当p为左孩子，x为右孩子时，将x左旋后再右旋。

    情况六：当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。

    当p为右孩子，x为左孩子时，将x右旋后再左旋。

  • 相关阅读:
    java成员等讲解
    JavaScript 奇怪又实用的姿势又增加了六个
    nodejs+vue交通违章查询及缴费elementui
    golang反射
    idea显示git分支信息(GitToolBox插件)
    PC_访存过程@内存地址翻译过程@具有快表TLB和cache的多级存储系统
    数据库原理及应用实验报告-实验10-触发器
    java保留两位小数4种方法
    分布式链路追踪系统Skywalking的部署和应用
    逻辑漏洞---登录验证码安全
  • 原文地址：https://blog.csdn.net/young_man2/article/details/125900973