平衡二叉树(AVL树)

首页 » 算法 » 平衡二叉树(AVL树)

二叉树结构可以很好的解决插入和查询的问题,但是也有一些特殊的树并不是这样,然而更像单链表

平衡二叉树(AVL树)
左子树全部为空(单链表)

上边的问题可以用平衡二叉树来解决

平衡二叉树也叫平衡二叉搜索树(AVL树)

特点:他的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一个平衡二叉树

平衡二叉树的转换是通过左旋转、右旋转和双旋转来完成的

一、左旋转

平衡二叉树(AVL树)
平衡前,数列4、3、6、5、7、8
平衡二叉树(AVL树)
平衡后
左旋转的方法
1、创建一个新的节点newnode(以4这个值创建),值等于当前根节点的值
2、把新节点的左子树设置了当前节点的左子树 newnode.left = left
3、把新节点的右子树设置为当前节点的右子树的左子树 newnode.right=right.left
4、把当前节点的值换为右子节点的值 value=right.value
5、把当前节点的右子树设置成右子树的右子树 right=right.right
6、把当前节点的左子树设置为新节点 left=newleft;

二、右旋转

平衡二叉树(AVL树)
平衡前,数列 10、12、8、9、7、6
平衡二叉树(AVL树)
平衡后
右旋转的方法
1、创建一个新的节点newNode(以10这个值创建),值等于当前根节点的值
2、把新节点的右子树设置成当前节点的右子树 newnode.right=right
3、把新节点的左子树设置为当前节点的左子树的右子树 newnode.left=left.right
4、把当前节点的值替换为左子节点的值 value=left.value
5、把当前节点对的左子树设置成左子树的左子树 left=left.left
6、把当前节点的右子树设置为新节点 right=newleft

三、双旋转

但是仅仅一个旋转是不行的,因为可能会遇到这种情况

平衡二叉树(AVL树)
右旋转前,数列 10、11、7、6、8、9
平衡二叉树(AVL树)
右旋转后,发现还不是平衡二叉树

这时候就要用双旋装来解决了

当符合右旋转的条件时
1、如果他的左子树的右子树高度大于他的左子树的高度
2、先对当前这个节点的左子节点进行左旋转
3、再对当前节点进行右旋转操作

代码实现

package tree;

public class avltree {
public static void main(String[] args) {
 int [] arr2= {10,11,7,6,8,9};
 avl at2=new avl();
 for(int i=0;i<arr2.length;i++) {
  at2.add(new Node(arr2[i]));
 }
 at2.show();
 System.out.println("树的高度:"+at2.getRoot().height());
 System.out.println("左子树的高度:"+at2.getRoot().leftheight());
 System.out.println("右子树的高度:"+at2.getRoot().rightheight());
 System.out.println("根节点:"+at2.getRoot());
}
}
//创建avltree
class avl{
 private Node root;
 public void add(Node node) {
  if(root==null) {
   root=node;
  }else {
   root.add(node);
  }
 }
 public Node getRoot() {
  return root;
 }
 public void show() {
  if(root != null) {
   root.show();
  }else {
   System.out.println("空");
  }
 }

 public Node findParent(int value) {
  if(root==null)
   return null;
  else {
   return root.findParent(value);
  }
 }
 }


//节点
class Node{
 int value;
 Node left;
 Node right;
 public Node(int value) {
  this.value=value;
 }
 
 
 public Node findParent(int value) {
    if((this.left != null && this.left.value==value) 
      || this.right!=null && this.right.value==value) {
     return this;
    }else {
     if(value<this.value && this.left!=null){
      return this.left.findParent(value);
     }else if(value >= this.value && this.right!=null) {
      return this.right.findParent(value);
     }else {
      return null;
     }
    }}


 /*
  * 要先知道树的高度
  */
 //返回左子树的高度
 public int leftheight() {
  if(left == null)
   return 0;
  return left.height();
 }
 //返回右子树的高度
 public int rightheight() {
  if(right == null)
   return 0;
  return right.height();
 }
 //返回当前节点的高度,以该节点为根节点的树的高度
 public int height() {
  return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height())+1;
 }
 
 
