说明
《数据结构与算法分析-java语言描述》 P86
AVL（Adelson-Velskii和Landis）树是**带有平衡条件（balance codition）**的二叉查找树。
平衡条件必须要容易保持，而且它保持树的深度是O(logN)。
代码结构
树的节点
（内部静态构造类）
属性：
- 左节点
- 右节点
- 记录的信息
- <mark>点高度</mark>
- 出现频率（也可以不要频率，节省空间）
/** * 内部 * 静态 * AVL * 节点 * @author Administrator * @param <T> */
private static class AVLNode<T>{
/** * 内部属性 */
private T elementData ;
private AVLNode<T> left ;
private AVLNode<T> right;
private int height ;
private int frequancy ;
/** * 构造方法 * @param elementData * @param left * @param right */
public AVLNode(T elementData, AVLNode<T> left, AVLNode<T> right) {
super();
this.elementData = elementData;
this.left = left;
this.right = right;
}
public AVLNode(T elementData) {
super();
this.elementData = elementData;
}
}
树的构造方法
树的构造和一些属性。
属性：
- 记录根节点 root
- 【不必要】记录对比方法 Comparator cmp
- findMin 找到最小的节点
package cn.edut.tree;
import java.util.Comparator;
public class AVLTree<T extends Comparable<? super T>> {
//属性
/** * 根节点 */
private AVLNode<T> root ;
private Comparator<? super T> cmp ;
//构造
public AVLTree(){
clear();
}
/** * 传入对比器的构造 * @param cmp */
public AVLTree(Comparator<? super T> cmp) {
clear();
this.cmp = cmp ;
}
public void setComparator(Comparator<? super T> cmp) {
this.cmp = cmp;
}
public void clear() {
root=null;
cmp = null;
}
private AVLNode<T> finMin(AVLNode<T> currentNode){
if(currentNode.left==null) {
//到最左边了 =》 发现最小
return currentNode ;
}else {
return finMin(currentNode.left);
}
}
}
计算节点高度
高度规定
null ： -1
leaf ： 0
…
/** * 返回AVLNode的高度， * 如果是null就返回-1 * @param currentNode * @return */
private int nodeHeight(AVLNode<T> currentNode) {
return currentNode!=null?currentNode.height:-1;
}
插入方法
与非平衡树的插入方法相同，
<mark>但返回的时候调用用下面说到的“树平衡”方法，让子树保持平衡 。</mark>
（树同时也就平衡了）
代码逻辑
- 如果节点为null 直接插入个 new 节点 。 返回
- 判断插入元素的大小，小向左递归，大向右递归，有相同节点就频率加1
（频率：Node的一个属性）
3.<mark>调用“subtreeBalance”方法，确保当前节点子树平衡</mark>。返回
/** * 插入的封装 * @param e */
public void insert(T e) {
root = insert(e , root);
}
/** * 插入的实现 * @param e * @param currentNode * @return */
private AVLNode<T> insert(T e ,AVLNode<T> currentNode){
//到了空节点
if(currentNode==null) {
AVLNode<T> temp = new AVLNode<T>(e , null , null);
temp.frequancy = 1;
return temp;
}
//对比
int flag ;
if(cmp!=null) {
//无参对比
flag = cmp.compare(e, currentNode.elementData);
} else {
//有参对比
flag = e.compareTo(currentNode.elementData);
}
//当前节点判断
if(flag<0) {//左移
currentNode.left = insert(e, currentNode.left);
}else if(flag>0) { //右移
currentNode.right = insert(e,currentNode.right);
}else {
//节点的频率加
currentNode.frequancy++;
}
return subtreeBalance(currentNode);
}
∗∗“树平衡”方法∗∗
代码思路
- 判断子节点高度差（高度差小于2）
- 高度差太高，就需要平衡
平衡
2.1. 找到高度比较高的节点，
2.2. 判断需要<mark>单旋</mark>还是<mark>双旋</mark>
3.3. 调用相应的方法- 最后，更新一下节点高度。返回
private final static int ALLOW_IMBALANCE = 1 ;
/** * 树平衡 * @return */
private AVLNode<T> subtreeBalance(AVLNode<T> currentNode){
//null，返回null
if(currentNode==null) { //base case
return currentNode;
}
if(nodeHeight(currentNode.right) - nodeHeight(currentNode.left) > ALLOW_IMBALANCE)
{//右边比较重
//比较右边的左右哪个重
if(nodeHeight(currentNode.right.left)
<= nodeHeight(currentNode.right.right))
//注意，这里的=号，因为删除操作中造成的不平衡，用这个单旋也能解决
{//还是，右边比较重
//右单旋
currentNode = singleRotate(currentNode , 'r') ;
}else
{//左边比较重
//双旋转
currentNode = doubleRotate(currentNode , 'r') ;
}
}
else
if(nodeHeight(currentNode.left) - nodeHeight(currentNode.right) > ALLOW_IMBALANCE)
{//左边比较重
//比较左边的左右哪个重
if(nodeHeight(currentNode.left.left)
>= nodeHeight(currentNode.left.right))
//注意，这里的=号，因为删除操作中造成的不平衡，用这个单旋也能解决
{//还是，左边比较重
//左单旋
currentNode = singleRotate(currentNode , 'l') ;
}else
{//右边比较重
//双旋转
currentNode = doubleRotate(currentNode , 'l') ;
}
}
currentNode.height =
Math.max(nodeHeight(currentNode.left), nodeHeight(currentNode.right))
+1;
return currentNode ;
}
∗∗单旋∗∗
/** * 单旋实现 * @param currentNode * @param flag * @return */
private AVLNode<T> singleRotate(AVLNode<T> currentNode , char flag){
AVLNode<T> returnNode = null;
if(flag == 'r') {
//右边单旋
returnNode = currentNode.right ;
currentNode.right = returnNode.left ;
returnNode.left = currentNode ;
}else if(flag == 'l') {
returnNode = currentNode.left ;
currentNode.left = returnNode.right;
returnNode.right = currentNode;
}else {
throw new RuntimeException("***用户传错值了:flag="+flag) ;
}
//更新节点
//先是currentNode
currentNode.height =
Math.max(nodeHeight(currentNode.left),nodeHeight(currentNode.right))
+1;
//然后是更新的节点
returnNode.height =
Math.max(nodeHeight(returnNode.left), nodeHeight(returnNode.right))
+1;
return returnNode;
}
∗∗双旋∗∗
/** * 双旋 * @param currentNode * @param flag * @return */
private AVLNode<T> doubleRotate(AVLNode<T> currentNode , char flag){
if(flag=='r') {
//先右节点，左旋
currentNode.right= singleRotate(currentNode.right, 'l');
//然后当前节点，右旋
currentNode = singleRotate(currentNode, 'r') ;
}else if(flag=='l'){
//先左节点，右旋
currentNode.left = singleRotate(currentNode.left, 'r');
currentNode = singleRotate(currentNode, 'l');
}else {
throw new RuntimeException("***用户传错值了:flag="+flag) ;
}
return currentNode ;
}
∗∗删除∗∗
public void remove(T e) {
root = remove(e , root ) ;
}
private AVLNode<T> remove(T e , AVLNode<T> currentNode){
//先处理空节点
if(currentNode==null) { // base case
return currentNode;
}
//比较
int flag ;
if(cmp!=null) {
flag = cmp.compare(e, currentNode.elementData);
}else {
flag = e.compareTo(currentNode.elementData);
}
//处理
if(flag<0) { //左移
currentNode.left = remove(e, currentNode.left);
}else if(flag>0) { // 右移动
currentNode.right = remove(e,currentNode.right) ;
}else {//找到当前值
if(currentNode.frequancy>1) {
currentNode.frequancy--;
}else {
if(currentNode.left!=null && currentNode.right!=null) {
//找到节点了，再判断是否右两个子节点
//右边最小值 赋予 当前值
AVLNode<T> minNode = finMin(currentNode.right);
currentNode.elementData = minNode.elementData;
currentNode.frequancy =minNode.frequancy ;
remove(minNode.elementData, currentNode.right);
}else {
currentNode = currentNode.left!=null?currentNode.left : currentNode.right ;
}
}
}
return subtreeBalance(currentNode);
}
测试
打印方法
public void listAll() {
listAll_mid(root , 0 );
}
private void listAll_mid(AVLNode<T> currentNode , int src) {
//先打印右边
if(currentNode.right!=null) {
listAll_mid(currentNode.right, src+1);
}
//打印当前的
System.out.print("[");
for(int i=0 ; i<src ; i++) {
System.out.print("~~~~~ ");
}
System.out.println(currentNode.elementData+":"+currentNode.frequancy+":"+currentNode.height);
//打印左边
if(currentNode.left != null) {
listAll_mid(currentNode.left, src+1);
}
}
测试代码
/** * 测试 * 0.无参构造 * 1. 插入（平衡插入） * 2. 打印 ： 右 - - - | * 中 ↓ * 左 左 中 右 */
public static void main(String[] args) {
//无参构造
AVLTree<Integer> avlTree = new AVLTree<>();
/* * 添加1:添加时，仅有单旋情况 */
//添加3 2 1
for(int i=3 ; i>0 ; i--) {
avlTree.insert(i);
}
//添加4~7
for(int i=4 ; i<=7 ; i++) {
avlTree.insert(i);
}
/* * 添加2:添加时，有双旋情况 */
//加 16~10
for(int i=16 ; i>=10 ; i--) {
avlTree.insert(i);
}
//加 8 9
for(int i=8 ; i<=9 ; i++) {
avlTree.insert(i);
}
/* * 打印结果树 */
System.out.println("----插入♂ 结果------" );
avlTree.listAll();
/* * 插入对比器，看效果（没啥用，手痒） */
avlTree.setComparator(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
/* * 删除，打印结果 */
//测试1： 删10 、删12 重构树
int num1 = 10 ;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
//
num1 = 12;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
//测试2： 删7，中间删除
num1 = 7;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
}
测试结果
−−−−插入♂结果−−−−−−
[~~~~~ ~~~~~ ~~~~~ 16:1:0
[~~~~~ ~~~~~ 15:1:1
[~~~~~ ~~~~~ ~~~~~ 14:1:0
[~~~~~ 13:1:3
[~~~~~ ~~~~~ ~~~~~ 12:1:0
[~~~~~ ~~~~~ 11:1:2
[~~~~~ ~~~~~ ~~~~~ ~~~~~ 10:1:0
[~~~~~ ~~~~~ ~~~~~ 9:1:1
[~~~~~ ~~~~~ ~~~~~ ~~~~~ 8:1:0
[7:1:4
[~~~~~ ~~~~~ 6:1:1
[~~~~~ ~~~~~ ~~~~~ 5:1:0
[~~~~~ 4:1:2
[~~~~~ ~~~~~ ~~~~~ 3:1:0
[~~~~~ ~~~~~ 2:1:1
[~~~~~ ~~~~~ ~~~~~ 1:1:0
−−−−−−−删除了：10−−−−−−−
[~~~~~ ~~~~~ ~~~~~ 16:1:0
[~~~~~ ~~~~~ 15:1:1
[~~~~~ ~~~~~ ~~~~~ 14:1:0
[~~~~~ 13:1:3
[~~~~~ ~~~~~ ~~~~~ 12:1:0
[~~~~~ ~~~~~ 11:1:2
[~~~~~ ~~~~~ ~~~~~ 9:1:1
[~~~~~ ~~~~~ ~~~~~ ~~~~~ 8:1:0
[7:1:4
[~~~~~ ~~~~~ 6:1:1
[~~~~~ ~~~~~ ~~~~~ 5:1:0
[~~~~~ 4:1:2
[~~~~~ ~~~~~ ~~~~~ 3:1:0
[~~~~~ ~~~~~ 2:1:1
[~~~~~ ~~~~~ ~~~~~ 1:1:0
−−−−−−−删除了：12−−−−−−−
[~~~~~ ~~~~~ ~~~~~ 16:1:0
[~~~~~ ~~~~~ 15:1:1
[~~~~~ ~~~~~ ~~~~~ 14:1:0
[~~~~~ 13:1:2
[~~~~~ ~~~~~ ~~~~~ 11:1:0
[~~~~~ ~~~~~ 9:1:1
[~~~~~ ~~~~~ ~~~~~ 8:1:0
[7:1:3
[~~~~~ ~~~~~ 6:1:1
[~~~~~ ~~~~~ ~~~~~ 5:1:0
[~~~~~ 4:1:2
[~~~~~ ~~~~~ ~~~~~ 3:1:0
[~~~~~ ~~~~~ 2:1:1
[~~~~~ ~~~~~ ~~~~~ 1:1:0
−−−−−−−删除了：7−−−−−−−
[~~~~~ ~~~~~ ~~~~~ 16:1:0
[~~~~~ ~~~~~ 15:1:1
[~~~~~ ~~~~~ ~~~~~ 14:1:0
[~~~~~ 13:1:2
[~~~~~ ~~~~~ ~~~~~ 11:1:0
[~~~~~ ~~~~~ 9:1:1
[8:1:3
[~~~~~ ~~~~~ 6:1:1
[~~~~~ ~~~~~ ~~~~~ 5:1:0
[~~~~~ 4:1:2
[~~~~~ ~~~~~ ~~~~~ 3:1:0
[~~~~~ ~~~~~ 2:1:1
[~~~~~ ~~~~~ ~~~~~ 1:1:0
完整代码
package cn.edut.tree;
import java.util.Comparator;
public class AVLTree<T extends Comparable<? super T>> {
/** * 测试 * 0.无参构造 * 1. 插入（平衡插入） * 2. 打印 ： 右 - - - | * 中 ↓ * 左 左 中 右 */
public static void main(String[] args) {
//无参构造
AVLTree<Integer> avlTree = new AVLTree<>();
/* * 添加1:添加时，仅有单旋情况 */
//添加3 2 1
for(int i=3 ; i>0 ; i--) {
avlTree.insert(i);
}
//添加4~7
for(int i=4 ; i<=7 ; i++) {
avlTree.insert(i);
}
/* * 添加2:添加时，有双旋情况 */
//加 16~10
for(int i=16 ; i>=10 ; i--) {
avlTree.insert(i);
}
//加 8 9
for(int i=8 ; i<=9 ; i++) {
avlTree.insert(i);
}
/* * 打印结果树 */
System.out.println("----插入♂ 结果------" );
avlTree.listAll();
/* * 插入对比器，看效果（没啥用，手痒） */
avlTree.setComparator(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
/* * 删除，打印结果 */
//测试1： 删10 、删12 重构树
int num1 = 10 ;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
//
num1 = 12;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
//测试2： 删7，中间删除
num1 = 7;
System.out.println("-------删除了："+num1+"-------");
avlTree.remove(num1);
avlTree.listAll();
}
//属性
/** * 根节点 */
private AVLNode<T> root ;
private Comparator<? super T> cmp ;
//构造
public AVLTree(){
clear();
}
/** * 传入对比器的构造 * @param cmp */
public AVLTree(Comparator<? super T> cmp) {
clear();
this.cmp = cmp ;
}
public void setComparator(Comparator<? super T> cmp) {
this.cmp = cmp;
}
public void clear() {
root=null;
cmp = null;
}
public void remove(T e) {
root = remove(e , root ) ;
}
private AVLNode<T> remove(T e , AVLNode<T> currentNode){
//先处理空节点
if(currentNode==null) { // base case
return currentNode;
}
//比较
int flag ;
if(cmp!=null) {
flag = cmp.compare(e, currentNode.elementData);
}else {
flag = e.compareTo(currentNode.elementData);
}
//处理
if(flag<0) { //左移
currentNode.left = remove(e, currentNode.left);
}else if(flag>0) { // 右移动
currentNode.right = remove(e,currentNode.right) ;
}else {//找到当前值
if(currentNode.frequancy>1) {
currentNode.frequancy--;
}else {
if(currentNode.left!=null && currentNode.right!=null) {
//找到节点了，再判断是否右两个子节点
//右边最小值 赋予 当前值
AVLNode<T> minNode = finMin(currentNode.right);
currentNode.elementData = minNode.elementData;
currentNode.frequancy =minNode.frequancy ;
remove(minNode.elementData, currentNode.right);
}else {
currentNode = currentNode.left!=null?currentNode.left : currentNode.right ;
}
}
}
return subtreeBalance(currentNode);
}
public void listAll() {
listAll_mid(root , 0 );
}
private void listAll_mid(AVLNode<T> currentNode , int src) {
//先打印右边
if(currentNode.right!=null) {
listAll_mid(currentNode.right, src+1);
}
//打印当前的
System.out.print("[");
for(int i=0 ; i<src ; i++) {
System.out.print("~~~~~ ");
}
System.out.println(currentNode.elementData+":"+currentNode.frequancy+":"+currentNode.height);
//打印左边
if(currentNode.left != null) {
listAll_mid(currentNode.left, src+1);
}
}
/** * 插入的封装 * @param e */
public void insert(T e) {
root = insert(e , root);
}
/** * 插入的实现 * @param e * @param currentNode * @return */
private AVLNode<T> insert(T e ,AVLNode<T> currentNode){
//到了空节点
if(currentNode==null) {
AVLNode<T> temp = new AVLNode<T>(e , null , null);
temp.frequancy = 1;
return temp;
}
//对比
int flag ;
if(cmp!=null) {
//无参对比
flag = cmp.compare(e, currentNode.elementData);
} else {
//有参对比
flag = e.compareTo(currentNode.elementData);
}
//当前节点判断
if(flag<0) {//左移
currentNode.left = insert(e, currentNode.left);
}else if(flag>0) { //右移
currentNode.right = insert(e,currentNode.right);
}else {
//节点的频率加
currentNode.frequancy++;
}
return subtreeBalance(currentNode);
}
private AVLNode<T> finMin(AVLNode<T> currentNode){
if(currentNode.left==null) {
//到最左边了 =》 发现最小
return currentNode ;
}else {
return finMin(currentNode.left);
}
}
private final static int ALLOW_IMBALANCE = 1 ;
/** * 树平衡 * @return */
private AVLNode<T> subtreeBalance(AVLNode<T> currentNode){
//null，返回null
if(currentNode==null) { //base case
return currentNode;
}
if(nodeHeight(currentNode.right) - nodeHeight(currentNode.left) > ALLOW_IMBALANCE)
{//右边比较重
//比较右边的左右哪个重
if(nodeHeight(currentNode.right.left)
<= nodeHeight(currentNode.right.right))
//注意，这里的=号，因为删除操作中造成的不平衡，用这个单旋也能解决
{//还是，右边比较重
//右单旋
currentNode = singleRotate(currentNode , 'r') ;
}else
{//左边比较重
//双旋转
currentNode = doubleRotate(currentNode , 'r') ;
}
}
else
if(nodeHeight(currentNode.left) - nodeHeight(currentNode.right) > ALLOW_IMBALANCE)
{//左边比较重
//比较左边的左右哪个重
if(nodeHeight(currentNode.left.left)
>= nodeHeight(currentNode.left.right))
//注意，这里的=号，因为删除操作中造成的不平衡，用这个单旋也能解决
{//还是，左边比较重
//左单旋
currentNode = singleRotate(currentNode , 'l') ;
}else
{//右边比较重
//双旋转
currentNode = doubleRotate(currentNode , 'l') ;
}
}
currentNode.height =
Math.max(nodeHeight(currentNode.left), nodeHeight(currentNode.right))
+1;
return currentNode ;
}
/** * 双旋 * @param currentNode * @param flag * @return */
private AVLNode<T> doubleRotate(AVLNode<T> currentNode , char flag){
if(flag=='r') {
//先右节点，左旋
currentNode.right= singleRotate(currentNode.right, 'l');
//然后当前节点，右旋
currentNode = singleRotate(currentNode, 'r') ;
}else if(flag=='l'){
//先左节点，右旋
currentNode.left = singleRotate(currentNode.left, 'r');
currentNode = singleRotate(currentNode, 'l');
}else {
throw new RuntimeException("***用户传错值了:flag="+flag) ;
}
return currentNode ;
}
/** * 单旋实现 * @param currentNode * @param flag * @return */
private AVLNode<T> singleRotate(AVLNode<T> currentNode , char flag){
AVLNode<T> returnNode = null;
if(flag == 'r') {
//右边单旋
returnNode = currentNode.right ;
currentNode.right = returnNode.left ;
returnNode.left = currentNode ;
}else if(flag == 'l') {
returnNode = currentNode.left ;
currentNode.left = returnNode.right;
returnNode.right = currentNode;
}else {
throw new RuntimeException("***用户传错值了:flag="+flag) ;
}
//更新节点
//先是currentNode
currentNode.height =
Math.max(nodeHeight(currentNode.left),nodeHeight(currentNode.right))
+1;
//然后是更新的节点
returnNode.height =
Math.max(nodeHeight(returnNode.left), nodeHeight(returnNode.right))
+1;
return returnNode;
}
/** * 返回AVLNode的高度， * 如果是null就返回-1 * @param currentNode * @return */
private int nodeHeight(AVLNode<T> currentNode) {
return currentNode!=null?currentNode.height:-1;
}
/** * 内部 * 静态 * AVL * 节点 * @author Administrator * @param <T> */
private static class AVLNode<T>{
/** * 内部属性 */
private T elementData ;
private AVLNode<T> left ;
private AVLNode<T> right;
private int height ;
private int frequancy ;
/** * 构造方法 * @param elementData * @param left * @param right */
public AVLNode(T elementData, AVLNode<T> left, AVLNode<T> right) {
super();
this.elementData = elementData;
this.left = left;
this.right = right;
}
public AVLNode(T elementData) {
super();
this.elementData = elementData;
}
}
}
后记
这里写的也挺好的：
- 《java数据结构与算法之平衡二叉树(AVL树)的设计与实现》https://blog.csdn.net/javazejian/article/details/53892797
京公网安备 11010502036488号