AVL平衡樹
最早的平衡二叉樹之一。應用相對其他資料結構比較少。windows對程序位址空間的管理用到了AVL樹。
定義
- 左右子樹均為AVL樹
- 左右子樹的高度差的絕對值不超過1
平衡二叉樹
滿二叉樹一定是平衡二叉樹，高度最低
完全二叉樹也是平衡二叉樹，葉子節點深度相差不為1
線段樹也是平衡二叉樹，葉子節點深度相差不為1
下圖中看起來比較偏斜，但是符合定義 平衡二叉樹的高度和節點數量之間的關系也是O(logn)的 如若此時加入節點2,7，則不再符合定義
那麼，我們該如何調整呢?
- 先标記節點高度
2. 計算平衡因子（節點左右的高度差）
- 自平衡實作
自平衡實作
自平衡實作有很多情況，大緻分為一下幾種情況：LL，RR，RL，LR。
- 右旋轉LL
插入的元素在不平衡節點的左側的左側
如何右旋轉，x.right=y，y.left=T3 ；
旋轉時注意不能改變原二分搜尋樹的性質 T1<z<T2<x<T3<y<T4；
- 左旋轉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);
}
//右旋轉 發生在不平衡節點的左側的左側 LL
private 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;
}
//左旋轉 發生在不平衡節點右側的右側RR
private 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;
}
@Override
public 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;
}
@Override
public 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;
}
@Override
public boolean contains(K key) {
Node p=getNode(root,key);
return p==null? false:true;
}
@Override
public V get(K key) {
Node p=getNode(root, key);
return p==null? null:p.value;
}
@Override
public void set(K key, V value) {
Node p=getNode(root, key);
if(p==null){
throw new IllegalArgumentException("元素不存在！");
}else{
p.value=value;
}
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public 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);
}
@Override
public 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;
}
}
}