数据结构与算法(九,平衡二叉树)
2019-03-12 本文已影响0人
腊鸡程序员
90.jpg
1.概念
平衡二叉树是一颗二叉排序树,且树的每个节点的平衡因子的绝对值不大于1.
平衡因子:节点左子树层级与节点右子树层级的差值
2.构建一颗平衡二叉树
如何构建一颗平衡二叉树呢?
我们从根结点开始构建,每添加一个节点,我们就去调整树的平衡性,直到添加完所有的结点为止.
那么问题来了,如何调整一颗树的平衡性呢?
首先,我们得找到树中最小不平衡树,然后以最小不平衡树的根结点为中心点,通过旋转的方式使整颗树达到平衡.
那么,怎样找最小不平衡树.怎样旋转?
-
最小不平衡树
以距离插入结点最近的且结点平衡因子的绝对值大于1的结点为根结点的树,即最小不平衡树
image.png
-
旋转的规则
左平衡操作,当整颗树的根结点balance = LEFT_HIGH时,做左平衡操作.
image.png
右平衡操作,当整颗树的根结点balance = RIGHT_HIGH时,做右平衡操作
image.png
-
左旋转操作:
先看图
image.png
操作规则:
- 把β结点(Y的左孩子)作为x的右孩子
- Y结点替代X结点的位置
- X结点作为Y的左孩子
-
右旋转操作:
先看图,1图从右向左看
image.png
根据图2来看规则
- y结点的左孩子为yl结点,yl的右孩子作为Y的左孩子
- yl结点替代Y结点的位置
- Y结点作为yl结点的右孩子
3.代码
构建规则已经掌握,那么代码就是手到擒来
import org.junit.Test;
import java.util.LinkedList;
public class AVLBTree<E extends Comparable<E>> {
Node<E> root;
int size;
private static final int LH = 1;
private static final int RH = -1;
private static final int EH = 0;
public boolean insertElement(E element) {
Node<E> t = root;
if (t == null) {
root = new Node<>(element, null);
size = 1;
root.balance = 0;
return true;
} else {
//先找到结点要插入的位置,插入节点
Node<E> parent;
int cmp;
Comparable<E> e = element;
do {
parent = t;
cmp = e.compareTo(t.element);
if (cmp > 0) {
t = t.rightChild;
} else if (cmp < 0) {
t = t.leftChild;
} else {
return false;
}
} while (t != null);
Node child = new Node(element, parent);
if (cmp < 0) {
parent.leftChild = child;
} else {
parent.rightChild = child;
}
//插入后再调整平衡
while (parent != null) {
cmp = e.compareTo(parent.element);
if (cmp > 0) {
parent.balance--;
} else if (cmp < 0) {
parent.balance++;
} else {
break;
}
if (Math.abs(parent.balance) == 2) {
fixAfterInsert(parent);
break;
} else {
parent = parent.parent;
}
}
}
size++;
return true;
}
private void fixAfterInsert(Node<E> parent) {
if (parent.balance == 2) {
leftBalance(parent);
} else if (parent.balance == -2) {
rightBalance(parent);
}
}
/**
* 右平衡操作
* 先看右孩子的平衡因子,RH>左旋,LH>先右旋再左旋
* 最后调整t和tr的平衡因子
*
* @param t
*/
private void rightBalance(Node<E> t) {
Node<E> tr = t.rightChild;
switch (tr.balance){
case RH:
leftRotate(t);
break;
case LH:
Node trl = tr.leftChild;
switch (trl.balance){
case LH:
t.balance = EH;
tr.balance = RH;
trl.balance = EH;
break;
case RH:
t.balance = LH;
tr.balance = EH;
trl.balance = EH;
break;
case EH:
t.balance = EH;
tr.balance = EH;
trl.balance = EH;
break;
default:
break;
}
rightRotate(tr);
leftRotate(t);
break;
default:
break;
}
}
/**
* 左平衡操作,结合上面的旋转规则来看代码
* 先看左孩子的平衡因子,LH>直接右旋,RH>先左旋再右旋
* 最后修改旋转后t和tl的平衡因子
*
* @param t
*/
private void leftBalance(Node<E> t) {
Node<E> tl = t.leftChild;
switch (tl.balance) {
case LH:
rightRotate(t);
break;
case RH:
Node tlr = tl.rightChild;
switch (tlr.balance) {
case LH:
tl.balance = EH;
t.balance = RH;
tlr.balance = EH;
break;
case RH:
tl.balance = LH;
t.balance = EH;
tlr.balance = EH;
break;
case EH:
tl.balance = EH;
t.balance = EH;
tlr.balance = EH;
break;
default:
break;
}
leftRotate(tl);
rightRotate(t);
break;
default:
break;
}
}
private void leftRotate(Node<E> x) {
if (x != null) {
Node<E> y = x.rightChild;
//step1
x.rightChild = y.leftChild;
if (y.leftChild != null) {
y.leftChild.parent = x;
}
//step2
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else {
if (x.parent.leftChild == x) {
x.parent.leftChild = y;
} else if (x.parent.rightChild == x) {
x.parent.rightChild = y;
}
}
//step3
y.rightChild = x;
x.parent = y;
}
}
private void rightRotate(Node<E> y) {
if (y != null) {
Node yl = y.leftChild;
//step1
y.leftChild = yl.rightChild;
if (yl.rightChild != null) {
yl.rightChild.parent = y;
}
//step2
yl.parent = y.parent;
if (y.parent == null) {
root = yl;
} else {
if (y.parent.leftChild == y) {
y.parent.leftChild = yl;
} else if (y.parent.rightChild == y) {
y.parent.rightChild = yl;
}
}
//sep3
yl.rightChild = y;
y.parent = yl;
}
}
@Test
public void Test(){
Integer[] nums={5,8,2,0,1,-2};
AVLBTree<Integer> tree=new AVLBTree<>();
for(int i=0;i<nums.length;i++){
tree.insertElement(nums[i]);
}
showAVL(tree.root);
}
private void showAVL(Node root) {
LinkedList<Node> list = new LinkedList<>();
list.offer(root);
while (!list.isEmpty()){
Node node = list.pop();
System.out.print(node.element);
if (node.leftChild!=null){
list.offer(node.leftChild);
}
if (node.rightChild!=null){
list.offer(node.rightChild);
}
}
}
/**
* 结点
*
* @param <E>
*/
public static class Node<E extends Comparable<E>> {
int balance = 0;//平衡因子
E element;
Node<E> parent;
Node<E> leftChild;
Node<E> rightChild;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
public int getBalance() {
return balance;
}
public void setBalance(int balance) {
this.balance = balance;
}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public Node<E> getParent() {
return parent;
}
public void setParent(Node<E> parent) {
this.parent = parent;
}
public Node<E> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<E> leftChild) {
this.leftChild = leftChild;
}
public Node<E> getRightChild() {
return rightChild;
}
public void setRightChild(Node<E> rightChild) {
this.rightChild = rightChild;
}
}
}
