14.平衡二叉树（AVL树）
一.将二叉搜索树变平衡
1.题目描述：
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，请你返回任意一种。
2.示例：
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
3.解：
（1）我的答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode tempRoot = null;
private HashMap<TreeNode, Integer> heightSet = new HashMap<>();
public TreeNode balanceBST(TreeNode root) {
if (root == null) return null;
else midTravel(root);
return tempRoot;
}
private void midTravel(TreeNode root) {
if (root.left != null) midTravel(root.left);
tempRoot = insert(tempRoot, root.val);
if (root.right != null) midTravel(root.right);
}
private void updateHeight(TreeNode root) {
heightSet.put(root, Math.max(heightSet.getOrDefault(root.left, 0), heightSet.getOrDefault(root.right, 0)) + 1);
}
private TreeNode RR(TreeNode root) {
TreeNode newRoot = root.right;
root.right = newRoot.left;
newRoot.left = root;
updateHeight(root);
updateHeight(newRoot);
return newRoot;
}
private TreeNode RL(TreeNode root) {
root.right = LL(root.right);
return RR(root);
}
private TreeNode LR(TreeNode root) {
root.left = RR(root.left);
return LL(root);
}
private TreeNode LL(TreeNode root) {
TreeNode newRoot = root.left;
root.left = newRoot.right;
newRoot.right = root;
updateHeight(root);
updateHeight(newRoot);
return newRoot;
}
private TreeNode insert(TreeNode root, int val) {
//插入节点
if (root == null) {
root = new TreeNode(val);
} else if (val < root.val) {
root.left = insert(root.left, val);
if (heightSet.getOrDefault(root.left, 0) - heightSet.getOrDefault(root.right, 0) == 2) {
if (val < root.left.val) root = LL(root);
if (val > root.left.val) root = LR(root);
}
} else if (val > root.val) {
root.right = insert(root.right, val);
if (heightSet.getOrDefault(root.right, 0) - heightSet.getOrDefault(root.left, 0) == 2) {
if (val < root.right.val) root = RL(root);
if (val > root.right.val) root = RR(root);
}
} else if (val == root.val) {
System.out.println("已存在该节点，无法插入");
}
updateHeight(root);
return root;
}
}
4.总结
（1）原理
插入一个节点按照如下基本步骤进行：
按照二叉搜索树的方式增加节点，新增节点称为一个叶节点。
从新增节点开始，回溯到第一个失衡节点(5)。(如果回溯到根节点，还没有失衡节点，就说明该树已经符合AVL性质。)
找到断的边(5->3)，并确定断弦的方向(5的左侧)
以断边下端(3)为根节点，确定两个子树中的哪一个深度大(左子树还是右子树)。(这两棵子树的深度不可能相等，而且深度大的子树包含有新增节点。想想为什么)
如果第2和第3步中的方向一致(都为左或者都为右)，需要单旋转以失衡节点为根节点的子树。否则，双旋转以失衡节点为根节点的子树。（掌握LL，RR,LR,RL四种失衡情况下怎么进行旋转操作。）
原理链接
https://www.cnblogs.com/vamei/archive/2013/03/21/2964092.htm
（2）AVL树的实现和功能性操作：
public class AVLTree<T extends Comparable<T>> {
private AVLTreeNode<T> mRoot; // 根结点
// AVL树的节点(内部类)
class AVLTreeNode<T extends Comparable<T>> {
T key; // 关键字(键值)
int height; // 高度
AVLTreeNode<T> left; // 左孩子
AVLTreeNode<T> right; // 右孩子
public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
this.height = 0;
}
}
// 构造函数
public AVLTree() {
mRoot = null;
}
/*
* 获取树的高度
*/
private int height(AVLTreeNode<T> tree) {
if (tree != null)
return tree.height;
return 0;
}
public int height() {
return height(mRoot);
}
/*
* 比较两个值的大小
*/
private int max(int a, int b) {
return a>b ? a : b;
}
/*
* 前序遍历"AVL树"
*/
private void preOrder(AVLTreeNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍历"AVL树"
*/
private void inOrder(AVLTreeNode<T> tree) {
if(tree != null)
{
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 后序遍历"AVL树"
*/
private void postOrder(AVLTreeNode<T> tree) {
if(tree != null) {
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (递归实现)查找"AVL树x"中键值为key的节点
*/
private AVLTreeNode<T> search(AVLTreeNode<T> x, T key) {
if (x==null)
return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
return search(x.left, key);
else if (cmp > 0)
return search(x.right, key);
else
return x;
}
public AVLTreeNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非递归实现)查找"AVL树x"中键值为key的节点
*/
private AVLTreeNode<T> iterativeSearch(AVLTreeNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
else
return x;
}
return x;
}
public AVLTreeNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小结点：返回tree为根结点的AVL树的最小结点。
*/
private AVLTreeNode<T> minimum(AVLTreeNode<T> tree) {
if (tree == null)
return null;
while(tree.left != null)
tree = tree.left;
return tree;
}
public T minimum() {
AVLTreeNode<T> p = minimum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* 查找最大结点：返回tree为根结点的AVL树的最大结点。
*/
private AVLTreeNode<T> maximum(AVLTreeNode<T> tree) {
if (tree == null)
return null;
while(tree.right != null)
tree = tree.right;
return tree;
}
public T maximum() {
AVLTreeNode<T> p = maximum(mRoot);
if (p != null)
return p.key;
return null;
}
/*
* LL：左左对应的情况(左单旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
AVLTreeNode<T> k1;
k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height(k2.left), height(k2.right)) + 1;
k1.height = max( height(k1.left), k2.height) + 1;
return k1;
}
/*
* RR：右右对应的情况(右单旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
AVLTreeNode<T> k2;
k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height(k1.left), height(k1.right)) + 1;
k2.height = max( height(k2.right), k1.height) + 1;
return k2;
}
/*
* LR：左右对应的情况(左双旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
k3.left = rightRightRotation(k3.left);
return leftLeftRotation(k3);
}
/*
* RL：右左对应的情况(右双旋转)。
*
* 返回值：旋转后的根节点
*/
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
k1.right = leftLeftRotation(k1.right);
return rightRightRotation(k1);
}
/*
* 将结点插入到AVL树中，并返回根节点
*
* 参数说明：
* tree AVL树的根结点
* key 插入的结点的键值
* 返回值：
* 根节点
*/
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
if (tree == null) {
// 新建节点
tree = new AVLTreeNode<T>(key, null, null);
if (tree==null) {
System.out.println("ERROR: create avltree node failed!");
return null;
}
} else {
int cmp = key.compareTo(tree.key);
if (cmp < 0) { // 应该将key插入到"tree的左子树"的情况
tree.left = insert(tree.left, key);
// 插入节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.left) - height(tree.right) == 2) {
if (key.compareTo(tree.left.key) < 0)
tree = leftLeftRotation(tree);
else
tree = leftRightRotation(tree);
}
} else if (cmp > 0) { // 应该将key插入到"tree的右子树"的情况
tree.right = insert(tree.right, key);
// 插入节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.right) - height(tree.left) == 2) {
if (key.compareTo(tree.right.key) > 0)
tree = rightRightRotation(tree);
else
tree = rightLeftRotation(tree);
}
} else { // cmp==0
System.out.println("添加失败：不允许添加相同的节点！");
}
}
tree.height = max( height(tree.left), height(tree.right)) + 1;
return tree;
}
public void insert(T key) {
mRoot = insert(mRoot, key);
}
/*
* 删除结点(z)，返回根节点
*
* 参数说明：
* tree AVL树的根结点
* z 待删除的结点
* 返回值：
* 根节点
*/
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
// 根为空 或者 没有要删除的节点，直接返回null。
if (tree==null || z==null)
return null;
int cmp = z.key.compareTo(tree.key);
if (cmp < 0) { // 待删除的节点在"tree的左子树"中
tree.left = remove(tree.left, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.right) - height(tree.left) == 2) {
AVLTreeNode<T> r = tree.right;
if (height(r.left) > height(r.right))
tree = rightLeftRotation(tree);
else
tree = rightRightRotation(tree);
}
} else if (cmp > 0) { // 待删除的节点在"tree的右子树"中
tree.right = remove(tree.right, z);
// 删除节点后，若AVL树失去平衡，则进行相应的调节。
if (height(tree.left) - height(tree.right) == 2) {
AVLTreeNode<T> l = tree.left;
if (height(l.right) > height(l.left))
tree = leftRightRotation(tree);
else
tree = leftLeftRotation(tree);
}
} else { // tree是对应要删除的节点。
// tree的左右孩子都非空
if ((tree.left!=null) && (tree.right!=null)) {
if (height(tree.left) > height(tree.right)) {
// 如果tree的左子树比右子树高；
// 则(01)找出tree的左子树中的最大节点
// (02)将该最大节点的值赋值给tree。
// (03)删除该最大节点。
// 这类似于用"tree的左子树中最大节点"做"tree"的替身；
// 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
AVLTreeNode<T> max = maximum(tree.left);
tree.key = max.key;
tree.left = remove(tree.left, max);
} else {
// 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
// 则(01)找出tree的右子树中的最小节点
// (02)将该最小节点的值赋值给tree。
// (03)删除该最小节点。
// 这类似于用"tree的右子树中最小节点"做"tree"的替身；
// 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
AVLTreeNode<T> min = maximum(tree.right);
tree.key = min.key;
tree.right = remove(tree.right, min);
}
} else {
AVLTreeNode<T> tmp = tree;
tree = (tree.left!=null) ? tree.left : tree.right;
tmp = null;
}
}
return tree;
}
public void remove(T key) {
AVLTreeNode<T> z;
if ((z = search(mRoot, key)) != null)
mRoot = remove(mRoot, z);
}
/*
* 销毁AVL树
*/
private void destroy(AVLTreeNode<T> tree) {
if (tree==null)
return ;
if (tree.left != null)
destroy(tree.left);
if (tree.right != null)
destroy(tree.right);
tree = null;
}
public void destroy() {
destroy(mRoot);
}
/*
* 打印"二叉查找树"
*
* key -- 节点的键值
* direction -- 0，表示该节点是根节点;
* -1，表示该节点是它的父结点的左孩子;
* 1，表示该节点是它的父结点的右孩子。
*/
private void print(AVLTreeNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根节点
System.out.printf("%2d is root\n", tree.key, key);
else // tree是分支节点
System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null)
print(mRoot, mRoot.key, 0);
}
}
（3）测试程序
== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
== 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
== 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
== 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
== 高度: 5
== 最小值: 1
== 最大值: 16
== 树的详细信息:
7 is root
4 is 7's left child
2 is 4's left child
1 is 2's left child
3 is 2's right child
6 is 4's right child
5 is 6's left child
13 is 7's right child
11 is 13's left child
9 is 11's left child
8 is 9's left child
10 is 9's right child
12 is 11's right child
15 is 13's right child
14 is 15's left child
16 is 15's right child
== 删除根节点: 8
== 高度: 5
== 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16
== 树的详细信息:
7 is root
4 is 7's left child
2 is 4's left child
1 is 2's left child
3 is 2's right child
6 is 4's right child
5 is 6's left child
13 is 7's right child
11 is 13's left child
9 is 11's left child
10 is 9's right child
12 is 11's right child
15 is 13's right child
14 is 15's left child
16 is 15's right child
腾讯云智研发成长空间 5079人发布