本篇文章為大家帶來了關於java的相關知識，其中主要介紹了關於平衡二叉樹（AVL樹）的相關知識，AVL樹本質上是帶了平衡功能的二叉找樹，下面一起來看一下，希望對大家有幫助。
推薦學習：《java影片教學》
搜尋二元樹有著極高的搜尋效率，但是搜尋二元樹會出現以下極端情況：
這樣的二元樹搜尋效率甚至比鍊錶還低。在搜尋二元樹基礎上出現的平衡二元樹(AVL樹)就解決了這樣的問題。當平衡二元樹(AVL樹)的某個節點左右子樹高度差的絕對值大於1時，就會透過旋轉操作來減少它們的高度差。
AVL樹本質上還是一棵二元搜尋樹，它的特點是：
二元搜尋樹。 高度之差的絕對值（平衡因子）最多為1。也就是說，AVL樹，本質上是帶了平衡功能的二元查找樹（二元排序樹，二元搜尋樹）。 左旋和右旋的操作使二元樹再次達到平衡狀態。 平衡因子(balanceFactor)
高度之差 。 -1，0和1。
下面是AVL樹需要的簡單方法與屬性：
public class AVLTree <e>>{
class Node{
E value;
Node left;
Node right;
int height;
public Node(){}
public Node(E value){
this.value = value;
height = 1;
left = null;
right = null;
}
public void display(){
System.out.print(this.value + " ");
}
}
Node root;
int size;
public int size(){
return size;
}
public int getHeight(Node node) {
if(node == null) return 0;
return node.height;
}
//获取平衡因子(左右子树的高度差，大小为1或者0是平衡的，大小大于1不平衡)
public int getBalanceFactor(){
return getBalanceFactor(root);
}
public int getBalanceFactor(Node node){
if(node == null) return 0;
return getHeight(node.left) - getHeight(node.right);
}
//判断一个树是否是一个平衡二叉树
public boolean isBalance(Node node){
if(node == null) return true;
int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
if(balanceFactor > 1) return false;
return isBalance(node.left) && isBalance(node.right);
}
public boolean isBalance(){
return isBalance(root);
}
//中序遍历树
private void inPrevOrder(Node root){
if(root == null) return;
inPrevOrder(root.left);
root.display();
inPrevOrder(root.right);
}
public void inPrevOrder(){
System.out.print("中序遍历：");
inPrevOrder(root);
}}</e>往一個樹右子樹的右子樹上插入一個節點，導致二元樹變得不在平衡，如下圖，往平衡二元樹中插入5，導致這個樹變得不再平衡，此時需要左旋操作，如下：
程式碼如下：
//左旋,并且返回新的根节点
public Node leftRotate(Node node){
System.out.println("leftRotate");
Node cur = node.right;
node.right = cur.left;
cur.left = node;
//跟新node和cur的高度
node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
return cur;
}在一個AVL樹左子樹的左子樹上插入節點，導致二元樹變得不在平衡，如下圖，往平衡二元樹中插入2，導致這個樹變得不再平衡，此時需要左旋操作，如下：
程式碼如下：
//右旋，并且返回新的根节点
public Node rightRotate(Node node){
System.out.println("rightRotate");
Node cur = node.left;
node.left = cur.right;
cur.right = node;
//跟新node和cur的高度
node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
return cur;
}往AVL樹左子樹的右子樹上插入一個節點，導致該樹不再平衡，需要先對左子樹進行左旋，再對整棵樹右旋，如下圖所示，插入節點為5.
在AVL樹右子樹的左子樹上插入一個節點，導致該樹不再平衡，需要先對右子樹進行右旋，再對整棵樹左旋，如下圖所示，插入節點為2.
//添加元素
public void add(E e){
root = add(root,e);
}
public Node add(Node node, E value) {
if (node == null) {
size++;
return new Node(value);
}
if (value.compareTo(node.value) > 0) {
node.right = add(node.right, value);
} else if (value.compareTo(node.value) 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
//该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
else if (balanceFactor 1 && getBalanceFactor(node.left) 0
//该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋
else if(balanceFactor 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
} //删除节点
public E remove(E value){
root = remove(root,value);
if(root == null){
return null;
}
return root.value;
}
public Node remove(Node node, E value){
Node retNode = null;
if(node == null)
return retNode;
if(value.compareTo(node.value) > 0){
node.right = remove(node.right,value);
retNode = node;
}
else if(value.compareTo(node.value) 1 && getBalanceFactor(retNode.left) >= 0) {
return rightRotate(retNode);
}
//该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
else if (balanceFactor 1 && getBalanceFactor(retNode.left) 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}推薦學習：《java影片教學》
以上是Java資料結構之AVL樹詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！
