package com.tomsnail.data.tree;
/**
* AVL二叉平衡树
* @author tomsnail
* @date 2015年3月30日 下午4:35:50
*/
public class AVLTree {
/**
* 根节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:54
*/
private AVLNode rootNode;
private String bulidType = "";
/**
* 增加一个节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:08
*/
public void add(int value){
AVLNode subNode = null;
if(rootNode==null){
subNode = new AVLNode(value);
rootNode = subNode;
}else{
subNode = addNode(rootNode,value);
}
reBuild(subNode);
}
private AVLNode addNode(AVLNode node,int value){
AVLNode subNode = null;
if(node.getValue()>value){
if(node.getLeftNode()==null){
subNode = new AVLNode(value);
node.setLeftNode(subNode);
}else{
subNode = addNode(node.getLeftNode(), value);
}
}
if(node.getValue()<value){
if(node.getRightNode()==null){
subNode = new AVLNode(value);
node.setRightNode(subNode);
}else{
subNode = addNode(node.getRightNode(),value);
}
}
return subNode;
}
/**
* 重平衡树
* @author tomsnail
* @date 2015年3月30日 下午5:42:00
*/
private void reBuild(AVLNode node){
if(node!=null){
AVLNode tempRootNode = findTempRootNode(node);
if(tempRootNode!=null){
if(bulidType.equals("ll")){
Lrotate(node,tempRootNode);
}else if(bulidType.equals("rr")){
Rrotate(node,tempRootNode);
}else if(bulidType.equals("lr")){
Rrotate(node,tempRootNode.getLeftNode());
Lrotate(node,tempRootNode);
}else if(bulidType.equals("rl")){
Lrotate(node,tempRootNode.getRightNode());
Rrotate(node,tempRootNode);
}
reBuild(tempRootNode);
}
}
}
/**
* 右旋
* @author tomsnail
* @date 2015年3月30日 下午9:23:28
*/
private void Rrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getRightNode();//旋转节点
AVLNode rootNode = tempRootNode.getRootNode();//主根节点
String type = "";
if(rootNode!=null){
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getLeftNode();//调整节点
rotateNode.setLeftNode(tempRootNode);
tempRootNode.setRightNode(null);
if(adjustNode!=null){
tempRootNode.setRightNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}else if(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
* 左旋
* @author tomsnail
* @date 2015年3月30日 下午9:23:28
*/
private void Lrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getLeftNode();//旋转节点
AVLNode rootNode = tempRootNode.getRootNode();//主根节点
String type = "";
if(rootNode!=null){//子树类型
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getRightNode();//调整节点
rotateNode.setRightNode(tempRootNode);
tempRootNode.setLeftNode(null);
if(adjustNode!=null){
tempRootNode.setLeftNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}else if(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
* 查找最小不平衡的根节点
* @author tomsnail
* @date 2015年3月30日 下午5:40:55
*/
private AVLNode findTempRootNode(AVLNode node){
AVLNode noB = getNoBalance(node);
if(noB==null){
return null;
}
if(isTypeLL(noB)){
bulidType = "ll";
}else if(isTypeRR(noB)){
bulidType = "rr";
}else if(isTypeLR(noB)){
bulidType = "lr";
}else if(isTypeRL(noB)){
bulidType = "rl";
}
return noB;
}
//左左类型
private boolean isTypeLL(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){
return true;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//右右类型
private boolean isTypeRR(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){
return true;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//左右类型
private boolean isTypeLR(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){
return true;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//右左类型
private boolean isTypeRL(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){
return true;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//获取不平衡的根节点
private AVLNode getNoBalance(AVLNode node){
if(node.getRootNode()==null){
return null;
}else{
if(!isBalance(node.getRootNode())){
return node.getRootNode();
}else{
return getNoBalance(node.getRootNode());
}
}
}
/**
* 删除一个节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:20
*/
public void delete(int value){
AVLNode wantDeleteNode = find(value);
if(wantDeleteNode==null){
return;
}else{
if(wantDeleteNode.getLeftNode()==null&&wantDeleteNode.getRightNode()==null){//删除节点没有左右子树
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getLeftNode()==wantDeleteNode){
rootNode.setLeftNode(null);
}else{
rootNode.setRightNode(null);
}
reBuild(rootNode);
}
}else if(wantDeleteNode.getRightNode()==null){//删除节点只有左子树
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getLeftNode()==wantDeleteNode){
rootNode.setLeftNode(wantDeleteNode.getLeftNode());
}else{
rootNode.setRightNode(wantDeleteNode.getLeftNode());
}
wantDeleteNode.setLeftNode(null);
reBuild(rootNode);
}
}else if(wantDeleteNode.getLeftNode()==null){//删除节点只有右子树
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getRightNode()==wantDeleteNode){
rootNode.setLeftNode(wantDeleteNode.getRightNode());
}else{
rootNode.setRightNode(wantDeleteNode.getRightNode());
}
wantDeleteNode.setRightNode(null);
reBuild(rootNode);
}
}else {//删除节点有左右子树
AVLNode maxNode = getLeftMaxValueNode(wantDeleteNode.getLeftNode());//找到节点左子树最大值的节点
AVLNode rootMaxNode = maxNode.getRootNode();//获得该节点的父节点
if(maxNode.getLeftNode()!=null){//如果最大值节点有左子树，则将最大值节点的父节点的右子树设为它
rootMaxNode.setRightNode(maxNode.getLeftNode());
maxNode.setLeftNode(null);
}else{//否则置空
rootMaxNode.setRightNode(null);
}
wantDeleteNode.setValue(maxNode.getValue());//把要删除节点的值用最大值节点的值替换
maxNode=null;//引用置空
reBuild(rootMaxNode);
}
}
}
//得到左子树最大值节点
private AVLNode getLeftMaxValueNode(AVLNode node){
if(node!=null&&node.getRightNode()!=null){
return getLeftMaxValueNode(node.getRightNode());
}else{
return node;
}
}
/**
* 查找一个节点
* @author tomsnail
* @date 2015年3月30日 下午4:36:35
*/
public AVLNode find(int value){
return findWith2(rootNode,value);
}
private AVLNode findWith2(AVLNode node,int value){
if(node==null){
return null;
}
System.out.println(node.getValue());
if(node.getValue()>value){
return findWith2(node.getLeftNode(),value);
}else if(node.getValue()<value){
return findWith2(node.getRightNode(),value);
}else{
return node;
}
}
/**
* 中序遍历
* @author tomsnail
* @date 2015年3月31日 下午6:23:05
*/
public void midScan(AVLNode node){
if(node==null){
return;
}
midScan(node.getLeftNode());
System.out.println(node.getValue());
midScan(node.getRightNode());
}
public AVLNode getRootNode() {
return rootNode;
}
public static void main(String[] args) {
int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80
AVLTree tree = new AVLTree();
for(int i=0;i<is.length;i++){
tree.add(is[i]);
}
System.out.println(tree.getRootNode().getValue());
System.out.println("----------------------------");
tree.midScan(tree.getRootNode());
tree.delete(4);
System.out.println(isBalance(tree.getRootNode()));
System.out.println();
//tree.find(40);
}
public static int depth(AVLNode node){
if(node==null){
return 0;
}else{
int ld = depth(node.getLeftNode());
int rd = depth(node.getRightNode());
return 1 + (ld >rd ? ld : rd);
}
}
public static boolean isBalance(AVLNode node){
if (node==null)
return true;
int dis = depth(node.getLeftNode()) - depth(node.getRightNode());
if (dis>1 || dis<-1 )
return false;
else
return isBalance(node.getLeftNode()) && isBalance(node.getRightNode());
}
}
class AVLNode{
private int value;
private AVLNode leftNode;
private AVLNode rightNode;
private AVLNode rootNode;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public AVLNode getLeftNode() {
return leftNode;
}
public void setLeftNode(AVLNode leftNode) {
this.leftNode = leftNode;
if(leftNode!=null){
leftNode.setRootNode(this);
}
}
public AVLNode getRightNode() {
return rightNode;
}
public void setRightNode(AVLNode rightNode) {
this.rightNode = rightNode;
if(rightNode!=null){
rightNode.setRootNode(this);
}
}
public AVLNode getRootNode() {
return rootNode;
}
public void setRootNode(AVLNode rootNode) {
this.rootNode = rootNode;
}
public boolean hasSubNode(){
if(this.leftNode!=null||this.rightNode!=null){
return true;
}else{
return false;
}
}
public AVLNode(){
}
public AVLNode(int value){
this.value = value;
}
}