package avlbinarytree;
import java.util.Stack;
public class AVLSortTree<T extends Comparable<T>> {
private AVLNode<T> root;
public AVLSortTree() {
}
public AVLSortTree(AVLNode<T> root) {
this.root = root;
}
public AVLNode<T> getRoot() {
return root;
}
//左旋转
private void leftRotate(AVLNode<T> node){
if(node!=null){
AVLNode<T> rnode=node.getRightchild();
node.setRightchild(rnode.getLchild());
if(rnode.getLchild()!=null){
rnode.getLchild().setParent(node);
}
rnode.setParent(node.getParent());
if(node.getParent()==null){
this.root=rnode;
}else if(node.getParent().getLchild().equals(node)){
node.getParent().setLchild(rnode);
}else{
node.getParent().setRightchild(rnode);
}
rnode.setLchild(node);
node.setParent(rnode);
}
}
//右旋转
private void rightrotate(AVLNode<T> node){
if(node!=null){
AVLNode<T> lnode=node.getLchild();
node.setLchild(lnode.getRightchild());
if(lnode.getRightchild()!=null){
lnode.getRightchild().setParent(node);
}
lnode.setParent(node.getParent());
if(node.getParent()==null){
this.root=lnode;
}else if(node.getParent().getLchild()==node){
node.getParent().setLchild(lnode);
}else{
node.getParent().setRightchild(lnode);
}
lnode.setRightchild(node);
node.setParent(lnode);
}
}
public boolean leftbalance(AVLNode<T> node){
boolean highlower=true;
AVLNode<T> lnode=node.getLchild();
switch(lnode.getBf()){
case LH:
node.setBf(EH);
lnode.setBf(EH);
this.rightrotate(node);
break;
case RH:
AVLNode<T> rd=lnode.getRightchild();
switch(rd.getBf()){
case EH:
node.setBf(EH);
lnode.setBf(EH);
break;
case LH:
lnode.setBf(EH);
node.setBf(RH);
break;
case RH:
node.setBf(EH);
lnode.setBf(LH);
break;
}
rd.setBf(EH);
this.leftRotate(lnode);
this.rightrotate(node);
break;
case EH:
lnode.setBf(RH);
node.setBf(LH);
highlower=false;
this.rightrotate(node);
break;
}
return highlower;
}
public boolean rightbalance(AVLNode<T> node){
boolean heightlower=false;
AVLNode<T> rnode=node.getRightchild();
switch(rnode.getBf()){
case RH:
rnode.setBf(EH);
node.setBf(EH);
this.leftRotate(node);
break;
case LH:
AVLNode<T> ld=rnode.getLchild();
switch(ld.getBf()){
case EH:
node.setBf(EH);
rnode.setBf(EH);
break;
case LH:
node.setBf(EH);
rnode.setBf(RH);
break;
case RH:
node.setBf(LH);
rnode.setBf(EH);
break;
}
ld.setBf(EH);
this.rightrotate(rnode);
this.leftRotate(node);
break;
case EH:
node.setBf(RH);
rnode.setBf(LH);
heightlower=false;
this.leftRotate(node);
break;
}
return heightlower;
}
private void AfterFixInsertion(AVLNode<T> node){
if(node.getBf()==2){
leftbalance(node);
}
if(node.getBf()==-2){
rightbalance(node);
}
}
public void addAVLNode(T data){
addAVLNode(root,new AVLNode(data,null));
}
private AVLNode<T> addAVLNode(AVLNode<T> root,AVLNode<T> element){
AVLNode<T> node=root;
AVLNode<T> parent=null;
while(node!=null){
parent=node;
if(element.getData().compareTo(node.getData())<0){
node=node.getLchild();
}else{
node=node.getRightchild();
}
}
element.setParent(parent);
if(parent==null){
this.root=element;
}else if(element.getData().compareTo(parent.getData())<0){
parent.setLchild(element);
}else{
parent.setRightchild(element);
}
while(parent!=null){
if(element.getData().compareTo(parent.getData())<0){
parent.bf++;
}else{
parent.bf--;
}
if(parent.getBf()==0)break;
if(Math.abs(parent.getBf())==2){
AfterFixInsertion(parent);
break;
}
parent=parent.getParent();
}
return root;
}
public void preNode(){
PreNode(root);
}
private void PreNode(AVLNode<T> root){
if(root!=null){
System.out.print(root.getData()+" ");
PreNode(root.getLchild());
PreNode(root.getRightchild());
}
}
public void nrInOrderTraverse(){
nrInOrderTraverse(root);
}
private void nrInOrderTraverse(AVLNode<T> root){
Stack<AVLNode<T>> stack=new Stack<AVLNode<T>>();
AVLNode<T> node=root;
while(node!=null || !stack.isEmpty()){
while(node!=null){
System.out.print(node.getData()+" ");
stack.push(node);
node=node.getLchild();
}
node=stack.pop();
node=node.getRightchild();
}
}
//将u的树替换成v的树
private void transplant(AVLNode<T> u,AVLNode<T> v){
if(u.getParent()==null){
this.root=v;
}else if(u.equals(u.getParent().getLchild())){
u.getParent().setLchild(v);
}else{
u.getParent().setRightchild(v);
}
if(v!=null){
v.setParent(u.getParent());
}
}
public T getMinmum(){
return this.getMinmum(root).getData();
}
//找到当前最小的节点
private AVLNode<T> getMinmum(AVLNode<T> root){
AVLNode<T> node=root;
while(node.getLchild()!=null){
node=node.getLchild();
}
return node;
}
public T getMaxmum(){
return this.getMaxmum(root).getData();
}
//找到当前最小的节点
private AVLNode<T> getMaxmum(AVLNode<T> root){
AVLNode<T> node=root;
while(node.getRightchild()!=null){
node=node.getRightchild();
}
return node;
}
public T getSuccessorData(T data){
AVLNode<T> node=this.getSuccessor(root,data);
if(node!=null){
return node.getData();
}else{
return null;
}
}
//获得某个节点的后继
private AVLNode<T> getSuccessor(AVLNode<T> root,T data){
AVLNode<T> element=this.getAVLNode(root, data);//得到当前的节点
if(element==null)return null;
if(element.getRightchild()!=null){
return getMinmum(element.getRightchild());
}
AVLNode<T> parent=element.getParent();
while(parent!=null && parent.getRightchild().equals(element)){
element=parent;
parent=parent.getParent();
}
return parent;
}
private void deleteAVLNode(AVLNode<T> root,T data){
AVLNode<T> p=null;
AVLNode<T> current=this.getAVLNode(root, data);//得到当前的节点
if(current==null)return ;
AVLNode<T> parent=current.getParent();//得到当前节点的父节点
p=current;
if(current.getLchild()==null){
this.transplant(current,current.getRightchild());
}else if(current.getRightchild()==null){
this.transplant(current, current.getLchild());
}else{
AVLNode<T> y=this.getSuccessor(root,data);
if(!current.equals(y.getParent())){
this.transplant(y, y.getRightchild());
y.setRightchild(current.getRightchild());
y.getRightchild().setParent(y);
}
System.out.println(current.getParent());
this.transplant(current, y);
y.setLchild(current.getLchild());
y.getLchild().setParent(y);
}
boolean h=true;
while(parent!=null&&h){
if(p.equals(parent.getLchild())){
parent.bf--;
}else{
parent.bf++;
}
if(Math.abs(parent.getBf())==1)break;
AVLNode<T> r=parent;
if(parent.getBf()==2){
h=this.leftbalance(r);
}else{
h=this.rightbalance(r);
}
p=parent;
parent=parent.getParent();
}
current.setParent(null);
current.setLchild(null);
current.setRightchild(null);
current=null;
}
public boolean deleteAVLNode(T data){
deleteAVLNode(root,data);
if(this.root!=null){
return true;
}else{
return false;
}
}
private AVLNode<T> getAVLNode(AVLNode<T> root,T data){
AVLNode<T> node=root;
while(node!=null&&!node.getData().equals(data)){
if(data.compareTo(node.getData())<0){
node=node.getLchild();
}else{
node=node.getRightchild();
}
}
if(node!=null){
return node;
}else{
return null;
}
}
private static final int LH=1;
private static final int EH=0;
private static final int RH=-1;
static class AVLNode<T extends Comparable<T>> implements Comparable<AVLNode<T>>{
private T data;
private AVLNode<T> parent,lchild,rightchild;
private int bf;
public AVLNode(){}
public AVLNode(T data,AVLNode<T> parent){
this(data,parent,null,null,0);
}
public AVLNode(T data, AVLNode<T> parent, AVLNode<T> lchild,
AVLNode<T> rightchild, int bf) {
this.data = data;
this.parent = parent;
this.lchild = lchild;
this.rightchild = rightchild;
this.bf = bf;
}
@Override
public int hashCode() {
return data.hashCode();
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
AVLNode other = (AVLNode) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
return true;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public AVLNode<T> getParent() {
return parent;
}
public void setParent(AVLNode<T> parent) {
this.parent = parent;
}
public AVLNode<T> getLchild() {
return lchild;
}
public void setLchild(AVLNode<T> lchild) {
this.lchild = lchild;
}
public AVLNode<T> getRightchild() {
return rightchild;
}
public void setRightchild(AVLNode<T> rightchild) {
this.rightchild = rightchild;
}
public int getBf() {
return bf;
}
public void setBf(int bf) {
this.bf = bf;
}
@Override
public int compareTo(AVLNode<T> o) {
return this.data.compareTo(o.getData());
}
}
public static void main(String[] args) {
AVLSortTree<Integer> a=new AVLSortTree<Integer>();
a.addAVLNode(1);
a.addAVLNode(2);
a.addAVLNode(3);
a.addAVLNode(4);
a.addAVLNode(5);
a.addAVLNode(6);
a.preNode();
System.out.println();
a.nrInOrderTraverse();
//
System.out.println(a.deleteAVLNode(6));
System.out.println();
//
a.preNode();
System.out.println(a.getMinmum());
System.out.println(a.getMaxmum());
System.out.println(a.getSuccessorData(5));
a.deleteAVLNode(4);
a.preNode();
}
}