devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡二叉树(AVL)【java实现+图解】_java 二叉平衡树

作者：黑客灵魂 | 2024-07-20 19:49:22

赞

踩

java 二叉平衡树

目录

一、平衡二叉树(AVL)

二、平衡二叉树的四种旋转

1.右旋转

2.左旋转

3. 左右旋转

4. 右左旋转

 三、基于二叉搜索树之平衡二叉树的代码实现

1.具体方法思路

2.java代码实现 

一、平衡二叉树(AVL)

一种自平衡二叉搜索树，它是在每个节点上增加一个平衡因子，然后通过调整树中节点的高度来保持树的平衡。平衡因子是左子树的高度减去右子树的高度，用它可以表示出当前节点的平衡程度。对于任意一个结点，左子树和右子树的高度差不能超过1，当一个节点的平衡因子绝对值大于1时，这个节点就被称为不平衡节点。

二、平衡二叉树的四种旋转

1.右旋转

 

  1.     //左旋转
  2.     public Node leftSpin(Node x){
  3.         Node y = x.right;
  4.         Node t2 = y.left;
  5.  
  6.         x.right = t2;
  7.         y.left = x;
  8.         //更新节点的高度
  9.         x.height = Math.max(getHight(x.left),getHight(x.right))+1;
  10.         y.height = Math.max(getHight(y.left),getHight(y.right))+1;
  11.         return y;
  12.     }

 

2.左旋转

 

  1.     //右旋转
  2.     public Node rightSpin(Node x){
  3.         Node y = x.left;
  4.         Node t2 = y.right;
  5.  
  6.         x.left = t2;
  7.         y.right = x;
  8.         //更新节点的高度
  9.         x.height = Math.max(getHight(x.left),getHight(x.right))+1;
  10.         y.height = Math.max(getHight(y.left),getHight(y.right))+1;
  11.         return y;
  12.     }

3. 左右旋转

先旋转成上面只需要右旋转的情况，再经过右旋转成平衡二叉树

4. 右左旋转

先旋转成上面只需要左旋转的情况，再经过左旋转成平衡二叉树

 三、基于二叉搜索树之平衡二叉树的代码实现

1.具体方法思路

主要方法：

添加：每次添加一个节点后更新输的高度，平衡因子可能改变，依据平衡因子对二叉树进行调整；

删除：每删除一个节点后，也需要更新输的高度，平衡因子可能改变，依据平衡因子对二叉树进行调整。

辅助方法：

判断是否是二叉搜索树：通过中序遍历，将节点的前一个值与后一个值比较；

判断是否是平衡二叉树：通过判断每个子树的平衡因子的是否在[-1，1]区间内。

