树
1. 顺序存储结构二叉树
顺序存储结构的二叉树：用一组连续的存储单元来存放二叉树中的结点
public class ArrayBinaryTree {
int[] container;
public ArrayTree(int[] container) {
this.container = container;
}
// i的父节点
public int parent(int i) {
return (i - 1) / 2;
}
// i的左孩子
public int left(int i) {
return 2 * i + 1;
}
// i的右孩子
public int right(int i) {
return 2 * i + 2;
}
// 先序遍历
public void preorder(int index) {
if (container == null || container.length == 0)
return;
System.out.println(container[index]);
if (left(index) < container.length)
preorder(left(index));
if (right(index) < container.length)
preorder(right(index));
}
// 中序遍历
public void inorder(int index) {
if (container == null || container.length == 0)
return;
if (left(index) < container.length)
inorder(left(index));
System.out.println(container[index]);
if (right(index) < container.length)
inorder(right(index));
}
// 后序遍历
public void postorder(int index) {
if (container == null || container.length == 0)
return;
if (left(index) < container.length)
postorder(left(index));
if (right(index) < container.length)
postorder(right(index));
System.out.println(container[index]);
}
}
2. 链式存储结构二叉树
链式存储结构的二叉树：用链表来存放二叉树中的结点
从递归执行过程的角度看，先序、中序和后序遍历是完全相同的
由二叉树的先序序列和中序序列，或后序序列和中序序列，或层序序列和中序序列，可以唯一地确定一颗二叉树；先序或后序可以确定根节点，在中序中可以根据根节点来确定其左右子树
import java.util.LinkedList;
public class LinkedBinaryTree<E> {
BiTNode<E> root;
static class BiTNode<E> {
E data;
BiTNode<E> left;
BiTNode<E> right;
public BiTNode(E data, BiTNode<E> left, BiTNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
// 递归先序遍历
public void preOrder(BiTNode<E> root) {
if (root != null) {
System.out.println(root.data);
preOrder(root.left);
preOrder(root.right);
}
}
// 递归中序遍历
public void inOrder(BiTNode<E> root) {
if (root != null) {
inOrder(root.left);
System.out.println(root.data);
inOrder(root.right);
}
}
// 递归后序遍历
public void postOrder(BiTNode<E> root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
System.out.println(root.data);
}
}
// 借助栈，非递归先序遍历
// 先序遍历和中序遍历思想类似，只需把访问结点的操作放在入栈之前
public void preOrderByStack(BiTNode<E> root) {
// 初始化一个栈
LinkedList<BiTNode<E>> stack = new LinkedList<>();
// current指向当前遍历的结点
BiTNode<E> current = root;
// 当current不为空，或栈不为空时循环
while (current != null || !stack.isEmpty()) {
if (current != null) { // 一路向左
System.out.println(current.data);
stack.push(current);
// 向左子树走
current = current.left;
} else { // 出栈，并转向出栈结点的右子树
current = stack.pop();
// 向右子树走
current = current.right;
}
}
}
// 借助栈，非递归中序遍历
public void inOrderByStack(BiTNode<E> root) {
// 初始化一个栈
LinkedList<BiTNode<E>> stack = new LinkedList<>();
// current指向当前遍历的结点
BiTNode<E> current = root;
// 当current不为空，或栈不为空时循环
while (current != null || !stack.isEmpty()) {
if (current != null) { // 一路向左
stack.push(current);
// 向左子树走
current = current.left;
} else { // 出栈，并转向出栈结点的右子树
current = stack.pop();
System.out.println(current.data);
// 向右子树走
current = current.right;
}
}
}
/**
* 借助栈，非递归后序遍历：
* 从根节点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，
* 但是此时还不能出栈访问，因为如果其有右子树，还需按相同的规则对右子树进行处理。
* 若栈顶元素想要出栈被访问，则其右子树需为空或刚被访问完
*/
public void postOrderByStack(BiTNode<E> root) {
// 初始化一个栈
LinkedList<BiTNode<E>> stack = new LinkedList<>();
// current指向当前遍历的结点
BiTNode<E> current = root;
// visited指向最近访问过的结点，用以分清返回时是从哪个子树返回的
BiTNode<E> visited = null;
while (current != null || !stack.isEmpty()) {
if (current != null) { // 走到最左边
stack.push(current);
current = current.left;
} else { // 向右
// 读取栈顶元素
current = stack.peek();
// 若有右子树，且未被访问过
if (current.right != null && current.right != visited) {
// 转向右子树
current = current.right;
stack.push(current);
// 再走向右子树的左边
current = current.left;
} else { // 没有右子树，或右子树已经被访问了
// 将栈顶元素出栈，并访问
current = stack.pop();
System.out.println(current.data);
// 记录最近访问过的结点
visited = current;
// 右子树已访问(此时左子树早已访问完)，则下一轮该从栈顶取出中间元素来访问，
// 因此置为空，不用再先走到最左边
current = null;
}
}
}
}
/**
* 借助队列，层次遍历：
* 初始化将二叉树根节点入队
* 每次出队一个结点并访问，直到队列为空
* 若它有左子树，则将左子树根节点入队；
* 若它有右子树，则将右子树根节点入队。
*/
public void levelOrder(BiTNode<E> root) {
// 初始化一个队列
LinkedList<BiTNode<E>> queue = new LinkedList<>();
// current指向当前遍历的结点
BiTNode<E> current = root;
// 将根节点入队
queue.addLast(current);
// 队列不为空则循环
while (!queue.isEmpty()) {
// 队头结点出队，并访问
current = queue.removeFirst();
System.out.println(current.data);
// 若有左子树，则将左子树根节点入队
if (current.left != null)
queue.addLast(current.left);
// 若有右子树，则将右子树根节点入队
if (current.right != null)
queue.addLast(current.right);
}
}
// 根据二叉树的先序序列和中序序列建立其二叉链表
// preFirst和preLast为先序的第一个和最后一个结点的下标
// inFirst和inLast为中序的第一个和最后一个结点的下标
// 初始时：preFirst = inFirst = 0; preLast = inLast = length - 1;
public BiTNode<E> createByPreAndIn(E[] pre, E[] in, int preFirst, int preLast, int inFirst, int inLast) {
// 建立根节点
BiTNode<E> root = new BiTNode<>(pre[preFirst], null, null);
// 寻找根节点在中序序列中的位置
int i = inFirst;
while (!in[i].equals(root.data))
i++;
// 左子树长度
int lLen = i - inFirst;
// 右子树长度
int rLen = inLast - i;
// 递归建立左子树
if (lLen != 0)
root.left = createByPreAndIn(pre, in, preFirst + 1, preFirst + lLen, inFirst, inFirst + lLen - 1);
else
root.left = null;
// 递归建立右子树
if (rLen != 0)
root.right = createByPreAndIn(pre, in, preLast - rLen + 1, preLast, inLast - rLen + 1, inLast);
else
root.right = null;
return root;
}
}
3. 线索二叉树
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。二叉树的线索化是将二叉树中的空指针改为指向前驱或后继的线索。而前驱或后继信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
当线索化二叉树后，节点的属性left和right有如下情况：
- left指向的是左子树，也可能是指向的前驱节点
- right指向的是右子树，也可能是指向后继节点
public class ThreadedBinaryTree<E> {
BiTNode<E> root;
BiTNode<E> prev = null;
static class BiTNode<E> {
E data;
BiTNode<E> left;
BiTNode<E> right;
// lTag为0则指向左子树，为1则指向前驱节点
int lTag;
// rTag为0则指向右子树，为1则指向后继节点
int rTag;
public BiTNode(E data, BiTNode<E> left, BiTNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
/**
* 通过中序遍历，对二叉树递归地线索化：
* root指向正在访问的结点
* prev指向刚刚访问过的结点，即prev指向root的前驱
* 在中序遍历过程中：
* 若root的左子树为空，则将root的左指针指向prev(即建立前驱线索)，
* 若prev的右子树为空，则将prev的右指针指向root(即建立后继线索)
*/
private void inThread(BiTNode<E> root) {
if (root != null) {
// 递归，线索化左子树
inThread(root.left);
// 建立前驱线索
if (root.left == null) {
root.left = prev;
root.lTag = 1;
}
// 建立前驱结点的后继线索
if (prev != null && prev.right == null) {
prev.right = root;
prev.rTag = 1;
}
// prev若作为方法参数在递归中传递，则不能写prev = root，因为会引发在递归调用里修改引用无效的问题
// 标记当前结点为刚刚访问过的结点
prev = root;
// 递归，线索化右子树
inThread(root.right);
}
}
// 建立中序线索二叉树
public void createInThread(BiTNode<E> root) {
if (root != null) {
// 将二叉树线索化
inThread(root);
// 处理遍历的最后一个结点的后继
prev.right = null;
prev.rTag = 1;
}
}
// 在中序线索二叉树中，获取中序序列中的第一个结点
private BiTNode<E> firstInNode(BiTNode<E> root) {
while (root.lTag == 0)
root = root.left;
return root;
}
// 在中序线索二叉树中，获取中序序列中node结点的后继
private BiTNode<E> nextInNode(BiTNode<E> node) {
if (node.rTag == 0)
// 返回后继
return firstInNode(node.right);
else
// rTag == 1，直接返回后继
return node.right;
}
// 利用firstInNode和nextInNode方法，实现中序线索二叉树的中序遍历
public void inOrder(BiTNode<E> root) {
BiTNode<E> current = firstInNode(root);
while (current != null) {
System.out.println(current.data);
// 将current设为其在中序序列中的后继
current = nextInNode(current);
}
}
}
4. 哈夫曼树
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度(WPL)最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
若规定根节点层数为1，则从根结点到第L层结点路径长度为L-1。
结点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积。
树的带权路径长度为：所有叶子结点的带权路径长度之和。
给定n个权值分别为w1，w2，...，wn的结点，构造哈夫曼树的过程如下：
- 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
- 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和
- 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
- 重复步骤2和3，直至F中只剩下一棵树为止
哈夫曼树的特点：
- 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
- 构造过程中共新建了n-1个结点(双分支结点)，因此哈夫曼树中的结点总数为2n-1
- 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点
前缀编码：是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。
哈夫曼编码是可变字长编码(VLC)的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。
由哈夫曼树构造哈夫曼编码：将每个出现的字符当作一个独立的结点，其权值为它出现的频度，构造出对应的哈夫曼树。可以将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为0表示"转向左孩子”，标记为1表示“转向右孩子”。
import java.util.*;
/**
* 创建哈夫曼树相关方法：getNodeList、createHuffmanTree
* 获取哈夫曼编码相关方法：generateHuffmanCode、getHuffmanCode
* 使用哈夫曼编码表编码(压缩)相关方法：encode
* 使用哈夫曼编码表解码(解压)相关方法：decode、byteToBinaryString
*/
public class HuffmanTree {
private static BiTNode root;
private static Map<Byte, String> huffmanCode = new HashMap<>();
private static class BiTNode {
Byte data;
int weights;
BiTNode left;
BiTNode right;
public BiTNode(Byte data, int weights, BiTNode left, BiTNode right) {
this.data = data;
this.weights = weights;
this.left = left;
this.right = right;
}
}
// 传递字节数组，统计各个字符出现次数作为权值，进而获取节点集合
private static LinkedList<BiTNode> getNodeList(byte[] bytes) {
// 节点集合
LinkedList<BiTNode> nodes = new LinkedList<>();
// 存储各个字符出现次数
HashMap<Byte, Integer> map = new HashMap<>();
// 统计每一个字符出现的次数
for (byte b : bytes) {
if (map.containsKey(b))
map.put(b, map.get(b) + 1);
else
map.put(b, 1);
}
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
nodes.add(new BiTNode(entry.getKey(), entry.getValue(), null, null));
}
return nodes;
}
// 给定权集，构造哈夫曼树
private static BiTNode createHuffmanTree(LinkedList<BiTNode> forest) {
while (forest.size() > 1) {
// 按权值从小到大排序
Collections.sort(forest, (o1, o2) -> o1.weights - o2.weights);
// 选取两棵根结点权值最小的树
BiTNode left = forest.removeFirst();
BiTNode right = forest.removeFirst();
// 构造一个新树，权值置为左、右子树上根结点的权值之和
BiTNode parent = new BiTNode(null, left.weights + right.weights, left, right);
// 将新得到的树加入森林中
forest.add(parent);
}
// 森林中仅剩下的一棵树就是哈夫曼树
return forest.removeFirst();
}
// 传递哈夫曼树，生成哈夫曼编码
private static void generateHuffmanCode(BiTNode node, String code, StringBuilder stringBuilder) {
// node不为空才处理
if (node != null) {
StringBuilder sb = new StringBuilder(stringBuilder);
sb.append(code);
if (node.data == null) { // 若是非叶子结点
generateHuffmanCode(node.left, "0", sb);
generateHuffmanCode(node.right, "1", sb);
} else { // 若是叶子结点
huffmanCode.put(node.data, sb.toString());
}
}
}
// 便于调用generateHuffmanCode方法
public static Map<Byte, String> getHuffmanCode(byte[] bytes) {
huffmanCode.clear();
LinkedList<BiTNode> nodeList = getNodeList(bytes);
root = createHuffmanTree(nodeList);
if (root != null) {
generateHuffmanCode(root.left, "0", new StringBuilder());
generateHuffmanCode(root.right, "1", new StringBuilder());
}
return huffmanCode;
}
// 传递原始数据的字节数组和对应的哈夫曼编码表，进行编码(压缩)
public static byte[] encode(byte[] source, Map<Byte, String> huffmanCode) {
// 将bytes转换为对应的哈弗曼编码字符串
StringBuilder code = new StringBuilder();
for (byte b : source) {
code.append(huffmanCode.get(b));
}
// 将code二进制字符串转换为byte数组
// int length = (code.length() + 7) / 8;
int length = (int) Math.ceil(code.length() / 8.0);
// 编码后的byte数组
byte[] encode = new byte[length];
// encode的索引
int index = 0;
for (int i = 0; i < code.length(); i += 8) {
String strByte;
if (i + 8 > code.length()) // 如果不够8位
strByte = code.substring(i);
else
strByte = code.substring(i, i + 8);
// 将strByte转成一个byte，存入到encode中
encode[index++] = (byte) Integer.parseInt(strByte, 2);
}
return encode;
}
// 传递压缩后的数据和对应的哈夫曼编码表，进行解码(解压)
public static byte[] decode(byte[] encode, Map<Byte, String> huffmanCode) {
// bytes对应的哈弗曼编码字符串
StringBuilder code = new StringBuilder();
for (int i = 0; i < encode.length; i++) {
boolean or = (i != encode.length - 1);
code.append(byteToBinaryString(or, encode[i]));
}
// 将哈夫曼编码表的键和值交换
Map<String, Byte> table = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCode.entrySet()) {
table.put(entry.getValue(), entry.getKey());
}
// 存放byte的集合
List<Byte> source = new ArrayList<>();
int index = 0;
while (index < code.length()) {
// 偏移量
int offset = 1;
// 是否添加
boolean add = false;
while (add == false) {
String key = code.substring(index, index + offset);
if (table.containsKey(key)) { // 匹配到了
add = true;
source.add(table.get(key));
} else // 没有匹配到
offset++;
}
index += offset;
}
// 将集合转为数组
byte[] result = new byte[source.size()];
for (int i = 0; i < source.size(); i++) {
result[i] = source.get(i);
}
return result;
}
public static String byteToBinaryString(boolean or, int b) {
if (or)
// 按位或，给其最高位补1
b |= 256;
// 获取b对应的二进制补码
String binaryString = Integer.toBinaryString(b);
if (or)
return binaryString.substring(binaryString.length() - 8);
return binaryString;
}
}
// 测试
class HuffmanTreeClient {
public static void main(String[] args) {
String data = "I love you";
byte[] source = data.getBytes();
Map<Byte, String> huffmanCode = HuffmanTree.getHuffmanCode(source);
byte[] encode = HuffmanTree.encode(source, huffmanCode);
byte[] decode = HuffmanTree.decode(encode, huffmanCode);
System.out.println(new String(source));
System.out.println(new String(decode));
System.out.println(new String(source).equals(new String(decode)));
System.out.println((source.length - encode.length) / (source.length + 0.0));
}
}
5. 二叉搜索树
二叉搜索树(Binary Search Tree)，又称二叉排序树(Binary Sort Tree)。
二叉搜索树要么是一棵空树，要么是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均不大于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均不小于它的根结点的值
- 左、右子树也分别为二叉搜索树
根据二叉搜索树的定义，左子树结点值<=根结点值<=右子树结点值，因此对二叉搜索树进行中序遍历，可以得到一个递增的有序序列。
public class BinarySearchTree {
BiTNode root;
static class BiTNode {
int data;
BiTNode parent;
BiTNode left;
BiTNode right;
public BiTNode(int data, BiTNode parent, BiTNode left, BiTNode right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
}
// 递归中序遍历
public void inOrder(BiTNode root) {
if (root != null) {
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
// 将结点插入到二叉搜索树
public void insert(BiTNode node) {
BiTNode current = null;
BiTNode leaf = root;
// 寻找在哪一个叶子结点下插入
while (leaf != null) {
// 记录当前结点
current = leaf;
if (node.data < leaf.data)
leaf = leaf.left;
else
leaf = leaf.right;
}
// leaf为null，则current为叶子结点，将node插入到current下
node.parent = current;
if (current == null) // 若树为空
root = node;
else if (node.data < current.data)
// node比这个叶子结点小，则挂左边
current.left = node;
else
// node比这个叶子结点大，则挂右边
current.right = node;
}
public void create(int[] sequence) {
for (int i = 0; i < sequence.length; i++) {
insert(new BiTNode(sequence[i], null, null, null));
}
}
// 递归，查找给定关键字的结点
public BiTNode find(BiTNode node, int key) {
if (node == null || key == node.data)
return node;
if (key < node.data)
return find(node.left, key);
else
return find(node.right, key);
}
// 非递归，查找给定关键字的结点
public BiTNode search(int key) {
BiTNode node = root;
while (node != null && key != node.data) {
if (key < node.data)
node = node.left;
else
node = node.right;
}
return node;
}
// 查找某一子树的最小结点
public BiTNode minimum(BiTNode tree) {
BiTNode node = tree;
// 最小结点在二叉搜索树的最左边
if (node != null) {
while (node.left != null)
node = node.left;
}
return node;
}
// 查找某一子树的最大结点
public BiTNode maximum(BiTNode tree) {
BiTNode node = tree;
// 最大结点在二叉搜索树的最右边
if (node != null) {
while (node.right != null)
node = node.right;
}
return node;
}
// 查找某一结点的中序后继结点
public BiTNode successor(BiTNode tree) {
BiTNode node = tree;
// 若其右子树不为空，则其后继为右子树中最小的结点
if (node.right != null)
return minimum(node.right);
BiTNode parent = node.parent;
// 从node开始沿树向上找，直到某一结点是其父节点的左子树
while (parent != null && node == parent.right) {
node = parent;
parent = node.parent;
}
// parent为空，则为树根
// node不是其父节点的右子树，则为其父节点的左子树
return parent;
}
// 查找某一结点的中序前驱结点
public BiTNode predecessor(BiTNode tree) {
BiTNode node = tree;
// 若其左子树不为空，则其前驱为左子树中最大的结点
if (node.left != null)
return maximum(node.left);
BiTNode parent = node.parent;
// 从node开始沿树向上找，直到某一结点是其父节点的右子树
while (parent != null && node == parent.left) {
node = parent;
parent = node.parent;
}
// parent为空，则为树根
// node不是其父节点的左子树，则为其父节点的右子树
return parent;
}
// 用replacement子树替换target子树，子树替换而非结点替换；便于删除时移动子树
private void transplant(BiTNode target, BiTNode replacement) {
if (target.parent == null)
// 需要被替换的是根节点
root = replacement;
else if (target == target.parent.left)
// 若target是其父节点的左孩子，则让replacement成为其父节点的左孩子
target.parent.left = replacement;
else
// 若target是其父节点的右孩子，则让replacement成为其父节点的右孩子
target.parent.right = replacement;
if (replacement != null)
// 若replacement非空，则其父节点为target的父节点
replacement.parent = target.parent;
}
/**
* 删除有三种基本情况：
* 1. target没有孩子结点：直接删除，用null替换
* 2. target只有一个孩子：用这个孩子来替换target
* 3. target有两个孩子：在其右子树中找最小的结点min，这个min没有左孩子
* 3.1 若min不是其右孩子，则先用min的右孩子替换min，再用min替换target
* 3.2 若min是其右孩子，则用min替换target
*/
public void delete(BiTNode target) {
if (target.left == null)
// 没有左孩子，则用右孩子来替换target
transplant(target, target.right);
else if (target.right == null)
// 没有右孩子，则用左孩子来替换target
transplant(target, target.left);
// 若没有孩子结点，则经过以上两步，其已被null替换
else {
// 在其右子树中找最小的结点min
BiTNode min = minimum(target.right);
// 若min不是其右孩子，则先用min的右孩子替换min
if (min.parent != target) {
transplant(min, min.right);
// 下面两步是将target的右子树挂到min的右边
min.right = target.right;
min.right.parent = min;
}
// 用min替换target
transplant(target, min);
// 下面两步是将target的左子树挂到min的左边
min.left = target.left;
min.left.parent = min;
}
}
}
6. AVL树
平衡树(Balance Tree)：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。常见的符合平衡树的有：红黑树、AVL树(二叉平衡搜索树)、B树(多路平衡搜索树)等。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡树结点的平衡因子的值只可能是-1、0、1。
红黑树和AVL树都是从二叉搜索树进化而来的平衡树。
| 平衡树类型 | 平衡度 | 调整频率 | 适用场景 |
|---|---|---|---|
| AVL树 | 高 | 高 | 查询多 |
| 红黑树 | 低 | 低 | 增删多 |
LL平衡旋转(右单旋转)：由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
- LL平衡旋转如下图：将B的右孩子挂到A的左孩子，然后将A挂到B的右孩子
RR平衡旋转(左单旋转)：由于在结点A的右孩子(R)的右子树(R)上插入了新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡，需要一次向左的旋转操作。
- RR平衡旋转如下图：将B的左孩子挂到A的右孩子，然后将A挂到B的左孩子
LR平衡旋转(先左后右双旋转)：由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
- LR平衡旋转如下图：将C的左孩子挂到B的右孩子，C的右孩子挂到A的左孩子，然后将B挂到C的左孩子，A挂到C的右孩子
RL平衡旋转(先右后左双旋转)：由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
- RL平衡旋转：将C的左孩子挂到A的右孩子，C的右孩子挂到B的左孩子，然后将A挂到C的左孩子，B挂到C的右孩子
