平衡二叉樹的重點在於對不平衡的進行旋轉從而使它達到平衡.
下面是我理解的平衡二叉樹的操作總結:
平衡因子(BF)：
這是一個描述平衡度的一個量,計算的方式為 左子樹的深度-右子樹的深度。
我們可以從BF中就能知道左子樹和右子樹之間的平衡程度。
插入數據
平衡二叉樹最複雜的就是將數據插入到樹中了，因為要涉及到位置的調整。對於位置的調整在平衡二叉樹中成為樹的旋轉.根據平衡因子的狀態分為左旋和右旋.
那什麼時候需要進行旋轉呢?
這個問題確實值得思考,一般都是在平衡因子的絕對值大於1的時候就需要進行旋轉了，也就是說左右子樹的深度相差超過了1.
那從什麼地方做為跟節點進行旋轉呢？
這裡有一個術語叫做最小不平衡子樹,就是平衡因子絕對值大於1,並且最接近葉子節點的。
我們旋轉的時候,只需要對最小不平衡子樹進行旋轉就可以了。
左旋：
當平衡因子為正數的時候並且大於1的時候，進行左旋，左旋的方式為：根節點的左子樹的右子樹作為根節點的右子樹，根節點作為左子樹的右子樹。
右旋：
當平衡因子為負數的時候,並且小於-1的時候進行右旋，右旋的方式為：
將根節點的右節點的左子樹作為根節點的右子樹.
根節點作為跟節點的右節點的左子樹。
注意：
上面兩種實例根節點和子節點都是同一符號的,所以簡單的進行左旋或者右旋就可以了。如下圖：
,但是如果我們遇到符號不相同的情況下,需要進行兩次旋轉，如下圖：
這種情況下，第一次旋轉是將C作為根節點右旋,之後再進行左旋.
我們只需要記住正數的時候進行右旋,負數的時候進行左旋即可。
上面的原理講完了,下面是具體的JAVA代碼實現：
package com.hotusm.datastructure.tree;
/**
* @author luqibao
* @date 2017/3/31
*/
public class AVLTree {
/**
* 平衡因子所屬的狀態
*/
private static final int LH = 1; //左邊高
private static final int EH = 0; //一樣高
private static final int RH = -1; //右邊高
private TreeNode root; //樹的根
/**
* 向平衡二叉樹插入節點
*
* @param data
*/
public void insertNode(int data) {
if (this.root == null) {
this.root = new TreeNode(null, null, EH, data, null);
return;
}
insertAVLNode(this.root, data);
}
/**
* 進行右旋
*
* @param treeNode 需要旋轉的根
*/
/*
* 右旋
* 將根的左子樹的右子樹作為根的左子樹
* 左子樹的右子樹指向根(最後左子樹變為了根,根變為了右子樹)
*/
private void rRotate(TreeNode treeNode) {
TreeNode root = treeNode.getLeft;
if (treeNode == this.root) {
this.root = root;
}
treeNode.setLeft(root.getRight);
root.setRight(treeNode);
}
/**
* 進行左旋
*
* @param treeNode 需要旋轉的根
*/
/*
* 左旋
* 將根的右子樹的左子樹作為根的右子樹
* 右子樹的左子樹指向根（最後右子樹變為個根,根變為了左子樹）
* */
private void lRotate(TreeNode treeNode) {
TreeNode root = treeNode.getRight;
if (treeNode == this.root) {
this.root = root;
}
treeNode.setRight(root.getLeft);
root.setLeft(treeNode);
}
/**
* 左平衡旋轉（左邊平衡因子太大的原因 需要向右移動）
*
* @param root
*/
private void leftBalance(TreeNode root) {
TreeNode leftNode = root.getLeft;
switch (leftNode.getBf) {
case LH:
root.setBf(EH);
leftNode.setBf(EH);
rRotate(root);
break;
//如果是這種情況 根和左子樹平衡因子不是同符號的 所以需要兩次的旋轉
case RH:
TreeNode doubleLeftNode = leftNode.getRight;// 左子樹的右子樹
switch (doubleLeftNode.getBf) {
case RH:
root.setBf(EH);
leftNode.setBf(LH);
break;
case EH:
root.setBf(EH);
leftNode.setBf(EH);
break;
case LH:
root.setBf(RH);
leftNode.setBf(EH);
break;
}
doubleLeftNode.setBf(EH);
lRotate(leftNode);
rRotate(root);
break;
}
}
/**
* 右平衡旋轉 右邊平衡因子太大的原因
*
* @param root
*/
private void rightBalance(TreeNode root) {
TreeNode rightNode = root.getRight;
switch (rightNode.getBf) {
case RH:
root.setBf(EH);
rightNode.setBf(EH);
lRotate(root);
break;
case LH: //如果是這種情況 那麼根和右子樹的平衡因子不同符號 所以需要進行兩次的旋轉
TreeNode doubleLeftNode = rightNode.getLeft;
switch (doubleLeftNode.getBf) {
case LH:
root.setBf(EH);
rightNode.setBf(RH);
break;
case EH:
root.setBf(EH);
rightNode.setBf(EH);
break;
case RH:
root.setBf(LH);
rightNode.setBf(EH);
break;
}
doubleLeftNode.setBf(EH);
rRotate(rightNode);
lRotate(root);
break;
}
}
/**
* 向平衡二叉樹插入數據data
* 如果增高那麼返回true 否則返回false
*
* @param data
* @return
*/
private boolean insertAVLNode(TreeNode root, int data) {
boolean taller = false;
if (root.getData == data) {
return false;
}
if (data < root.getData) {
if (root.getLeft==null){
TreeNode child=new TreeNode(null,null,EH,data,root);
root.setLeft(child);
if (root.getBf==EH){
root.setBf(LH);
return true;
}
/*
* 在child 節點未插入到root的左子樹中的時候
* root的BF只能有兩種情況 EH(左右都沒節點) 和 RH(有右葉子節點)
* 所以還有一種可能就是當時RH的時候 BF變為EH
* */
root.setBf(EH);
}else {
taller=insertAVLNode(root.getLeft,data);
if (taller){
switch (root.getBf){
case LH:
leftBalance(root);
taller=false;
break;
case EH:
/*
*進行上一級的回溯
* O
* O O
* O O
*/
root.setBf(LH);
taller=true;
break;
default:
root.setBf(EH);
taller=false;
}
}
}
} else {
if (root.getRight==null){
TreeNode child=new TreeNode(null,null,EH,data,root);
root.setRight(child);
if (root.getBf==EH){
root.setBf(RH);
}
/*
* 和上面的類似,在右子樹插入到root之前 root的BF只有兩種情況 EH（沒有左右節點） LH （只有左葉子節點）
* */
root.setBf(EH);
}else {
taller=insertAVLNode(root.getRight,data);
if (taller){
switch (root.getBf){
case RH:
rightBalance(root);
taller=false;
break;
case LH:
root.setBf(EH);
taller=false;
break;
default:
/*
*這裡會進行回溯到更上的一級進行判斷 從而進行旋轉
* O
* O O
* O O
*/
root.setBf(RH);
taller=true;
}
}
}
}
return taller;
}
public static void main(String[] args) {
testInsertAVLTree;
}
public static void testInsertAVLTree {
AVLTree avlTree = new AVLTree;
avlTree.insertNode(1);
avlTree.insertNode(2);
avlTree.insertNode(3);
avlTree.insertNode(4);
avlTree.insertNode(5);
}
/**
* 樹的節點
*/
public static class TreeNode {
private TreeNode left;
private TreeNode right;
private TreeNode parent;
private int bf; //平衡因子
private int data;
public TreeNode(TreeNode left, TreeNode right, int bf, int data, TreeNode parent) {
this.left = left;
this.right = right;
this.bf = bf;
this.data = data;
this.parent = parent;
}
public TreeNode getLeft {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public int getBf {
return bf;
}
public void setBf(int bf) {
this.bf = bf;
}
public int getData {
return data;
}
public TreeNode getParent {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public void setData(int data) {
this.data = data;
}
@Override
public String toString {
return "TreeNode{" +
"left=" + left +
", right=" + right +
", bf=" + bf +
", data=" + data +
'}';
}
}
}代碼中進行了詳細的註釋，看起來應該是沒問題的。
參考：大話數據結構 第八章
相關推薦
推薦中...