平衡樹：
平衡樹是二叉樹的一種，其任意子樹的左右分支的高度之差（即平衡因子）最大不超過1的絕對值
平衡樹的優(yōu)缺點：
優(yōu)點：
查詢速度最快（log2N 次）
缺點：
插入刪除操作需要頻繁的改變樹的結(jié)構(gòu)，造成性能消耗眠砾。
平衡樹的插入思路：
1.首先，按照二叉樹的插入規(guī)則，插入節(jié)點统倒。
2.運用左右旋轉(zhuǎn)操作對樹進行調(diào)整。（左氛雪、右旋轉(zhuǎn)操作是基礎(chǔ)）
代碼實現(xiàn)
1.定義節(jié)點
public class Node<E extends Comparable> implements Comparable<Node<E>> {
E data;
/**
* 平衡因子
*/
int bf;
Node<E> leftChild;
Node<E> rightChild;
Node<E> parent;
public Node(E data) {
this.data = data;
}
@Override
public int compareTo(@NonNull Node<E> o) {
return this.data.compareTo(o.data);
}
}
2.定義平衡樹的屬性和常量
/**
* 平衡因子右邊高
*/
private static final int RH = -1;
/**
* 平衡因子左邊高
*/
private static final int LH = 1;
/**
* 平衡因子0
*/
private static final int EH = 0;
/**
* 根節(jié)點
*/
private Node<E> root;
3.左右旋轉(zhuǎn)操作的API
/**
* 左旋轉(zhuǎn)
*
* @param root 最小不平衡樹根節(jié)點
*/
private void leftRotation(Node root) {
if (root == null) {
return;
}
Node rightChild = root.rightChild;
Node parent = root.parent;
if (rightChild != null) {
rightChild.parent = parent;
Node left = rightChild.leftChild;
//1.將右子樹作為根節(jié)點
if (parent == null) {
this.root = rightChild;
} else {
if (root == parent.leftChild) {
parent.leftChild = rightChild;
} else {
parent.rightChild = rightChild;
}
}
//2.將以前的根節(jié)點作為rightChild的左節(jié)點
root.parent = rightChild;
rightChild.leftChild = root;
//3.將rightChild的左節(jié)點房匆，作為原來的root的右節(jié)點
if (left != null) {
left.parent = root;
}
root.rightChild = left;
}
}
/**
* 右旋轉(zhuǎn)
*
* @param root 最小不平衡樹根節(jié)點
*/
private void rightRotation(Node root) {
if (root == null) {
return;
}
Node leftChild = root.leftChild;
Node parent = root.parent;
if (leftChild != null) {
leftChild.parent = parent;
Node right = leftChild.rightChild;
//1.將左子樹作為根節(jié)點
if (parent == null) {
this.root = leftChild;
} else {
if (root == parent.leftChild) {
parent.leftChild = leftChild;
} else {
parent.rightChild = leftChild;
}
}
//2.將以前的根節(jié)點作為leftChild的右節(jié)點
root.parent = leftChild;
leftChild.rightChild = root;
//3.將leftChild的右節(jié)點，作為原來的root的左節(jié)點
if (right != null) {
right.parent = root;
}
root.leftChild = right;
}
}
3.左右平衡操作
/**
* 左平衡
*
* @param root 最小不平衡樹根節(jié)點
*/
private void leftBalance(Node root) {
if (root == null || root.leftChild == null) {
return;
}
Node leftChild = root.leftChild;
switch (leftChild.bf) {
case LH:
//如果左邊高报亩，直接右旋轉(zhuǎn)
root.bf = EH;
leftChild.bf = EH;
rightRotation(root);
break;
case RH:
//如果右邊高浴鸿，先左旋轉(zhuǎn)，后右旋轉(zhuǎn)
Node tlr = leftChild.rightChild;
switch (tlr.bf) {
case LH:
tlr.bf = EH;
root.bf = RH;
leftChild.bf = EH;
break;
case RH:
tlr.bf = EH;
root.bf = EH;
leftChild.bf = LH;
break;
case EH:
tlr.bf = EH;
root.bf = EH;
leftChild.bf = EH;
break;
default:
break;
}
leftRotation(leftChild);
rightRotation(root);
break;
}
}
/**
* 右平衡
*
* @param root 最小不平衡樹根節(jié)點
*/
private void rightBalance(Node root) {
if (root == null || root.rightChild == null) {
return;
}
Node rightChild = root.rightChild;
switch (rightChild.bf) {
case RH:
//如果右邊高弦追，直接左旋轉(zhuǎn)
root.bf = EH;
rightChild.bf = EH;
leftRotation(root);
break;
case LH:
//如果左邊高岳链，先右旋轉(zhuǎn)，后左旋轉(zhuǎn)
Node tll = rightChild.leftChild;
switch (tll.bf) {
case LH:
tll.bf = EH;
root.bf = EH;
rightChild.bf = RH;
break;
case RH:
tll.bf = EH;
root.bf = LH;
rightChild.bf = EH;
break;
case EH:
tll.bf = EH;
root.bf = EH;
rightChild.bf = EH;
break;
default:
break;
}
rightRotation(rightChild);
leftRotation(root);
break;
}
}
4.進行添加操作
/**
* 添加
*
* @param elment 元素
* @return true添加成功劲件，false 添加失數а啤（重復）
*/
public boolean add(E elment) {
if (root == null) {
Node<E> node = new Node<>(elment);
root = node;
return true;
}
//1.查找到添加的位置
Node<E> temp = root;
Node<E> parent = null;
while (temp != null) {
parent = temp;
int cmp = elment.compareTo(temp.data);
if (cmp > 0) {
temp = temp.rightChild;
} else if (cmp < 0) {
temp = temp.leftChild;
} else {
//重復
return false;
}
}
Node<E> newNode = new Node<>(elment);
int cmp = elment.compareTo(parent.data);
if (cmp > 0) {
parent.rightChild = newNode;
} else {
parent.leftChild = newNode;
}
newNode.parent = parent;
//2.改變相應的平衡因子
while (parent != null) {
int c = elment.compareTo(parent.data);
if (c > 0) {
parent.bf--;
} else {
parent.bf++;
}
if (parent.bf == EH) {
//如果有一個父節(jié)點平衡因子為0,則該樹任然是平衡樹，不做操作
break;
} else if (parent.bf == 2) {
leftBalance(parent);
break;
} else if (parent.bf == -2) {
rightBalance(parent);
break;
}
parent = parent.parent;
}
return true;
}
測試打恿阍丁：
提供遍歷方法(層序遍歷)：
public void traversal() {
if (root == null) {
return;
}
LinkedList<Node<E>> linkedList = new LinkedList<>();
linkedList.offer(root);
while (!linkedList.isEmpty()) {
Node node = linkedList.pop();
System.out.println(node.data + " bf:" + node.bf);
if (node.leftChild != null) {
linkedList.offer(node.leftChild);
}
if (node.rightChild != null) {
linkedList.offer(node.rightChild);
}
}
}
測試代碼：
@Test
public void testAVLBTree(){
int[] array = new int[]{4,1,9,2,0,7,5,11,49,21,3,45};
AVLBTree<Integer> avlbTree = new AVLBTree<>();
for (int i : array) {
avlbTree.add(i);
}
avlbTree.traversal();
}
打印結(jié)果(所有節(jié)點的平衡因子絕對值均小于2)
4 bf:0
1 bf:-1
11 bf:0
0 bf:0
2 bf:-1
7 bf:0
45 bf:0
3 bf:0
5 bf:0
9 bf:0
21 bf:0
49 bf:0
