平衡二叉树，递归实现
结构
由于二叉查找树插入删除操作，会导致树的不平衡，所有需要自己平衡，即平衡二叉树，
左边的是平衡二叉树，右边的则不平衡，树2的高度比树8高2，平衡条件是不超过1.
所以需要对数旋转以达到平衡。
class AVLTreeNode<E extends Comparable<E>>{
E data;
AVLTreeNode left;
AVLTreeNode right;
int height;
AVLTreeNode(E e) {
this(e,null,null);
}
AVLTreeNode(E e, AVLTreeNode<E> lt, AVLTreeNode<E> rt) {
data = e;
left = lt;
right = rt;
height = 0;
}
}
计算节点高度方法
private int height(AVLTreeNode<E> t){
return t == null ? -1 : t.height;
}
旋转
总共有四种情况
1对节点的左儿子的左儿子进行插入
2对节点的左儿子的右儿子进行插入
3对节点的右儿子的左儿子进行插入
4对节点的右儿子的右儿子进行插入
情况1,4对称，2,3对称
单旋转：左左，右右
左左的情况旋转如图，
右右的情况对称
左左：
private AVLTreeNode<E> rotateWithLeftChild(AVLTreeNode<E> k2) {
AVLTreeNode<E> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right))+1;
k1.height = Math.max(height(k1.left), k2.height)+1;
return k1;
}
右右：
private AVLTreeNode rotateWithRightChild(AVLTreeNode<E> k2) {
AVLTreeNode<E> k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.right), height(k2.left))+1;
k1.height =Math.max(height(k1.right), k2.height)+1;
return k1;
}
双旋转：左右，右左
上图为左右的平衡，先k3左子树右右单旋转，再k3左左单旋转，
右左的情况对称
左右：
private AVLTreeNode<E> doubleWithLeftChild(AVLTreeNode<E> k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
右左：
private AVLTreeNode<E> doubleWithRightChild(AVLTreeNode<E> k3) {
k3.right = rotateWithLeftChild(k3.right);
return rotateWithRightChild(k3);
}
平衡方法
private AVLTreeNode<E> balance(AVLTreeNode<E> t) {
if (t == null){
return t;
}
if (height(t.left) - height(t.right) > h){
if (height(t.left.left) >= height(t.left.right)){
//左左
t = rotateWithLeftChild(t);
}else {
//左右
t = doubleWithLeftChild(t);
}
}else{
if (height(t.right) - height(t.left) > h){
if (height(t.right.right) >= height(t.right.left)){
//右右
t = rotateWithRightChild(t);
} else {
//右左
t = doubleWithRightChild(t);
}
}
}
t.height = Math.max(height(t.left), height(t.right))+1;
return t;
}
insert
每次插入后都需要平衡
private AVLTreeNode<E> insert(E e, AVLTreeNode<E> t){
if (t == null){
return new AVLTreeNode<E>(e,null,null);
}
int result = e.compareTo(t.data);
if (result < 0){
t.left = insert(e, t.left);
}else if (result > 0){
t.right = insert(e, t.right);
}else {
}
return balance(t);
}
remove
删除跟二叉查找树一样，每次删除后都需要平衡
private AVLTreeNode<E> remove(E e, AVLTreeNode<E> t){
if (t == null){
return t;
}
int result = e.compareTo(t.data);
if (result < 0){
t.left = remove(e, t.left);
}else if (result > 0){
t.right = remove(e, t.right);
}else if (t.left != null && t.right != null){
t.data = (E) findMin(t.right).data;
t.right = remove(t.data, t.right);
}else {
t = (t.left != null) ? t.left : t.right;
}
return balance(t);
}
具体实现
package com.yb.shujujiegou.shu;
/**
* Created by 杨波 on 2017/5/9.
*/
public class AVLBinaryTree<E extends Comparable<E>> {
private static class AVLTreeNode<E extends Comparable<E>>{
E data;
AVLTreeNode left;
AVLTreeNode right;
int height;
AVLTreeNode(E e) {
this(e,null,null);
}
AVLTreeNode(E e, AVLTreeNode<E> lt, AVLTreeNode<E> rt) {
data = e;
left = lt;
right = rt;
height = 0;
}
}
private AVLTreeNode<E> root = null;
//计算节点高度
private int height(AVLTreeNode<E> t){
return t == null ? -1 : t.height;
}
//插入
private AVLTreeNode<E> insert(E e, AVLTreeNode<E> t){
if (t == null){
return new AVLTreeNode<E>(e,null,null);
}
int result = e.compareTo(t.data);
if (result < 0){
t.left = insert(e, t.left);
}else if (result > 0){
t.right = insert(e, t.right);
}else {
}
return balance(t);
}
//平衡最大差
private static final int h = 1;
//平衡
private AVLTreeNode<E> balance(AVLTreeNode<E> t) {
if (t == null){
return t;
}
if (height(t.left) - height(t.right) > h){
if (height(t.left.left) >= height(t.left.right)){
//左左
t = rotateWithLeftChild(t);
}else {
//左右
t = doubleWithLeftChild(t);
}
}else{
if (height(t.right) - height(t.left) > h){
if (height(t.right.right) >= height(t.right.left)){
//右右
t = rotateWithRightChild(t);
} else {
//右左
t = doubleWithRightChild(t);
}
}
}
t.height = Math.max(height(t.left), height(t.right))+1;
return t;
}
//右左(双旋转，先右子树左左单旋转,再右右单旋转)
private AVLTreeNode<E> doubleWithRightChild(AVLTreeNode<E> k3) {
k3.right = rotateWithLeftChild(k3.right);
return rotateWithRightChild(k3);
}
//左右(双旋转,先左子树右右单旋转,再左左单旋转)
private AVLTreeNode<E> doubleWithLeftChild(AVLTreeNode<E> k3) {
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
//右右(单旋转)
private AVLTreeNode rotateWithRightChild(AVLTreeNode<E> k2) {
AVLTreeNode<E> k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.right), height(k2.left))+1;
k1.height =Math.max(height(k1.right), k2.height)+1;
return k1;
}
//左左(单旋转)
private AVLTreeNode<E> rotateWithLeftChild(AVLTreeNode<E> k2) {
AVLTreeNode<E> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right))+1;
k1.height = Math.max(height(k1.left), k2.height)+1;
return k1;
}
public void insert(E e){
root = insert(e, root);
}
//遍历：中序
private void display(AVLTreeNode<E> avlTreeNode){
if (avlTreeNode!=null){
display(avlTreeNode.left);
System.out.print(avlTreeNode.data+" ");
display(avlTreeNode.right);
}
}
public void display(){
display(root);
}
//删除，每次删除都要平衡一次
private AVLTreeNode<E> remove(E e, AVLTreeNode<E> t){
if (t == null){
return t;
}
int result = e.compareTo(t.data);
if (result < 0){
t.left = remove(e, t.left);
}else if (result > 0){
t.right = remove(e, t.right);
}else if (t.left != null && t.right != null){
t.data = (E) findMin(t.right).data;
t.right = remove(t.data, t.right);
}else {
t = (t.left != null) ? t.left : t.right;
}
return balance(t);
}
private AVLTreeNode<E> findMin(AVLTreeNode<E> t) {
if (t == null){
return null;
}else if (t.left == null){
return t;
}
return findMin(t.left);
}
public void remove(E e){
root = remove(e, root);
}
public static void main(String[] args) {
AVLBinaryTree<Integer> avlBinaryTree = new AVLBinaryTree<Integer>();
avlBinaryTree.insert(3);
avlBinaryTree.insert(2);
avlBinaryTree.insert(1);
avlBinaryTree.insert(4);
avlBinaryTree.insert(5);
avlBinaryTree.remove(1);
avlBinaryTree.display();
avlBinaryTree.remove(4);
System.out.println();
avlBinaryTree.display();
}
}