文件乱码了怎么恢复_上海新增感染呈下降趋势_百度在线客服中心_市场推广渠道有哪些

一、二叉平衡树

上一章所示的同一组元素按照不同顺序插入到二叉排序树中可能会产生两种形状不同的二叉排序树。
在这里插入图片描述
当出现右边的情况时，树的高度过高，如果要查找值为“70”的节点需要查找7次，其查找次数已经接近于链表了，这样会导致查找效率过低。为了防止右图这种较为极端的情况出现，一种新的二叉树-二叉平衡树（AVL树）被提出了。

AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基（Adelson-Velsky）和叶夫根尼·兰迪斯（E.M. Landis），是他们名字的缩写。Adelson-Velsky和E.M. Landis在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

介绍这一数据结构之前，首先介绍一下平衡因子的概念：
平衡因子=左子树高-右子树高。

AVL树本质上是一棵空树或左右两个子树的高度差的绝对值不超过1的二叉查找树，同时它的左右两个子树也都是一棵平衡二叉树。

查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

其特点如下：
1.它和它的子树必须是一棵空树或左右两个子树的高度差的绝对值不超过1，即平衡因子的绝对值小于等于1。平衡二叉树结点的平衡因子的值只可能是−1、0或1。
2.它必须是一颗二叉查找树
在这里插入图片描述
由平衡二叉树的特点可以得到，上图中左侧为平衡二叉树，右侧不是平衡二叉树。

二、二叉平衡树的操作

1.查找

可以像普通二叉查找树一样的进行，所以耗费O(log n)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。

    // 查找与val数值相等的节点public TreeNode get(int val) {return get(root, val);}public TreeNode get(TreeNode currentNode, int val) {TreeNode findTreeNode = new TreeNode();while (currentNode != null) {if (currentNode.val > val) { // 当前节点比将要插入的值大currentNode = currentNode.left; // 去根节点左子树中继续寻找} else if (currentNode.val < val) { // 当前节点比将要插入的值小currentNode = currentNode.right; // 去根节点右子树中继续寻找} else if (currentNode.val == val)  {findTreeNode = currentNode; //相等，则currentNode是要寻找的节点。System.out.println(findTreeNode.val + " has been found!");return findTreeNode;}}System.out.println("Error! " + val + " does not exist!");return null;}

2.插入

二叉平衡树的插入可以像二叉查找树一样的进行，但是插入新节点后新的二叉树可能会失去平衡。如下图所示，插入节点67后，二叉树进入失衡状态。如何继续保持平衡？
在这里插入图片描述
想要对插入后的二叉树进行平衡，首先要了解以下概念：

最小不平衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过1的结点为根的子树称为最小不平衡子树。
在上图中，以70节点作为根节点的子树，即为最小不平衡子树。

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。如下所示：
在这里插入图片描述

	public void insert(int val) {root = insert(root, val);}// 将结点插入到AVL树中，并返回根节点private TreeNode insert(TreeNode tree, int val) {if (tree == null) {// 新建节点tree = new TreeNode(val);if (tree==null) {System.out.println("ERROR: create avltree node failed!");return null;}} else {if (val< tree.val) {    // 应该将key插入到"tree的左子树"的情况tree.left = insert(tree.left, val);// 插入节点后，若AVL树失去平衡，则进行相应的调节。if (height(tree.left) - height(tree.right) == 2) {if (val < tree.left.val)tree = leftLeftRotation(tree);elsetree = leftRightRotation(tree);}} else if (val > tree.val) {    // 应该将key插入到"tree的右子树"的情况tree.right = insert(tree.right, val);// 插入节点后，若AVL树失去平衡，则进行相应的调节。if (height(tree.right) - height(tree.left) == 2) {if (val > tree.right.val)tree = rightRightRotation(tree);elsetree = rightLeftRotation(tree);}} else {    // val == tree.valSystem.out.println("添加失败: 不允许添加相同的节点！");}}tree.height = Math.max( height(tree.left), height(tree.right)) + 1;return tree;}

