AVL(平衡二叉树)

AVL平衡树

最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

定义

1. 左右子树均为AVL树
2. 左右子树的高度差的绝对值不超过1

平衡二叉树

满二叉树一定是平衡二叉树，高度最低

完全二叉树也是平衡二叉树，叶子节点深度相差不为1

线段树也是平衡二叉树，叶子节点深度相差不为1

下图中看起来比较偏斜，但是符合定义 平衡二叉树的高度和节点数量之间的关系也是O(logn)的 如若此时加入节点2,7，则不再符合定义

那么，我们该如何调整呢?

1. 先标记节点高度

2. 计算平衡因子（节点左右的高度差）

3. 自平衡实现

自平衡实现

自平衡实现有很多情况，大致分为一下几种情况：LL，RR，RL，LR。

• 右旋转LL

插入的元素在不平衡节点的左侧的左侧

如何右旋转，x.right=y，y.left=T3 ；
旋转时注意不能改变原二分搜索树的性质 T1

• 左旋转RR

插入的元素在不平衡的节点的右侧的右侧

同右旋转

• LR

插入的元素在不平衡的节点的左侧的右侧

首先对x进行左旋转RR，再对y进行右旋转LL

• RL

插入的元素在不平衡的节点的右侧的左侧
先对x进行右旋转LL，在对y进行左旋转RR

• 删除节点之后的平衡

只需将删除节点后新树的根进行平衡操作即可。

源码

public class AVLTree<K extends Comparable<K>,V> implements Map<K, V> {private class Node{public K key;public V value;	public Node right,left;public int height;public Node(K key,V value) {this.key=key;this.value=value;right=null;left=null;height=1;}public Node(){this(null,null);}}private Node root;private int size;public AVLTree() {root=null;size=0;}//辅助函数 获取高度public int getHeight(Node node){if(node==null){return 0;}return node.height;}//辅助函数 获取平衡因子public int BanlanceFator(Node node){if(node==null){return 0;}return getHeight(node.left)-getHeight(node.right);}//辅助函数 判断是否是二分搜索树public boolean isBST(){ArrayList<K> tree=new ArrayList<K>();inOrder(root,tree);for(int i=1;i<tree.size();i++){if(tree.get(i-1).compareTo(tree.get(i))>0){return false;}}return true;}//中序遍历private void inOrder(Node node, ArrayList<K> tree) {if(node==null){return;}inOrder(node.left,tree);tree.add(node.key);inOrder(node.right, tree);}//判断是否是二叉平衡树public boolean isBalanced(){return isBalanced(root);}private boolean isBalanced(Node node) {if(node==null){return true;}int balancedFactor=BanlanceFator(node);if(Math.abs(balancedFactor)>1){return false;}return isBalanced(node.left)&&isBalanced(node.right);}//右旋转 	发生在不平衡节点的左侧的左侧 LLprivate Node rightRotate(Node node){Node x=node.left;Node T3=x.right;x.right=node;node.left=T3;node.height=1+Math.max(getHeight(node.left), getHeight(node.right));x.height=1+Math.max(getHeight(x.left), getHeight(x.right));return x;}//左旋转 	发生在不平衡节点右侧的右侧RRprivate Node leftRotate(Node node){Node x=node.right;Node T2=x.left;x.left=node;node.right=T2;node.height=1+Math.max(getHeight(node.left), getHeight(node.right));x.height=1+Math.max(getHeight(x.left), getHeight(x.right));return x;}@Overridepublic void add(K key, V value) {root=add(root,key,value);}//以node为根节点，将键值对k-v添加到树private Node add(Node node,K key,V value){if(node==null){size++;return new Node(key,value);}if(key.compareTo(node.key)>0){node.right=add(node.right,key,value);}else if(key.compareTo(node.key)<0){node.left=add(node.left,key,value);}else{node.value=value;}node.height=1+Math.max(getHeight(node.left), getHeight(node.right));if(BanlanceFator(node)>1&&BanlanceFator(node.left)>=0){return rightRotate(node);}if(BanlanceFator(node)<-1&&BanlanceFator(node.right)<=0){return leftRotate(node);}if(BanlanceFator(node)>1&&BanlanceFator(node.left)<0){node.left=leftRotate(node.left);return rightRotate(node);}if(BanlanceFator(node)<-1&&BanlanceFator(node.right)>0){node.right=rightRotate(node.right);return leftRotate(node);}return node;}@Overridepublic V remove(K key) {Node p=getNode(root, key);if(p==null){return null;}root=remove(root,key);return p.value;}private Node remove(Node node,K key){if(node==null){return null;}Node retNode;if(key.compareTo(node.key)>0){node.right=remove(node.right,key);retNode=node;}else if(key.compareTo(node.key)<0){node.left=remove(node.left,key);retNode=node;}else{if(node.left==null){Node rightNode=node.right;node.right=null;size--;retNode=rightNode;}else if(node.right==null){Node leftNode=node.left;node.left=null;size--;retNode=leftNode;}else {Node successor=minnum(node);successor.right=remove(successor.right, successor.key);successor.left=node.left;node.left=null;node.right=null;size--;retNode=successor;}}if(retNode==null){return null;}retNode.height=1+Math.max(getHeight(retNode.left), getHeight(retNode.right));if(BanlanceFator(retNode)>1&&BanlanceFator(retNode.left)>=0){return rightRotate(retNode);}if(BanlanceFator(retNode)<-1&&BanlanceFator(retNode.right)<=0){return leftRotate(retNode);}if(BanlanceFator(retNode)>1&&BanlanceFator(retNode.left)<0){retNode.left=leftRotate(retNode.left);return rightRotate(retNode);}if(BanlanceFator(retNode)<-1&&BanlanceFator(retNode.right)>0){retNode.right=rightRotate(retNode.right);return leftRotate(retNode);}return retNode;}private Node minnum(Node node){if(node.left==null){return node;}else{return minnum(node.left);}}private Node removeMin(Node node){if(node.left==null){Node p=node.right;node.right=null;size--;return p;}node.left=removeMin(node.left);return node;}@Overridepublic boolean contains(K key) {Node p=getNode(root,key);return p==null? false:true;}@Overridepublic V get(K key) {Node p=getNode(root, key);return p==null? null:p.value;}@Overridepublic void set(K key, V value) {Node p=getNode(root, key);if(p==null){throw new IllegalArgumentException("元素不存在！");}else{p.value=value;}}@Overridepublic int getSize() {return size;}@Overridepublic boolean isEmpty() {return size==0;}@Overridepublic Set keys() {Set<K> set=new BSTSet<K>();inOrder(root,set);return set;}private void inOrder(Node node, Set<K> set) {if(node==null){return;}inOrder(node.left,set);set.add(node.key);inOrder(node.right, set);}@Overridepublic List values() {return null;}private Node getNode(Node node,K key){if(node==null){return null;}if(key.compareTo(node.key)>0){return getNode(node.right,key);}else if(key.compareTo(node.key)<0){return getNode(node.left,key);}else{return node;}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！