简介：本文介绍平衡二叉树基本概念，并通过继承AbstractBinaryTree抽象类，java实现ALVBinaryTreeList，主要操作算法有插入和删除。
一、平衡二叉树基本概念 1.平衡二叉树是什么？2.为什么会出现平衡二叉树？平衡二叉树时一种结构平衡的二叉树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
3.平衡二叉树有哪些性质？1）二叉树插入时存在最坏情况，导致查找的时间复杂度为O(n)。例如：顺序插入1，2，3，...，时，二叉树严重失衡，退化为普通链表，查找时间复杂度为O(n)。
2）平衡二叉树通过调整二叉树的结构使二叉树平衡，最坏查找的时间复杂度变为
1）本身是一棵二叉搜索树。
2）带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
4.平衡二叉树节点如何定义？
除了需要像二叉树一样存在父节点、左孩子、右孩子、节点值之外，还需要可以求节点平衡因子的树高度。
二、平衡二叉树ALVBinaryTreeList实现和布局
1.实现思路
和上一篇BinaryTreeList一样，参照java集合ArrayList实现一个ALVBinaryTreeList，并增加平衡二叉树特有算法。
2.ALVBinaryTreeList如何布局？
由于平衡二叉树是二叉树的一种，其基本的遍历、深度等操作已经在AbstractTreeList中实现，因此ALVBinaryTreeList只需要继承AbstractTreeList，并实现节点插入、删除算法即可。
三、基于平衡二叉树的ALVBinaryTreeList实现
1.节点定义
2.ALVBinaryTreeList如何布局？和上一篇BinaryTreeList一样，参照java集合ArrayList实现一个ALVBinaryTreeList，并增加平衡二叉树特有算法。
由于平衡二叉树是二叉树的一种，其基本的遍历、深度等操作已经在AbstractTreeList中实现，因此ALVBinaryTreeList只需要继承AbstractTreeList，并实现节点插入、删除算法即可。
平衡二叉树属性比普通二叉树多一个高度，用于计算节点平衡度，因此在二叉树节点增加一个symbol作为高度，并增加一个构造方法。
static class Node2.ALVBinaryTreeList结构{ int symbol;//此处表示节点的高度 E value; Node parent; Node leftChild; Node rightChild; Node(Node parent,Node left,Node right,E value,int symbol){ this.parent = parent; this.leftChild = left; this.rightChild = right; this.value = value; this.symbol = symbol; } Node(Node parent,Node left,Node right,E value){ this.parent = parent; this.leftChild = left; this.rightChild = right; this.value = value; } Node(Node left,Node right,E value){ this(null,left,right,value); } Node(){} }
public class ALVBinaryTreeList3.平衡二叉树插入后调整思路extends AbstractTreeList { //各种实现代码在此 }
思想：平衡二叉树插入操作和普通二叉树一样，都需要在已有树节点某个叶子节点上插入，但是多了一个调整平衡的操作。
待插入节点z，在以r为根节点的子树上插入z，分为r的左孩子左子树插入、r的左孩子右子树插入、r的右孩子右子树插入、r的右孩子左子树插入。
1）r的左孩子左子树插入
如下图所示，需要以r的左孩子为轴进行右旋。
2）r的左孩子的右子树插入
如下图所示，需要先以r的左孩子为轴左旋，然后以旋转后的r的新的左孩子为轴，右旋。
3）r的右孩子右子树插入
需要以r的右孩子为轴左旋。
4）r的右孩子左子树插入
4.平衡二叉树插入代码实现需要以r的右孩子为轴右旋，然后以新的r的右孩子为轴左旋 。
1）左旋、右旋
void lRotate(Node2）获取子树高度、平衡因子x) { Node y = x.rightChild; x.rightChild = y.leftChild; if(y.leftChild!=null) y.leftChild.parent = x; y.parent = x.parent; if(x.parent == null) root = y; else if(x == x.parent.leftChild) x.parent.leftChild = y; else x.parent.rightChild = y; y.leftChild = x; x.parent = y; x.symbol = Math.max(height(x.leftChild), height(x.rightChild))+1; y.symbol = Math.max(height(y.leftChild), height(y.rightChild))+1; } void rRotate(Node x) { Node y = x.leftChild; x.leftChild = y.rightChild; if(y.rightChild!=null) y.rightChild.parent = x; y.parent = x.parent; if(x.parent == null) root = y; else if(x == x.parent.leftChild) x.parent.leftChild = y; else x.parent.rightChild = y; y.rightChild = x; x.parent = y; x.symbol = Math.max(height(x.leftChild), height(x.rightChild))+1; y.symbol = Math.max(height(y.leftChild), height(y.rightChild))+1; }
int height(Node3）插入节点node){ return (node == null)?0:node.symbol; } int getBalanceFactory(Node node) { return (node == null) ? 0:(height(node.leftChild) - height(node.rightChild)); }
@Override
public boolean add(E e) {
if(e == null) throw new NullPointerException("插入的元素为空");
addVal(e);
return true;
}
void addVal(E val){
Node r = root,p=null;
while (r!=null) {
p = r;
if(compare(val, r.value) < 0) r=r.leftChild;
else if(compare(val, r.value) > 0) r=r.rightChild;
else return ;
}
Node e = new Node(p,null,null,val,1);
if(p == null) root = e;
else if(compare(val, p.value) < 0) p.leftChild = e;
else if(compare(val, p.value) > 0) p.rightChild = e;
else if(compare(val, p.value) == 0) return;
adjust(e);//从添加的元素e开始向上调整二叉树，直到根节点
size++;
}
4）调整平衡
void adjust(Node5.平衡二叉树删除代码实现p) { while(p != null) { int pHeight = Math.max(height(p.leftChild), height(p.rightChild)+1); p.symbol = pHeight; int pBf = getBalanceFactory(p); if(pBf == 2) {//左高 if(getBalanceFactory(p.leftChild) == 1) {//左孩子左子树插入 rRotate(p); }else if(getBalanceFactory(p.leftChild) == -1) {//左孩子右子树插入 lRotate(p.leftChild); rRotate(p); } }else if(pBf == -2) { if(getBalanceFactory(p.rightChild) == -1) { lRotate(p); }else if(getBalanceFactory(p.rightChild) == 1) { rRotate(p.rightChild); lRotate(p); } } if(p.parent == null) { root = p; return; } p = p.parent; } }
寻找到待删除节点z，然后：
1）z是叶子节点：直接删除。然后从叶子结点向上校验其各父节点是否失衡，失衡调整。
2）z是单孩子节点：用其子树代替。然后从删除节点父亲节点向上校验其父亲节点是否失衡，失衡调整。
3） z是双孩子节点：找其右子树最大节y点替换当前节点。如果y是z的右孩子，直接将y替换z。否则，需要先将y.right替换y，然后y替换z。最后从该节点父亲节点向上调整平衡。
//用newNode为根的树替代oldNode
void transplant(NodeoldNode,NodenewNode) {
if (oldNode.parent == null) root = newNode;
else if(oldNode == oldNode.parent.leftChild) oldNode.parent.leftChild = newNode;
else oldNode.parent.rightChild = newNode;
if(newNode != null) newNode.parent = oldNode.parent;
}
@Override
public boolean remove(Object o) {
if(o == null) throw new NullPointerException();
Noder;
if((r = root) == null) return false;
while(r!=null) {
if(compare((E)o,r.value) < 0) r = r.leftChild;
else if (compare((E)o,r.value) > 0) r = r.rightChild;
else {
//找到了节点r对应值为o
if(r.leftChild == null) transplant(r, r.rightChild);//没有左孩子
else if(r.rightChild == null) { //没有右孩子
transplant(r, r.leftChild);
adjust(r.parent);
}else {//有2个孩子
Noder2 = r.rightChild;
while(r2.leftChild!=null) r2 = r2.leftChild;
if(r2.parent != r) {
transplant(r2, r2.rightChild);
r2.rightChild = r.rightChild;
r2.rightChild.parent = r2;
}
transplant(r, r2);
r2.leftChild = r.leftChild;
r2.leftChild.parent = r2;
adjust(r2);
}
return true;
}
}
return false;
}
6.ALVBinaryTreeList节点清空实现
节点z清空需要节点z的左右子树都为空时才可，因此需要借助二叉树后续遍历实现节点清空。
首先Node类中新增节点清空方法
//在Node类中新增clear方法用于清空节点
void clear() {
this.parent = null;
this.leftChild = null;
this.rightChild = null;
this.value = null;
}
其次实现ALVBinaryTreeList清空方法
@Override
public void clear() {
//clear需要让节点的左右子树全为空，因此需要后续遍历
Nodecur=root,pre=null;
linkedList> stack = new linkedList<>();
while(cur!=null || !stack.isEmpty()) {
while(cur!=null) {
stack.push(cur);
cur = cur.leftChild;
}
cur = stack.pop();
if(cur.rightChild==null || cur.rightChild==pre) {
pre = cur;
cur.clear();
cur = null;
size--;
}else {
stack.push(cur);
cur = cur.rightChild;
}
}
root = null;
}
五、ALVBinaryTreeList测试
测试思路：生成随机数添加到ALVBinaryTreeList中，然后同时添加到set中，中序遍历获取ALVBinaryTreeList元素，并且将set中的元素排序，最后比较排序好的setList和中序遍历list元素是否一致。
节点删除方法测试是同样的思路。下面给出节点删除测试代码：
static void binaryTest() {
AbstractTreeList binaryTreeList = new ALVBinaryTreeList();
Random random = new Random();
Set set1= new HashSet();
for(int i=0;i<10000;i++) {
int e = random.nextInt(100000);
set1.add(e);
binaryTreeList.add(Integer.valueOf(e));
}
Object[] arr1 = set1.toArray();
for(Object el : arr1) {
binaryTreeList.remove(el);
set1.remove(el);
Object[] binaryarr = binaryTreeList.toArray();
Object[] setarr = set1.toArray();
Arrays.sort(setarr);
for (int j=0;j