3.调整最小不平衡子树

调整最小不平衡子树即可使二叉树恢复平衡，可以通过四种旋转操作调整不平衡子树。

1）LL平衡旋转（右单旋转）

LL 是指在节点A 左孩子（L）的左子树（L）插入了新节点，导致A节点失衡的节点是A节点的左子树的左子树。

A的平衡因子由1增至2，导致以A为根的子树失去平衡，对于 LL 型，需要执行右旋转操作。

将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

在这里插入图片描述
如上图所示，左中右三个二叉树依次是：插入节点前的平衡二叉树、插入节点后失衡的二叉树、旋转后恢复平衡的二叉平衡树。

	// 左旋转public TreeNode leftRotation(TreeNode k2) {TreeNode k1;k1 = k2.left;k2.left = k1.right;k1.right = k2;k2.height = Math.max(height(k2.left), height(k2.right)) + 1;k1.height = Math.max(height(k1.left), k2.height) + 1;return k1;}// LL: 左左对应的情况(左单旋转)。public TreeNode leftLeftRotation(TreeNode k1) {return leftRotation(k1);}

2）RR平衡旋转（左单旋转）

RR是指在节点A 右孩子（R）的右子树（R）插入了新节点，导致A节点失衡的节点是A节点的右子树的右子树。

A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，对于 RR 型，需要执行左旋转操作。

将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。
在这里插入图片描述
如上图所示，左中右三个二叉树依次是：插入节点前的平衡二叉树、插入节点后失衡的二叉树、旋转后恢复平衡的二叉平衡树。

	// 右旋转public TreeNode rightRotation(TreeNode k1) {TreeNode k2;k2 = k1.right;k1.right = k2.left;k2.left = k1;k1.height = Math.max(height(k1.left), height(k1.right)) + 1;k2.height = Math.max(height(k2.right), k1.height) + 1;return k2;}// RR: 右右对应的情况(右单旋转)。public TreeNode rightRightRotation(TreeNode k1) {return rightRotation(k1);}

3）LR平衡旋转（先左后右旋转）

LR 是指在节点A 左孩子（L）的右子树（R）插入了新节点，导致A节点失衡的节点是A节点的左子树的右子树。

A的平衡因子由1增至2，导致以A为根的子树失去平衡，对于 LR 型，需要先执行左旋转再执行右旋转操作。

先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。
在这里插入图片描述
如上图所示，左中右三个二叉树依次是：插入节点前的平衡二叉树、插入节点后失衡的二叉树、旋转后恢复平衡的二叉平衡树。

两次旋转的拆解过程如下：
在这里插入图片描述

	// 左旋转public TreeNode leftRotation(TreeNode k2) {TreeNode k1;k1 = k2.left;k2.left = k1.right;k1.right = k2;k2.height = Math.max(height(k2.left), height(k2.right)) + 1;k1.height = Math.max(height(k1.left), k2.height) + 1;return k1;}// 右旋转public TreeNode rightRotation(TreeNode k1) {TreeNode k2;k2 = k1.right;k1.right = k2.left;k2.left = k1;k1.height = Math.max(height(k1.left), height(k1.right)) + 1;k2.height = Math.max(height(k2.right), k1.height) + 1;return k2;}// LR: 左右对应的情况(左双旋转)。public TreeNode leftRightRotation(TreeNode k1) {k1.left = rightRotation(k1.left);return leftRotation(k1);}

4）RL平衡旋转（先右后左旋转）

RL 是指在节点A 右孩子（R）的左子树（L）插入了新节点，导致A节点失衡的节点是A节点的右子树的左子树。

A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，对于RL 型，需要先执行右旋转再执行左旋转操作。
先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。
在这里插入图片描述
如上图所示，左中右三个二叉树依次是：插入节点前的平衡二叉树、插入节点后失衡的二叉树、旋转后恢复平衡的二叉平衡树。