AVL二进制排序树的Java实现

在过去的两天里，我终于了解了AVL树. 在“算法分析和设计基础”一书中，将其安排在变更治理一章中，这是示例简化思想在搜索树中的应用. 它对平衡的要求是: 每个节点的左右子树之间的高度差不超过1. 因此，我们仅需在插入或删除节点时确保这种平衡. 如果天平破裂，请进行一系列旋转使树恢复平衡.

共有四种旋转类型: 左单圈，右单圈，左和右双圈，右和左双圈. 只要提到AVL树的算法手册，就会有一个轮换说明. 它在两个单圈和两个双圈之间是对称的. 看似复杂的双转弯，其想法是首先转换为单转弯，以便通过单转弯实现再平衡. 因此，这四个旋转的实现非常简单.

由于每次旋转，我们都可以将树的高度恢复到插入前的水平实现二叉排序树，因此当天平损坏时，仅旋转一圈就可以解决问题. 需要旋转的是插入节点所在的最小子树，左右子树之间的高度差大于1.

由于AVL树是平衡搜索树，因此从普通的二进制搜索树中更容易记住.

二叉树的插入以递归的方式执行，可以非常清楚地表达算法思想. 应该注意的是，指针不能在java实现中使用，因此与c ++相比，必须注意将插入的节点挂到原始树上.

public class BinarySortTree {
	
	//节点结构
	public static class BinaryTreeNode{
		int v,height;
		BinaryTreeNode leftChild,rightChild;
		public BinaryTreeNode(int v){
			this.v = v;
			this.leftChild = null;
			this.rightChild = null;
			this.height = 0;
		}
		
		public BinaryTreeNode(int v, BinaryTreeNode leftChild,
				BinaryTreeNode rightChild,int height) {
			super();
			this.v = v;
			this.leftChild = leftChild;
			this.rightChild = rightChild;
			this.height = height;
		}
		
	}
	
	//需要处理空节点，为空时高为-1
	public static int height(BinaryTreeNode node){
		return node == null ? -1:node.height;
	}
	
	private BinaryTreeNode root;
	public BinaryTreeNode getRoot() {
		return root;
	}
	public void insert(int value){
		this.root = insert(value,this.root);
	}
	
	//递归插入
	public BinaryTreeNode insert(int value,BinaryTreeNode t){
		if(t == null){
			return new BinaryTreeNode(value);
		}
		//插入值与当前节点比较，小于插入到左子树，大于插入到右子树
		if(value < t.v){
			t.leftChild = insert(value,t.leftChild);
		}else if(value > t.v){							
			t.rightChild = insert(value,t.rightChild);	
		}else{/*equal,do nothing*/}
		//更新高度
		t.height = Math.max(height(t.leftChild), height(t.rightChild)) + 1;
		return t;
	}
}

有了这个基础，便可以达到平衡. 所需的工作是进行4次旋转，并在插入时重写插入方法，如果天平损坏，则旋转以恢复天平.

public class AvlTree extends BinarySortTree{
	
	public BinaryTreeNode rotateWithLeftChild(BinaryTreeNode k2){
		BinaryTreeNode k1 = k2.leftChild;
		k2.leftChild= k1.rightChild;
		k1.rightChild = k2;
		//重新计算高度
		k2.height = Math.max(height(k2.leftChild),height(k2.rightChild)) + 1;
		k1.height = Math.max(height(k1.leftChild), k2.height) +1;
		return k1;
	}
	
	public BinaryTreeNode rotateWithRightChild(BinaryTreeNode k2){
		BinaryTreeNode k1 = k2.rightChild;
		k2.rightChild= k1.leftChild;
		k1.leftChild = k2;
		//重新计算高度
		k2.height = Math.max(height(k2.leftChild),height(k2.rightChild)) + 1;
		k1.height = Math.max(height(k1.rightChild), k2.height) +1;
		return k1;
	}
	public BinaryTreeNode doubleWithLeftChild(BinaryTreeNode k3){
		k3.leftChild = rotateWithRightChild(k3.leftChild);
		return rotateWithLeftChild(k3);
	}
	public BinaryTreeNode doubleWithRightChild(BinaryTreeNode k3){
		k3.rightChild = rotateWithLeftChild(k3.rightChild);
		return rotateWithRightChild(k3);
	}
	@Override
	public BinaryTreeNode insert(int value, BinaryTreeNode t) {
		if(t == null){
			return new BinaryTreeNode(value);
		}
		//插入值与当前节点比较，小于插入到左子树，大于插入到右子树
		if(value < t.v){
			t.leftChild = insert(value,t.leftChild);
			//判断平衡是否被破坏
			if(height(t.leftChild) - height(t.rightChild) == 2){
				if(value < t.leftChild.v){
					t = rotateWithLeftChild(t);
				}else if(value > t.leftChild.v){
					t = doubleWithLeftChild(t);
				}else{/*impossible do nothing*/}
			}
		}else if(value > t.v){
			t.rightChild = insert(value,t.rightChild);	
			//判断平衡是否被破坏
			if(height(t.rightChild) - height(t.leftChild) == 2){
				if(value > t.rightChild.v){
					t = rotateWithRightChild(t);
				}else if(value < t.rightChild.v){
					t = doubleWithRightChild(t);
				}else{/*impossible do nothing*/}
			}
		}else{/*equal,do nothing*/}
		//更新高度
		t.height = Math.max(height(t.leftChild), height(t.rightChild)) + 1;
		return t;
	}
}

使用groovy进行单元测试，同时使用中间顺序遍历输出实现二叉排序树，更直观:

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
import binaryTree.BinarySortTree.BinaryTreeNode;
class TestBinaryTree {
	int[] date = [1,6,4,3,9,2,8,7]
	
	@Test
	public void testBinarySortTree() {
		BinarySortTree tree = new BinarySortTree();
		date.each{
			tree.insert(it);
		}
		show(tree);
		assertEquals tree.getRoot().rightChild.leftChild.v,4
	}
	@Test
	public void testAvlTree(){
		AvlTree tree = new AvlTree();
		date.each{
			tree.insert(it);
		}
		show(tree);
		assertEquals tree.getRoot().leftChild.rightChild.v,3
		tree.insert(5)
		show(tree);
		assertEquals tree.getRoot().rightChild.leftChild.leftChild.v,5
	}
	
	private static void show(BinarySortTree t){
		print(t.getRoot(),0)
	}
	
	private static void print(BinaryTreeNode root,int depth){
		if(root != null){
			print(root.leftChild,depth+1);
			printPrefix(depth);
			System.out.println(root.v);
			print(root.rightChild,depth+1);
		}
	}
	
	static final String PREFIX = "    ";
	private static void printPrefix(int times){
		while(times-->0){
			if(times == 0)
				System.out.print("+---");
			else
				System.out.print(PREFIX);
		}
	}
}

参考:

【1】AVL树和JAVA实现

【2】二叉平衡树，AVL树和JAVA的实现

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-190215-1.html