2.java代码实现 

  1. import java.util.*;
  2. import java.util.stream.Collectors;
  3.  
  4. public class AVL<T extends Comparable<T>> {
  5.  
  6.     public class Node {
  7.         T val;
  8.         Node left;
  9.         Node right;
  10.         //以该节点为根的树的高度
  11.         int height;
  12.  
  13.         //统计单词出现的次数
  14.         int count;
  15.  
  16.         public Node(T val) {
  17.             this.val = val;
  18.             this.height = 1;//默认高度为1
  19.             this.count = 1;
  20.         }
  21.  
  22.         @Override
  23.         public String toString() {
  24.             return String.format("val:%s,heiget:%d,count:%d",this.val,this.height,this.count);
  25.         }
  26.     }
  27.  
  28.     private Node root;
  29.     private Integer size;
  30.  
  31.     public AVL() {
  32.         this.root = null;
  33.         this.size = 0;
  34.     }
  35.  
  36.     public boolean isEmpt() {
  37.         return this.size == 0;
  38.     }
  39.  
  40.     public Integer getSize() {
  41.         return this.size;
  42.     }
  43.  
  44.  
  45.     //验证是否是二叉搜索树
  46.     public  boolean isBinaryTree(){
  47.         List<T> list = new ArrayList<>();
  48.         midTraversal(list,this.root);
  49.         for (int i = 1; i < list.size(); i++) {
  50.             if (list.get(i-1).compareTo(list.get(i))>0){
  51.                 return false;
  52.             }
  53.         }
  54.         return true;
  55.     }
  56.  
  57.     //获取当前节点的高度
  58.     public int getHight(Node node){
  59.         if (node==null){
  60.             return 0;
  61.         }
  62.         return node.height;
  63.     }
  64.     //获取当前节点的平衡因子
  65.     public int getBalanceFactor(Node node){
  66.         if (node==null){
  67.             return 0;
  68.         }
  69.         return getHight(node.left)-getHight(node.right);
  70.     }
  71.     
  72.  
  73.     public boolean isBalanceTree(){
  74.         return isBalanceTree(this.root);
  75.     }
  76.  
  77.     //判断以node为节点的树是否是平衡二叉树
  78.     private boolean  isBalanceTree(Node node){
  79.         if (node==null){
  80.             return true;
  81.         }
  82.         int balanceFactor = Math.abs(getBalanceFactor(node));
  83.  
  84.         if (balanceFactor>1){
  85.             return false;
  86.         }else {
  87.             return isBalanceTree(node.left)&&isBalanceTree(node.right);
  88.         }
  89.     }
  90.     
  91.     //左旋转
  92.     public Node leftSpin(Node x){
  93.         Node y = x.right;
  94.         Node t2 = y.left;
  95.  
  96.         x.right = t2;
  97.         y.left = x;
  98.         //更新节点的高度
  99.         x.height = Math.max(getHight(x.left),getHight(x.right))+1;
  100.         y.height = Math.max(getHight(y.left),getHight(y.right))+1;
  101.         return y;
  102.     }
  103.     //右旋转
  104.     public Node rightSpin(Node x){
  105.         Node y = x.left;
  106.         Node t2 = y.right;
  107.  
  108.         x.left = t2;
  109.         y.right = x;
  110.         //更新节点的高度
  111.         x.height = Math.max(getHight(x.left),getHight(x.right))+1;
  112.         y.height = Math.max(getHight(y.left),getHight(y.right))+1;
  113.         return y;
  114.     }
  115.  
  116.     //添加
  117.     public void add(T val) {
  118.         this.root = add(this.root, val);
  119.     }
  120.  
  121.     private Node add(Node node, T val) {
  122.         if (node == null) {
  123.             this.size++;
  124.             Node leafNode = new Node(val);
  125.             return leafNode;
  126.         }
  127.         //当前节点的值小于添加的val,因此val做右孩子
  128.         if (node.val.compareTo(val) < 0) {
  129.             node.right = add(node.right, val);
  130.             //更新高度
  131.             node.height = Math.max(getHight(node.left),getHight(node.right))+1;
  132.         } else if (node.val.compareTo(val) > 0){
  133.             node.left = add(node.left, val);
  134.             //更新高度
  135.             node.height = Math.max(getHight(node.left),getHight(node.right))+1;
  136.         }else {
  137.             node.count++;
  138.         }
  139.  
  140.         //添加后还要判断是否是平衡二叉树
  141.         Node resNode = node;
  142.         int balanceFactor = getBalanceFactor(node);
  143.         if (balanceFactor>1&&getBalanceFactor(node.left)>=0){
  144.             //右
  145.             resNode = rightSpin(node);
  146.         }else if (balanceFactor>1&&getBalanceFactor(node.left)<0){
  147.             //左右
  148.             node.left = leftSpin(node.left);
  149.             resNode = rightSpin(node);
  150.         }else if (balanceFactor<-1&&getBalanceFactor(node.right)<=0){
  151.             //左
  152.             resNode = leftSpin(node);
  153.         }else if (balanceFactor<-1&&getBalanceFactor(node.right)>0){
  154.             //右左
  155.             node.right = rightSpin(node.right);
  156.             resNode = leftSpin(node);
  157.         }
  158.         return resNode;
  159.     }
  160.  
  161.  
  162.     //删除操作
  163.     //删除树中的val
  164.     public void remove(T val){
  165.         if (!contain(val)){
  166.             return;
  167.         }
  168.         this.root = remove(this.root,val);
  169.     }
  170.  
  171.     /**
  172.      * 删除val
  173.      * @param node
  174.      * @param val
  175.      * @return
  176.      */
  177.     public Node remove(Node node, T val){
  178.         //    递归终止条件
  179.         if (node == null) {
  180.             return null;
  181.         }
  182.         Node resNode = null;
  183.         if (node.val.compareTo(val) == 0) {
  184.             this.size--;
  185.             if (node.right==null){
  186.                 //右子树为空
  187.                 resNode = node.left;
  188.             }else if (node.left==null){
  189.                 //左子树为空
  190.                 resNode = node.right;
  191.             }else {
  192.                 //    左右子树都不为空
  193.                 //    1.找到删除节点的后继
  194.                  Node suffixNode = getMinDG(node.right);
  195.                 // 2.删除后继
  196.                 suffixNode.right = remove(node.right,getMinDG(node.right).val);
  197.                 // 3.连接
  198.                 suffixNode.left = node.left;
  199.                 this.size++;
  200.                 //    返回删除后的根
  201.                 resNode = suffixNode;
  202.             }
  203.         }else if (node.val.compareTo(val)<0){
  204.             node.right = remove(node.right,val);
  205.             resNode = node;
  206.         }else {
  207.             node.left = remove(node.left,val);
  208.             resNode =  node;
  209.         }
  210.  
  211.         //删除节点可能为叶子结点
  212.         if (resNode==null){
  213.             return null;
  214.         }
  215.         //更新高度
  216.         resNode.height = Math.max(getHight(resNode.left),getHight(resNode.right))+1;
  217.         int balanceFactor = getBalanceFactor(resNode);
  218.         if (balanceFactor>1&&getBalanceFactor(resNode.left)>=0){
  219.             //右
  220.             resNode = rightSpin(resNode);
  221.         }else if (balanceFactor>1&&getBalanceFactor(resNode.left)<0){
  222.             //左右
  223.             resNode.left = leftSpin(resNode.left);
  224.             resNode = rightSpin(resNode);
  225.         }else if (balanceFactor<-1&&getBalanceFactor(resNode.right)<=0){
  226.             //左
  227.             resNode = leftSpin(resNode);
  228.         }else if (balanceFactor<-1&&getBalanceFactor(resNode.right)>0){
  229.             //右左
  230.             resNode.right = rightSpin(resNode.right);
  231.             resNode = leftSpin(resNode);
  232.         }
  233.         return resNode;
  234.     }
  235.  
  236.     private Node getMinDG(Node node) {
  237.         // 递归终止条件
  238.         if (node.left == null) {
  239.             return node;
  240.         }
  241.         //   递归操作
  242.         return getMinDG(node.left);
  243.     }
  244.  
  245.     public String midTraversal() {
  246.         List<T> res = new ArrayList<>();
  247.         midTraversal(res, this.root);
  248.         return res.stream().map(item -> item.toString()).collect(Collectors.joining(","));
  249.     }
  250.  
  251.     /**
  252.      * 中序遍历
  253.      *
  254.      * @param result
  255.      * @param node   当前节点
  256.      * @return
  257.      */
  258.     private void midTraversal(List<T> result, Node node) {
  259.         if (node == null) {
  260.             return;
  261.         }
  262.         midTraversal(result, node.left);
  263.         result.add(node.val);
  264.         midTraversal(result, node.right);
  265.     }
  266.  
  267.     public void showTree(){
  268.         showTree(this.root);
  269.     }
  270.     private void showTree(Node node){
  271.         if (node == null) {
  272.             return;
  273.         }
  274.         showTree(node.left);
  275.         System.out.print(node);
  276.         System.out.println("BalanceFactor:"+getBalanceFactor(node));
  277.         showTree(node.right);
  278.     }
  279.  
  280.     //查询是否存在val
  281.     public boolean contain(T val){
  282.         return contain(this.root,val);
  283.     }
  284.     private boolean contain(Node node,T val){
  285.     //    递归的终止条件
  286.     //    查询到低也没有找到
  287.         if (node==null){
  288.             return false;
  289.         }
  290.     //    递归操作
  291.         if (node.val.compareTo(val)==0){
  292.             return true;
  293.         }else if (node.val.compareTo(val)<0){
  294.             return contain(node.right,val);
  295.         }else {
  296.             return  contain(node.left,val);
  297.         }
  298.     }
  299.     //测试
  300.     public static void main(String[] args) {
  301.         AVL<String> bst = new AVL<>();
  302.  
  303.         List<String> list = ReadBookUtil.readBook("pride-and-prejudice.txt");
  304.         list.stream().forEach(item->{
  305.             bst.add(item);
  306.         });
  307.         System.out.println("是否是二分搜索树"+bst.isBinaryTree());
  308.         System.out.println("是否是平衡二叉树"+bst.isBalanceTree());
  309.         bst.showTree();
  310.   
  311.     }
  312. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/858157
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号