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();
}
}
相关文章
- 使用java登录远程LINUX并对服务实现各种操作
- 二叉树各种操作的总结
- 实现二叉树各种基本操作的算法
- Java8 使用stream实现各种list操作
- 使用java实现ffmpeg的各种操作
- 平衡二叉树的java实现
- 数据结构中很常见的各种树（BST二叉搜索树、AVL平衡二叉树、RBT红黑树、B-树、B+树、B*树）
- Ubuntu 14.04 LTS 版本(仅对32位操作系统，i686)下，安装 Java SE Development Kit 8u152（JDK 1.8.0_152）
- 【Win10操作】完美卸载Java旧版本，安装Java13
- Java 数据结构-特点： 代表一个队列，通常按照先进先出（FIFO）的顺序操作元素。 实现类： LinkedList, PriorityQueue, ArrayDeque。 堆（Heap） 堆（Heap）优先队列的基础，可以实现最大堆和最小堆。 PriorityQueue<Integer minHeap = new PriorityQueue<>; PriorityQueue<Integer maxHeap = new PriorityQueue<>(Collections.reverseOrder); 树（Trees） Java 提供了 TreeNode 类型，可以用于构建二叉树等数据结构。 class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 图（Graphs） 图的表示通常需要自定义数据结构或使用图库，Java 没有内建的图类。 以上介绍的只是 Java 中一些常见的数据结构，实际上还有很多其他的数据结构和算法可以根据具体问题选择使用。 其他一些说明 以下这些类是传统遗留的，在 Java2 中引入了一种新的框架-集合框架(Collection)，我们后面再讨论。 枚举（Enumeration） 枚举（Enumeration）接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很广。 枚举（The Enumeration）接口定义了一种从数据结构中取回连续元素的方式。 例如，枚举定义了一个叫nextElement 的方法，该方法用来得到一个包含多元素的数据结构的下一个元素。 关于枚举接口的更多信息，请参见枚举（Enumeration）。 位集合（BitSet） 位集合类实现了一组可以单独设置和清除的位或标志。 该类在处理一组布尔值的时候非常有用，你只需要给每个值赋值一"位"，然后对位进行适当的设置或清除，就可以对布尔值进行操作了。 关于该类的更多信息，请参见位集合（BitSet）。 向量（Vector） 向量（Vector）类和传统数组非常相似，但是Vector的大小能根据需要动态的变化。 和数组一样，Vector对象的元素也能通过索引访问。 使用Vector类最主要的好处就是在创建对象的时候不必给对象指定大小，它的大小会根据需要动态的变化。 关于该类的更多信息，请参见向量(Vector) 栈（Stack） 栈（Stack）实现了一个后进先出（LIFO）的数据结构。 你可以把栈理解为对象的垂直分布的栈，当你添加一个新元素时，就将新元素放在其他元素的顶部。 当你从栈中取元素的时候，就从栈顶取一个元素。换句话说，最后进栈的元素最先被取出。 关于该类的更多信息，请参见栈（Stack）。 字典（Dictionary） 字典（Dictionary） 类是一个抽象类，它定义了键映射到值的数据结构。 当你想要通过特定的键而不是整数索引来访问数据的时候，这时候应该使用 Dictionary。 由于 Dictionary 类是抽象类，所以它只提供了键映射到值的数据结构，而没有提供特定的实现。 关于该类的更多信息，请参见字典（ Dictionary）。 Dictionary 类在较新的 Java 版本中已经被弃用（deprecated），推荐使用 Map 接口及其实现类，如 HashMap、TreeMap 等，来代替 Dictionary。