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