二叉树学习笔记之树的旋转

简介: 树旋转(Tree rotation)是二叉树中的一种子树调整操作,每一次旋转并不影响对该二叉树进行中序遍历的结果。 树旋转通常应用于需要调整树的局部平衡性的场合。

树旋转(Tree rotation)是二叉树中的一种子树调整操作,每一次旋转并不影响对该二叉树进行中序遍历的结果。
树旋转通常应用于需要调整树的局部平衡性的场合。

左旋和右旋

树的旋转有两种基本的操作,即左旋(逆时针方向旋转)和右旋(顺时针方向旋转)。

树旋转包括两个不同的方式,分别是左旋转(以P为转轴)和右旋转(以Q为转轴)。两种旋转呈镜像,而且互为逆操作。

下图示意了两种树旋转过程中, 子树的初态和终态

        +---+                          +---+
        | Q |                          | P |
        +---+                          +---+
       /     \     right rotation     /     \
    +---+   +---+  ------------->  +---+   +---+
    | P |   | Z |                  | X |   | Q |
    +---+   +---+  <-------------  +---+   +---+
   /     \          left rotation         /     \
+---+   +---+                          +---+   +---+
| X |   | Y |                          | Y |   | Z |
+---+   +---+                          +---+   +---+

其中, 右旋转详细步骤如下图 R0, R1, R2 三个步骤所示, 左旋转则如 L0, L1, L2 三个步骤所示.

                                                                  __
                                                                 /  \
                                     +---+                      /  +---+
                                     | Q |                     /   | Q |
                           +---+     +---+              +---+ /    +---+
        +---+              | P |    /     \      R1     | P |/    /     \              +---+
        | Q |     R0       +---+   /     +---+ ----->   +---+    /     +---+   R2      | P |
        +---+   ----->    /     \ /      | Z |         /        /      | Z | ----->    +---+
       /     \         +---+   +---+     +---+      +---+    +---+     +---+          /     \
    +---+   +---+      | X |   | Y |                | X |    | Y |                 +---+   +---+
    | P |   | Z |      +---+   +---+                +---+    +---+                 | X |   | Q |
    +---+   +---+              __                                                  +---+   +---+
   /     \                    /  \                                                        /     \
+---+   +---+     L2       +---+  \                       +---+                L0      +---+   +---+
| X |   | Y |   <-----     | P |   \                      | P |              <-----    | Y |   | Z |
+---+   +---+              +---+    \ +---+      L1       +---+     +---+              +---+   +---+
                          /     \    \| Q |    <-----    /     \    | Q |
                       +---+     \    +---+           +---+     \   +---+
                       | X |      \        \          | X |      \ /     \
                       +---+     +---+    +---+       +---+     +---+   +---+
                                 | Y |    | Z |                 | Y |   | Z |
                                 +---+    +---+                 +---+   +---+


AVL树的调整

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。

 


目录
相关文章
|
4月前
|
存储 算法
算法编程(十):相交链表
算法编程(十):相交链表
35 0
|
6月前
|
存储 算法
【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历
【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历
|
2月前
|
算法 Java 测试技术
【广度优先搜索】【网格】【割点】1263. 推箱子
【广度优先搜索】【网格】【割点】1263. 推箱子
LeetCode-1145 二叉树着色游戏
LeetCode-1145 二叉树着色游戏
|
8月前
|
算法
当二叉树的树叶飘落:深入探究后序遍历
后序遍历是一种深度优先遍历(Depth-First Traversal)方法,它的特点是对于每个节点的访问顺序是从左子节点到右子节点,最后再访问节点本身。具体来说,后序遍历按照以下顺序访问节点:
47 0
|
10月前
Leecode543. 二叉树的直径
Leecode543. 二叉树的直径
23 0
|
11月前
图解LeetCode——1145. 二叉树着色游戏
图解LeetCode——1145. 二叉树着色游戏
85 0
进阶指南图论——闇の連鎖 I. 黑暗的锁链(树上差分+LCA)
进阶指南图论——闇の連鎖 I. 黑暗的锁链(树上差分+LCA)
139 0
|
存储 算法
树与图的存储算法模板
树与图的存储算法模板
59 0
|
算法 Go
第十一章 运用广度优先搜索走迷宫
广度优先搜索类似于树的层次遍历。从图中的某一顶点出发,遍历每一个顶点时,依次遍历其所有的邻接点,然后再从这些邻接点出发,同样依次访问它们的邻接点。按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到。
111 0
第十一章 运用广度优先搜索走迷宫