前言

没有必要过度关注本文中二叉树的增删改导致的结构改变，规则操作什么的了解一下就好，看不下去就跳过，本文过多的XX树操作图片纯粹是为了作为规则记录，该文章主要目的是增强下个人对各种常用XX树的设计及缘由的了解，也从中了解到常用的实现案例使用XX树实现的原因。

数据在计算机中的存储结构主要为顺序存储结构、链式存储结构、索引存储结构、散列存储结构，其中链式存储结构最常见的示例是链表与树，链式存储结构主要有以下特点：

• 优点：逻辑相邻的节点物理上不必相邻，插入、删除灵活，只需改变节点中的指针指向
• 缺点：存储空间利用率低，需通过指针维护节点间的逻辑关系；查找效率比顺序存储慢

度：当前节点下的子节点个数

二叉树

二叉树是每个节点最多有两个子树的树结构，左侧子树节点称为“左子树”（left subtree），右侧子树节点称为“右子树”（right subtree）。每个节点最多有2个子节点的树（即每个定点的度小于3）。

二叉树的特点

• 至少有一个节点(根节点)
• 每个节点最多有两颗子树，即每个节点的度小于3。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。

满二叉树

除了叶子节点外每一个节点都有两个子节点，且所有叶子节点都在二叉树的同一高度上。

image

完全二叉树

如果二叉树中除去底层节点后为满二叉树，且底层节点依次从左到右分布，则此二叉树被称为完全二叉树。

image

二叉查找树（Binary Search Tree - BST，又称二叉排序树、二叉搜索树）

二叉查找树根节点的值大于其左子树中任意一个节点的值，小于其右子树中任意一节点的值，且该规则适用于树中的每一个节点。

image

二叉查找树的查询效率介于O(log n)~O(n)之间，理想的排序情况下查询效率为O(log n),极端情况下BST就是一个链表结构(如下图)，此时元素查找的效率相等于链表查询O(n)。

image

二叉查找树需要注意的是删除节点操作时的不同情况，删除节点根据节点位置会有以下三种情况：

• 删除节点的度为0，则直接删除
• 删除节点的度为1，则该子节点替代删除节点
• 删除节点的度为2，则从左子树中寻找值最大的节点替代删除节点。对树结构改动最少、节点值最进行删除节点值的必然是左子树中的最大叶子节点值与右子树中的最小叶子节点值

为什么不用右子树中的最小叶子节点值取代删除节点？个人认为是为了维持范围值(纯属臆测)：

右子树中的最小叶子节点值大于删除节点左子树中的所有节点，但若该叶子节点比删除节点大很多，这将会大大扩大左子树的范围值，左子树可插入的范围值也会大大增大，对左子树的查询效率造成较大的影响 左子树中的最大叶子节点值也大于删除节点左子树中其它所有的节点，虽然是使用该节点替代删除节点会缩小的左子树的值范围，但也减少左子树的插入范围值，对左子树的查询影响不大

由上可以看出，二叉查找树(BST)无法根据节点的结构改变(添加或删除)动态平衡树的排序结构，也因此对某些操作的效率造成一定的影响，而AVL树在BST的结构特点基础上添加了旋转平衡功能解决了这些问题。

平衡二叉搜索树 (Balanced binary search trees,又称AVL树、平衡二叉查找树)

AVL树是最早被发明的自平衡二叉搜索树，树中任一节点的两个子树的高度差最大为1，所以它也被称为高度平衡树，其查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

平衡二叉搜索树由Adelson-Velskii和Landis在1962年提出,因此又被命名为AVL树。平衡因子(平衡系数)是AVL树用于旋转平衡的判断因子，某节点的左子树与右子树的高度(深度)差值即为该节点的平衡因子。

AVL树的特点

• 具有二叉查找树的特点(左子树任一节点小于父节点，右子树任一节点大于父节点)，任何一个节点的左子树与右子树都是平衡二叉树
• 任一节点的左右子树高度差小于1，即平衡因子为范围为[-1,1] 如上左图根节点平衡因子=1，为AVL树；右图根节点平衡因子=2，固非AVL树，只是BST。

为什么选择AVL树而不是BST？

大多数BST操作(如搜索、最大值、最小值、插入、删除等)的时间复杂度为O(h)，其中h是BST的高度。对于极端情况下的二叉树，这些操作的成本可能变为O(n)。如果确保每次插入和删除后树的高度都保持O(log n)，则可以保证所有这些操作的效率都是O(log n)。

节点插入、旋转

AVL树插入节点的如下：

1. 根据BST入逻辑将新节点插入树中
2. 从新节点往上遍历检查每个节点的平衡因子，若发现有节点平衡因子不在[-1,1]范围内(即失衡节点u)，则通过旋转重新平衡以u为根的子树

旋转的方式：

1. 左旋转：用于平衡RR情况，对失衡节点u(unbalanced)及子树进行左旋
2. 右旋转：用于平衡LL情况，对失衡节点u及子树进行右旋
3. 左右旋转：用于平衡LR情况，对失衡节点失衡u的左子节点ul左旋，再对失衡节点u右旋
4. 右左旋转：用于平衡情况，对失衡节点u失衡方向的右子节点ur右旋，再对失衡节点u左旋

LL - 插入节点是失衡节点u左子节点ul上的左子树节点

gif图中的高度是从叶子节点开始计算的，因为插入节点后是从下往上检测节点的平衡因子，所以叶子节点高度恒为1更方便平衡因子的运算

image

image

LR - 插入节点是失衡节点u左子节点ul上的右子树节点

image

image

RR - 插入节点是失衡节点u右子节点ur上的右子树节点

image

image

RL - 插入节点是失衡节点u右子节点ur上的左子树节点

image

image

规律总结：

• 失衡节点到其最底部叶子节点的高度不会超过4
• 失衡节点哪里不平衡就会往哪里的反向旋转
• 添加的节点到失衡节点的路径如果是一条直线(即LL或RR)，则只需对失衡节点u进行反向旋转
• 添加的节点到失衡节点的路径如果是一条曲线(即LR或RL)，则需先对该路径上失衡节点u的子节点(ul/ur)进行旋转，再对失衡节点进行旋转
• 失衡节点u旋转后会成为它原来子树(ul/ur)中的一颗子树，如果u旋转时替代u的子树已有u旋转方向上的子树，那么该子树会断裂成为u的子树(如下LR的u右旋，uls已有右子树T2，故会T2断裂以BST的规则重新插入成为u的子树)

<pre style="box-sizing: border-box; outline: none; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-numeric: inherit; font-variant-east-asian: inherit; font-weight: 400; font-stretch: inherit; font-size: 18px; line-height: inherit; font-family: couriernew, courier, monospace; vertical-align: baseline; color: rgb(93, 93, 93); letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">

作者：Java程序猿阿谷
链接：https://www.jianshu.com/p/ed7935fd510f
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。