/*
左旋转的方法
1、创建一个新的节点newnode(以4这个值创建),值等于当前根节点的值
2、把新节点的左子树设置了当前节点的左子树 newnode.left = left
3、把新节点的右子树设置为当前节点的右子树的左子树 newnode.right=right.left
4、把当前节点的值换为右子节点的值 value=right.value
5、把当前节点的右子树设置成右子树的右子树 right=right.right
6、把当前节点的左子树设置为新节点 left=newleft;

*/
 private void leftgo() {
  //创建一个新的节点newnode(以4这个值创建),值等于当前根节点的值
  Node newNode = new Node(value);
  //把新节点的左子树设置了当前节点的左子树 newnode.left = left
  newNode.left=left;
  //把新节点的右子树设置为当前节点的右子树的左子树 newnode.right=right.left
  newNode.right=right.left;
  //把当前节点的值换为右子节点的值 value=right.value
  value=right.value;
  //把当前节点的右子树设置成右子树的右子树 right=right.right
  right=right.right;
  //把当前节点的左子树设置为新节点 left=newleft;
  left=newNode;
 }
 
/*
右旋转的方法
1、创建一个新的节点newNode(以10这个值创建),值等于当前根节点的值
2、把新节点的右子树设置成当前节点的右子树 newnode.right=right
3、把新节点的左子树设置为当前节点的左子树的右子树 newnode.left=left.right
4、把当前节点的值替换为左子节点的值 value=left.value
5、把当前节点对的左子树设置成左子树的左子树 left=left.left
6、把当前节点的右子树设置为新节点 right=newleft
 
*/
 
 private void rightgo() {
  Node newnode=new Node(value);
  newnode.right=right;
  newnode.left=left.right;
  value=left.value;
  left=left.left;
  right=newnode;
 }
 
 @Override
 public String toString() {
  return "Node [value=" + value + "]";
 }

 public void add(Node node) {
  if(node==null){
   return;
  }else {
   if(node.value<this.value) {
    if(this.left==null) {
     this.left=node;
    }else {
     this.left.add(node);
    }
   }else {
    if(this.right==null) {
     this.right=node;
    }else {
     this.right.add(node);
    }
   }
  }
  
  /*
   * 当添加完一个节点后,如果(右子树的高度-左子树的高度)>1 ,左旋转
   */
  if(rightheight()-leftheight()>1) {
   //如果他的右子树的左子树高度大于他的右子树的高度
   if(right != null && right.leftheight() > right.rightheight()) {
    //先进行右旋转
    right.rightgo();
    //然后在对当前节点进行左旋转
    leftgo();
   }
   else
    leftgo();
   return;//必须有
  }
  /*
   * 当添加完一个节点后,如果(左子树的高度-右子树的高度)>1 ,右旋转
   */
  
  else if(leftheight()-rightheight()>1) {
   /*
    当符合右旋转的条件时
    1、如果他的左子树的右子树高度大于他的左子树的高度
    2、先对当前这个节点的左子节点进行左旋转
    3、再对当前节点进行右旋转操作
    */
   if(left != null && left.rightheight() > left.leftheight()){
    //先对当前节点的左节点进行左旋转
    left.leftgo();
    //再对当前节点进行右旋转
    rightgo();
   }else
    rightgo();
  }
 }
 //中序遍历
 public void show() {
  if(this.left != null) {
   this.left.show();
  }
  System.out.println(this);
  if(this.right != null) {
   this.right.show();
  }
  
 }
}

 

分享到:
赞(0) 打赏

评论 6

评论前必须登录!

 

  1. #1

    以后多多交流

    我是你哥6个月前 (04-03)
  2. #2

    最好再详细点

    努力6个月前 (04-03)
  3. #3

    以后多多交流

    白云6个月前 (04-03)
  4. #4

    你好4个月前 (05-26)
  5. #5

    我加你了哦

    渣渣辉4个月前 (05-26)
  6. #6

    可以

    中国加油小子4个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00