本文将详细讲解平衡二叉树的实现原理，在阅读本文章前，我假设你已经对平衡二叉树有基本的了解，并且已经阅读了
http://zhouyunan2010.iteye.com/blog/1255299关于二叉排序树的实现。
package com.utils;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 平衡二叉树
* 定义:首先它是一种特殊的二叉排序树，其次它的左子树和右子树都是平衡二叉树，
* 且左子树和右子树的深度之差不超过1
* 平衡因子:可以定义为左子树的深度减去右子树的深度
*
* 平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况下平均查找时间为n，
* 二叉排序树在此时形如一个单链表
* 平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN
*/
public class AVLTree<E> {
/**
* 根节点
*/
private Entry<E> root = null;
/**
* 树中元素个数
*/
private int size = 0;
public AVLTree(){
}
public int size(){
return size;
}
/**
* @param p 最小旋转子树的根节点
* 向左旋转之后p移到p的左子树处，p的右子树B变为此最小子树根节点，
* B的左子树变为p的右子树
* 比如： A(-2) B(1)
* \ 左旋转 / \
* B(0) ----> A(0) \
* / \ \ \
* BL(0) BR(0) BL(0) BR(0)
* 旋转之后树的深度之差不超过1
*/
private void rotateLeft(Entry<E> p) {
System.out.println("绕"+p.element+"左旋");
if(p!=null){
Entry<E> r = p.right;
p.right = r.left; //把p右子树的左节点嫁接到p的右节点，如上图，把BL作为A的右子节点
if (r.left != null) //如果B的左节点BL不为空，把BL的父节点设为A
r.left.parent = p;
r.parent = p.parent; //A的父节点设为B的父节点
if (p.parent == null) //如果p是根节点
root = r; //r变为父节点，即B为父节点
else if (p.parent.left == p) //如果p是左子节点
p.parent.left = r; //p的父节点的左子树为r
else //如果p是右子节点
p.parent.right = r; //p的父节点的右子树为r
r.left = p; //p变为r的左子树，即A为B的左子树
p.parent = r; //同时更改p的父节点为r，即A的父节点为B
}
}
/**
* @param p 最小旋转子树的根节点
* 向右旋转之后，p移到p的右子节点处，p的左子树B变为最小旋转子树的根节点
* B的右子节点变为p的左节点、
* 例如: A(2) B(-1)
* / 右旋转 / \
* B(0) ------> / A(0)
* / \ / /
* BL(0) BR(0) BL(0) BR(0)
*/
private void rotateRight(Entry<E> p){
System.out.println("绕"+p.element+"右旋");
if(p!=null){
Entry<E> l = p.left;
p.left = l.right; //把B的右节点BR作为A的左节点
if (l.right != null) //如果BR不为null，设置BR的父节点为A
l.right.parent = p;
l.parent = p.parent; //A的父节点赋给B的父节点
if (p.parent == null) //如果p是根节点
root = l; //B为根节点
else if (p.parent.right == p) //如果A是其父节点的左子节点
p.parent.right = l; //B为A的父节点的左子树
else //如果A是其父节点的右子节点
p.parent.left = l; //B为A的父节点的右子树
l.right = p; //A为B的右子树
p.parent = l; //设置A的父节点为B
}
}
/**
* 平衡而二叉树的插入操作
* 基本原理为：
* 1.首先如同二叉排序树一般，找到其要插入的节点的位置，并把元素插入其中；
* 2.自下向上进行回溯，回溯做两个事情：
* (1)其一是修改祖先节点的平衡因子，当插入 一个节点时只有根节点到插入节点
* 的路径中的节点的平衡因子会被改变，而且改变的原则是当插入节点在某节点(称为A)
* 的左子树 中时，A的平衡因子(称为BF)为BF+1,当插入节点在A的右子树中时A的BF-1，
* 而判断插入节点在左子树中还是右子树中只要简单的比较它与A的大小
* (2)在改变祖先节点的平衡因子的同时，找到最近一个平衡因子大于2或小于-2的节点，
* 从这个节点开始调整最小不平衡树进行旋转调整，关于如何调整见下文。
* 由于调整后，最小不平衡子树的高度与插入节点前的高度相同，故不需继续要调整祖先节点。
* 这里还有一个特殊情况，如果调整BF时，发现某个节点的BF变为0了，则停止向上继续调整，
* 因为这表明此节点中高度小的子树增加了新节点，高度不变，那么祖先节点的BF自然不变。
*
*
*/
public boolean add(E element){
Entry<E> t = root;
if(t == null){
root = new Entry<E>(element,null);
size = 1;
return true;
}
int cmp;
Entry<E> parent; //保存t的父节点
Comparable<? super E> e = (Comparable<? super E>) element;
//从根节点向下搜索，找到插入位置
do {
parent = t;
cmp = e.compareTo(t.element);
if(cmp < 0){
t = t.left;
}else if(cmp > 0){
t = t.right;
}else{
return false;
}
} while (t!=null);
Entry<E> child = new Entry(element,parent);
if(cmp < 0){
parent.left = child;
}else{
parent.right = child;
}
//自下向上回溯，查找最近不平衡节点
while(parent!=null){
cmp = e.compareTo(parent.element);
if(cmp < 0){ //插入节点在parent的左子树中
parent.balance++;
}else{ //插入节点在parent的右子树中
parent.balance--;
}
if(parent.balance == 0){ //此节点的balance为0，不再向上调整BF值，且不需要旋转
break;
}
if(Math.abs(parent.balance) == 2){ //找到最小不平衡子树根节点
fixAfterInsertion(parent);
break; //不用继续向上回溯
}
parent = parent.parent;
}
size ++;
return true;
}
/**
* 调整的方法：
* 1.当最小不平衡子树的根(以下简称R)为2时，即左子树高于右子树：
* 如果R的左子树的根节点的BF为1时，做右旋；
* 如果R的左子树的根节点的BF为-1时，先左旋然后再右旋
*
* 2.R为-2时，即右子树高于左子树：
* 如果R的右子树的根节点的BF为1时，先右旋后左旋
* 如果R的右子树的根节点的BF为-1时，做左旋
*
* 至于调整之后，各节点的BF变化见代码
*/
private void fixAfterInsertion(Entry<E> p){
if(p.balance == 2){
leftBalance(p);
}
if(p.balance == -2){
rightBalance(p);
}
}
/**
* 做左平衡处理
* 平衡因子的调整如图：
* t rd
* / \ / \
* l tr 左旋后右旋 l t
* / \ -------> / \ / \
* ll rd ll rdl rdr tr
* / \
* rdl rdr
*
* 情况2(rd的BF为0)
*
*
* t rd
* / \ / \
* l tr 左旋后右旋 l t
* / \ -------> / \ \
* ll rd ll rdl tr
* /
* rdl
*
* 情况1(rd的BF为1)
*
*
* t rd
* / \ / \
* l tr 左旋后右旋 l t
* / \ -------> / / \
* ll rd ll rdr tr
* \
* rdr
*
* 情况3(rd的BF为-1)
*
*
* t l
* / 右旋处理 / \
* l ------> ll t
* / \ /
* ll rd rd
* 情况4(L等高)
*/
private boolean leftBalance(Entry<E> t){
boolean heightLower = true;
Entry<E> l = t.left;
switch (l.balance) {
case LH: //左高，右旋调整,旋转后树的高度减小
t.balance = l.balance = EH;
rotateRight(t);
break;
case RH: //右高，分情况调整
Entry<E> rd = l.right;
switch (rd.balance) { //调整各个节点的BF
case LH: //情况1
t.balance = RH;
l.balance = EH;
break;
case EH: //情况2
t.balance = l.balance = EH;
break;
case RH: //情况3
t.balance = EH;
l.balance = LH;
break;
}
rd.balance = EH;
rotateLeft(t.left);
rotateRight(t);
break;
case EH: //特殊情况4,这种情况在添加时不可能出现，只在移除时可能出现，旋转之后整体树高不变
l.balance = RH;
t.balance = LH;
rotateRight(t);
heightLower = false;
break;
}
return heightLower;
}
/**
* 做右平衡处理
* 平衡因子的调整如图：
* t ld
* / \ / \
* tl r 先右旋再左旋 t r
* / \ --------> / \ / \
* ld rr tl ldl ldr rr
* / \
* ldl ldr
* 情况2(ld的BF为0)
*
* t ld
* / \ / \
* tl r 先右旋再左旋 t r
* / \ --------> / \ \
* ld rr tl ldl rr
* /
* ldl
* 情况1(ld的BF为1)
*
* t ld
* / \ / \
* tl r 先右旋再左旋 t r
* / \ --------> / / \
* ld rr tl ldr rr
* \
* ldr
* 情况3(ld的BF为-1)
*
* t r
* \ 左旋 / \
* r -------> t rr
* / \ \
* ld rr ld
* 情况4(r的BF为0)
*/
private boolean rightBalance(Entry<E> t){
boolean heightLower = true;
Entry<E> r = t.right;
switch (r.balance) {
case LH: //左高，分情况调整
Entry<E> ld = r.left;
switch (ld.balance) { //调整各个节点的BF
case LH: //情况1
t.balance = EH;
r.balance = RH;
break;
case EH: //情况2
t.balance = r.balance = EH;
break;
case RH: //情况3
t.balance = LH;
r.balance = EH;
break;
}
ld.balance = EH;
rotateRight(t.right);
rotateLeft(t);
break;
case RH: //右高，左旋调整
t.balance = r.balance = EH;
rotateLeft(t);
break;
case EH: //特殊情况4
r.balance = LH;
t.balance = RH;
rotateLeft(t);
heightLower = false;
break;
}
return heightLower;
}
/**
* 查找指定元素，如果找到返回其Entry对象，否则返回null
*/
private Entry<E> getEntry(Object element) {
Entry<E> tmp = root;
Comparable<? super E> e = (Comparable<? super E>) element;
int c;
while (tmp != null) {
c = e.compareTo(tmp.element);
if (c == 0) {
return tmp;
} else if (c < 0) {
tmp = tmp.left;
} else {
tmp = tmp.right;
}
}
return null;
}
/**
* 平衡二叉树的移除元素操作
*
*/
public boolean remove(Object o){
Entry<E> e = getEntry(o);
if(e!=null){
deleteEntry(e);
return true;
}
return false;
}
private void deleteEntry(Entry<E> p){
size --;
//如果p左右子树都不为空，找到其直接后继，替换p，之后p指向s，删除p其实是删除s
//所有的删除左右子树不为空的节点都可以调整为删除左右子树有其一不为空，或都为空的情况。
if (p.left != null && p.right != null) {
Entry<E> s = successor(p);
p.element = s.element;
p = s;
}
Entry<E> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) { //如果其左右子树有其一不为空
replacement.parent = p.parent;
if (p.parent == null) //如果p为root节点
root = replacement;
else if (p == p.parent.left) //如果p是左孩子
p.parent.left = replacement;
else //如果p是右孩子
p.parent.right = replacement;
p.left = p.right = p.parent = null; //p的指针清空
//这里更改了replacement的父节点，所以可以直接从它开始向上回溯
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 如果全树只有一个节点
root = null;
} else { //左右子树都为空
fixAfterDeletion(p); //这里从p开始回溯
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
/**
* 返回以中序遍历方式遍历树时，t的直接后继
*/
static <E> Entry<E> successor(Entry<E> t) {
if (t == null)
return null;
else if (t.right != null) { //往右，然后向左直到尽头
Entry<E> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else { //right为空，如果t是p的左子树，则p为t的直接后继
Entry<E> p = t.parent;
Entry<E> ch = t;
while (p != null && ch == p.right) { //如果t是p的右子树，则继续向上搜索其直接后继
ch = p;
p = p.parent;
}
return p;
}
}
/**
* 删除某节点p后的调整方法：
* 1.从p开始向上回溯，修改祖先的BF值，这里只要调整从p的父节点到根节点的BF值，
* 调整原则为，当p位于某祖先节点(简称A)的左子树中时，A的BF减1，当p位于A的
* 右子树中时A的BF加1。当某个祖先节点BF变为1或-1时停止回溯，这里与插入是相反的，
* 因为原本这个节点是平衡的，删除它的子树的某个节点并不会改变它的高度
*
* 2.检查每个节点的BF值，如果为2或-2需要进行旋转调整，调整方法如下文，
* 如果调整之后这个最小子树的高度降低了，那么必须继续从这个最小子树的根节点(假设为B)继续
* 向上回溯，这里和插入不一样，因为B的父节点的平衡性因为其子树B的高度的改变而发生了改变，
* 那么就可能需要调整，所以删除可能进行多次的调整。
*
*/
private void fixAfterDeletion(Entry<E> p){
boolean heightLower = true; //看最小子树调整后，它的高度是否发生变化，如果减小，继续回溯
Entry<E> t = p.parent;
Comparable<? super E> e = (Comparable<? super E>)p.element;
int cmp;
//自下向上回溯，查找不平衡的节点进行调整
while(t!=null && heightLower){
cmp = e.compareTo(t.element);
/**
* 删除的节点是右子树，等于的话，必然是删除的某个节点的左右子树不为空的情况
* 例如： 10
* / \
* 5 15
* / \
* 3 6
* 这里删除5，是把6的值赋给5，然后删除6，这里6是p，p的父节点的值也是6。
* 而这也是右子树的一种
*/
if(cmp >= 0 ){
t.balance ++;
}else{
t.balance --;
}
if(Math.abs(t.balance) == 1){ //父节点经过调整平衡因子后，如果为1或-1，说明调整之前是0，停止回溯。
break;
}
Entry<E> r = t;
//这里的调整跟插入一样
if(t.balance == 2){
heightLower = leftBalance(r);
}else if(t.balance==-2){
heightLower = rightBalance(r);
}
t = t.parent;
}
}
private static final int LH = 1; //左高
private static final int EH = 0; //等高
private static final int RH = -1; //右高
/**
* 树节点，为方便起见不写get，Set方法
*/
static class Entry<E>{
E element;
Entry<E> parent;
Entry<E> left;
Entry<E> right;
int balance = EH; //平衡因子，只能为1或0或-1
public Entry(E element,Entry<E> parent){
this.element = element;
this.parent = parent;
}
public Entry(){}
@Override
public String toString() {
return element+" BF="+balance;
}
}
//返回中序遍历此树的迭代器,返回的是一个有序列表
private class BinarySortIterator implements Iterator<E>{
Entry<E> next;
Entry<E> lastReturned;
public BinarySortIterator(){
Entry<E> s = root;
if(s !=null){
while(s.left != null){ //找到中序遍历的第一个元素
s = s.left;
}
}
next = s; //赋给next
}
@Override
public boolean hasNext() {
return next!=null;
}
@Override
public E next() {
Entry<E> e = next;
if (e == null)
throw new NoSuchElementException();
next = successor(e);
lastReturned = e;
return e.element;
}
@Override
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
lastReturned = null;
}
}
public Iterator<E> itrator(){
return new BinarySortIterator();
}
private int treeHeight(Entry<E> p){
if(p == null){
return -1;
}
return 1 + Math.max(treeHeight(p.left), treeHeight(p.right));
}
//测试，你也可以任意测试
public static void main(String[] args) {
AVLTree<Integer> tree = new AVLTree<Integer>();
System.out.println("------添加------");
tree.add(50);
System.out.print(50+" ");
tree.add(66);
System.out.print(66+" ");
for(int i=0;i<10;i++){
int ran = (int)(Math.random() * 100);
System.out.print(ran+" ");
tree.add(ran);
}
System.out.println("------删除------");
tree.remove(50);
tree.remove(66);
System.out.println();
Iterator<Integer> it = tree.itrator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
}
}
分享到：
相关推荐
在Java编程领域，平衡二叉树（特别是AVL树）是一种高效的数据结构，它通过保持树的高度平衡来确保查找、插入和删除操作的最优化。AVL树是最早被提出的自平衡二叉搜索树，由G. M. Adelson-Velsky和E. M. Landis于1962...
此外，二叉树的应用还包括在构建二叉搜索树、平衡二叉树、堆等特殊二叉树结构时使用，这些结构在数据库索引、优先级队列等场景中有广泛的应用。 总之，Java实现二叉树的最佳方法依赖于对二叉树性质的深入理解以及对...
- 二叉树类型：满二叉树、完全二叉树、平衡二叉树（如AVL树、红黑树）等。 - 特殊操作：插入、删除、查找等操作在二叉树中的实现。 2. **Java编程**： - 类与对象：二叉树的实现通常通过创建一个表示节点的类，...
对于平衡树，ASL通常低于非平衡二叉树，因为它保持了良好的高度平衡。项目中计算ASL的功能可以帮助评估和优化查找性能。 总的来说，这个Java GUI项目提供了一个实践平台，用于理解和操作二叉树和平衡树，涵盖了基本...
3. 平衡二叉树：如AVL树和红黑树，这类二叉树保持左右子树的高度差不超过1，以确保高效的查找性能。 Java实现二叉树通常涉及以下概念： 1. 节点类：每个节点通常包含一个值（数据），以及指向左子节点和右子节点的...
此外，可能还会涉及到对这两种树的性能分析，比较它们在不同场景下的优劣，以及如何根据具体需求选择合适的平衡二叉树。 为了完成这样的课程设计，学生需要具备扎实的二叉树基础知识，理解二叉搜索树的性质，并能...
在Java中实现平衡二叉树，通常会用到AVL树或红黑树等算法。 AVL树是最早被提出的一种自平衡二叉搜索树，由G. M. Adelson-Velsky和E. M. Landis于1962年提出，因此得名AVL树。AVL树的关键特性是保持平衡因子为-1、0...
4. **平衡二叉树**：为了保持二叉搜索树的性能，我们需要保持树的平衡。AVL树和红黑树是两种常见的自平衡二叉搜索树，它们通过旋转操作确保树的高度平衡，从而优化查找效率。 5. **树的其他操作**：除了基本操作外...
java数据结构与算法之平衡二叉树的设计与实现分析.pdf
不平衡的二叉树可能会导致性能下降，因此有自平衡二叉树如AVL树和红黑树等，它们在插入或删除后会通过旋转操作保持树的高度平衡，从而确保搜索效率。 此外，二叉树还可以扩展为更复杂的数据结构，如B树和B+树，常...
下面将详细介绍二叉树的概念、常见类型以及在Java中的具体实现。 二叉树定义： 二叉树是由n（n>=0）个有限节点组成的一个有穷集合。这个集合满足以下条件： 1. 有一个特定的称为根的节点。 2. 每个节点最多有两个子...
java数据结构与算法之平衡二叉树AVL树的设计与实现分析.doc
以上仅是二叉树操作的一部分，实际的`BinaryTree.java`文件可能包含更多功能，如层序遍历、最小（最大）元素查找、平衡二叉树操作等。二叉树的性质和操作是数据结构和算法课程的重点，熟练掌握这些概念和实现对于...
这里我们关注的是“创建二叉树”的Java程序，这涉及到对二叉树概念的理解，以及如何用Java语言来实现它。 首先，我们要理解什么是二叉树。二叉树是每个节点最多有两个子节点的树形数据结构，通常分为左子节点和右子...
平衡二叉树（AVL树）是数据结构与算法领域中的一个重要概念，它是一种自平衡的二叉查找树。在AVL树中，任何节点的两个子树的高度差最多为1，这确保了树的平衡性，从而保证了在最佳情况下操作的时间复杂度为O(log n)...
总之，这个Java实现的二叉树是一个典型的二叉搜索树，其节点存储字符串，且遵循严格的大小规则，使得它在处理字符串数据时具有高效的操作性能。理解并掌握这样的数据结构对于任何IT专业人员来说都是至关重要的，无论...
通过分析这个源码，我们可以更深入地理解二叉树的原理和Java中的实现细节。同时，学习如何使用工具（如IDE、调试器、代码分析工具等）来辅助理解和调试这个程序也是很重要的实践技能。 总之，二叉树是数据结构中的...
5. **平衡二叉树（Balanced Binary Trees）**：为了优化查找效率，有时我们需要保持二叉树的高度平衡，例如AVL树和红黑树。这类平衡二叉树在插入和删除操作后，会自动调整以保持平衡。 6. **二叉堆（Binary Heap）*...
在Java实现中，`isBalanced`函数首先检查根节点是否为空，如果不为空，就计算左右子树的高度差并进行递归判断。`height`函数则用于计算节点的高度，返回左右子树中最大高度加1。这种方法虽然直观，但可能会对同一...