平衡树插入
2018-12-24 本文已影响0人
夜亦明
平衡树：
平衡树是二叉树的一种，其任意子树的左右分支的高度之差（即平衡因子）最大不超过1的绝对值
平衡树的优缺点：
优点：
查询速度最快（log2N 次）
缺点：
插入删除操作需要频繁的改变树的结构，造成性能消耗。
平衡树的插入思路：
1.首先，按照二叉树的插入规则，插入节点。
2.运用左右旋转操作对树进行调整。（左、右旋转操作是基础）
代码实现
1.定义节点
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;
/**
* 根节点
*/
private Node<E> root;
3.左右旋转操作的API
/**
* 左旋转
*
* @param root 最小不平衡树根节点
*/
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.将右子树作为根节点
if (parent == null) {
this.root = rightChild;
} else {
if (root == parent.leftChild) {
parent.leftChild = rightChild;
} else {
parent.rightChild = rightChild;
}
}
//2.将以前的根节点作为rightChild的左节点
root.parent = rightChild;
rightChild.leftChild = root;
//3.将rightChild的左节点，作为原来的root的右节点
if (left != null) {
left.parent = root;
}
root.rightChild = left;
}
}
/**
* 右旋转
*
* @param root 最小不平衡树根节点
*/
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.将左子树作为根节点
if (parent == null) {
this.root = leftChild;
} else {
if (root == parent.leftChild) {
parent.leftChild = leftChild;
} else {
parent.rightChild = leftChild;
}
}
//2.将以前的根节点作为leftChild的右节点
root.parent = leftChild;
leftChild.rightChild = root;
//3.将leftChild的右节点，作为原来的root的左节点
if (right != null) {
right.parent = root;
}
root.leftChild = right;
}
}
3.左右平衡操作
/**
* 左平衡
*
* @param root 最小不平衡树根节点
*/
private void leftBalance(Node root) {
if (root == null || root.leftChild == null) {
return;
}
Node leftChild = root.leftChild;
switch (leftChild.bf) {
case LH:
//如果左边高，直接右旋转
root.bf = EH;
leftChild.bf = EH;
rightRotation(root);
break;
case RH:
//如果右边高，先左旋转，后右旋转
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 最小不平衡树根节点
*/
private void rightBalance(Node root) {
if (root == null || root.rightChild == null) {
return;
}
Node rightChild = root.rightChild;
switch (rightChild.bf) {
case RH:
//如果右边高，直接左旋转
root.bf = EH;
rightChild.bf = EH;
leftRotation(root);
break;
case LH:
//如果左边高，先右旋转，后左旋转
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) {
//如果有一个父节点平衡因子为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();
}
打印结果(所有节点的平衡因子绝对值均小于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
