devbox
小桥流水78
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构和算法---平衡二叉树_java 二叉平衡树

作者：小桥流水78 | 2024-07-20 19:44:12

赞

踩

java 二叉平衡树

平衡二叉树
        给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.


上边BST 存在的问题分析:
        1左子树全部为空，从形式上看，更像一个单链表.
        2插入速度没有影响
        3查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势，因为每次还需要比较左子树，其查询速度比 单链表还慢
        4解决方案-平衡二叉树(AVL)

平衡二叉树基本介绍:
        1.平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
        2.具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

单旋转(左旋转)
        根据{4,3,6,5,7,8}创建出对应的平衡二叉树
        对节点A进行左旋转的步骤
                ①将A 节点的 右节点 的 左节点 ，指向 A节点
                ②将 A节点的右节点，指向A 节点的右节点的左节点

detail:

 
单旋转(右旋转)
         创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
         对节点A进行右旋转的步骤
                ①将A 节点的 左节点 的 右节点 ，指向 A节点
                ②将 A节点的左节点，指向A 节点的左节点的右节点

 detail:

 双旋转
        前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
        int[] arr = { 10, 11, 7, 6, 8, 9 };  运行原来的代码可以看到，并没有转成 AVL树.
        int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
问题分析{ 10, 11, 7, 6, 8, 9 }

         ①当符合右旋转的条件时
         ②若它的左子树的右子树的高度大于它的右子树的高度
         ③先对当前这个结点的左节点进行左旋转
         ④再对当前结点进行右旋转
代码:

  1. package ASDF;
  2.  
  3. public class AVLT {
  4.     public static void main(String[] args) {
  5.         //int []arr = {4,3,6,5,7,8};
  6.         int []arr = {10, 11, 7, 6, 8, 9};
  7.         AVLTree avlTree = new AVLTree();
  8.         for (int i = 0; i < arr.length; i++) {
  9.             avlTree.add(new Node(arr[i]));
  10.         }
  11.         avlTree.midOrder();
  12.         System.out.println(avlTree.getRoot().height());
  13.         System.out.println(avlTree.getRoot().LeftHeight());
  14.         System.out.println(avlTree.getRoot().RighttHeight());
  15.         System.out.println(avlTree.getRoot().left.left.value);
  16.     }
  17. }
  18.  
  19. class AVLTree{
  20.     private Node root;
  21.  
  22.  
  23.  
  24.     public Node getRoot() {
  25.         return root;
  26.     }
  27.  
  28.     public void setRoot(Node root) {
  29.         this.root = root;
  30.     }
  31.  
  32.     //添加结点
  33.     public void add(Node node){
  34.         if(root==null){
  35.             root=node;
  36.         }else {
  37.             root.add(node);
  38.         }
  39.     }
  40.     public void midOrder(){
  41.         if(root!=null){
  42.             root.midOrder();
  43.         }else {
  44.             System.out.println("empty!");
  45.         }
  46.     }
  47.     public Node search(int value){
  48.         if(root==null){
  49.             return null;
  50.         }else {
  51.             return root.Search(value);
  52.         }
  53.     }
  54.     public Node parentSearch(int value){
  55.         if(root==null){
  56.             return null;
  57.         }else {
  58.             return root.searchParent(value);
  59.         }
  60.     }
  61.  
  62.     //返回
  63.  
  64.     /**
  65.      *
  66.      * @param node 当做二叉排序树的根节点
  67.      * @return 返回以node为根节点的二叉排序树的最小结点的值
  68.      */
  69.     public int delRigthTreeMin(Node node){
  70.        Node t = node;
  71.         while (t.left!=null){
  72.             t=t.left;
  73.         }
  74.         delNode(t.getValue());
  75.         return t.getValue();
  76.     }
  77.     public void delNode(int value){
  78.         if(root==null){
  79.             return;
  80.         }else {
  81.             //1.先找到要删除的节点
  82.             Node targetNode = search(value);
  83.             if (targetNode == null) {
  84.                 return;
  85.             }
  86.             //若当前这个二叉排序树只有一个结点
  87.             if(root.getLeft()==null&&root.getRight()==null){
  88.                 root=null;
  89.                 return;
  90.             }
  91.             //找targetNode的父节点
  92.            Node parent = parentSearch(value);
  93.             //若要删除的是叶子结点
  94.             if(targetNode.getLeft()==null&&targetNode.getRight()==null){
  95.                 //判断targetNode是父结点的左还是右子结点
  96.                 if(parent.getLeft()!=null&&parent.getLeft().getValue()==value){
  97.                     parent.setLeft(null);
  98.                 }else if(parent.getRight()!=null&&parent.getRight().getValue()==value) {
  99.                     parent.setRight(null);
  100.                 }
  101.             }else if(targetNode.getLeft()!=null&&targetNode.getRight()!=null){//删除有两颗子树的结点
  102.                 int i = delRigthTreeMin(targetNode.right);
  103.                 targetNode.setValue(i);
  104.             }else {//删除只有一颗子树的结点
  105.                 //若要删除的结点有左子节点
  106.                 if (targetNode.left!=null){
  107.                     if(parent!=null){
  108.                         if(parent.getLeft().getValue()==value){//若targetNode是parent的左子节点
  109.                             parent.left=targetNode.left;
  110.                         }else if(parent.right==targetNode){
  111.                             parent.right=targetNode.left;
  112.                         }
  113.                     }else {
  114.                         root=targetNode.left;
  115.                     }
  116.  
  117.                 }else {
  118.                     if(parent!=null){
  119.                         if(parent.left.getValue()==value){//若targetNode是parent的左子节点
  120.                             parent.left=targetNode.right;
  121.                         }else if(parent.right==targetNode){
  122.                             parent.right=targetNode.right;
  123.                         }
  124.                     }else {
  125.                         root=targetNode.right;
  126.                     }
  127.  
  128.                 }
  129.             }
  130.  
  131.         }
  132.     }
  133. }
  134. class Node {
  135.     int value;//结点权值
  136.     Node left;//指向左子节点
  137.     Node right;//指向右子节点
  138.  
  139.  
  140.     //返回当前结点的(以该结点为根节点的树的高度)
  141.     public int height(){
  142.         return Math.max(left==null?0: left.height(),right==null?0: right.height())+1;
  143.     }
  144.     //返回左子树的高度
  145.     public int LeftHeight(){
  146.        if(left==null){
  147.            return 0;
  148.        }else {
  149.            return left.height();
  150.        }
  151.     }
  152.     //返回右子树的高度
  153.     public int RighttHeight(){
  154.         if(right==null){
  155.             return 0;
  156.         }else {
  157.             return right.height();
  158.         }
  159.     }
  160.  
  161.     //左旋转
  162.     public void leftRotate(){
  163.         //创建新结点(以当前根节点的值)
  164.         Node node = new Node(value);
  165.         //把新的结点的左子树 设置成当前结点的左子树
  166.         node.left=left;
  167.         //把新的结点的右子树 设置成当前结点的右子树的左子树
  168.         node.right=right.left;
  169.         //把当前结点的值 替换成右子结点的值
  170.         this.value = right.value;
  171.         //把当前结点的右子树 设置成当前结点的右子树的右子树
  172.         this.right = right.right;
  173.         //把当前结点的左子树(左子节点) 设置为新的结点
  174.         left=node;
  175.     }
  176.     //右旋转
  177.     public void rightRotate(){
  178.         //创建新结点(以当前根节点的值)
  179.         Node node = new Node(value);
  180.         //把新的结点的右子树 设置成当前结点的右子树
  181.         node.right=right;
  182.         //把新的结点的左子树 设置成当前结点的左子树的右子树
  183.         node.left=left.right;
  184.         //把当前结点的值 替换成左子结点的值
  185.         this.value = left.value;
  186.         //把当前结点的左子树 设置成当前结点的左子树的左子树
  187.         this.left = left.left;
  188.         //把当前结点的右子树(右子节点) 设置为新的结点
  189.         right=node;
  190.     }
  191.  
  192.     //双旋转
  193.     public void Rotate(){
  194.         //创建新结点(以当前根节点的值)
  195.         Node node = new Node(value);
  196.         //把新的结点的右子树 设置成当前结点的右子树
  197.         node.right=right;
  198.         //把新的结点的左子树 设置成当前结点的左子树的右子树
  199.         node.left=left.right;
  200.         //把当前结点的值 替换成左子结点的值
  201.         this.value = left.value;
  202.         //把当前结点的左子树 设置成当前结点的左子树的左子树
  203.         this.left = left.left;
  204.         //把当前结点的右子树(右子节点) 设置为新的结点
  205.         right=node;
  206.     }
  207.     //查找要删除的结点
  208.     public Node Search(int value){
  209.         if(value==this.value){
  210.             return this;
  211.         }else if(value<this.value){
  212.             if(this.left==null){
  213.                 return null;
  214.             }
  215.             return this.left.Search(value);
  216.         }else {
  217.             if(this.right==null){
  218.                 return null;
  219.             }
  220.             return this.right.Search(value);
  221.         }
  222.     }
  223.     //查找要删除结点的父结点
  224.     public Node searchParent(int value){
  225.         if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
  226.                 return this;
  227.         }else {
  228.             //若查找的值 小于当前结点的值 且当前结点的左子节点不为空
  229.             if(value<this.value&&this.left!=null){
  230.                 return this.left.searchParent(value);
  231.             }else if(value>=this.value&&this.right!=null){
  232.                 return this.right.searchParent(value);
  233.             }else{
  234.                 return null;//没有父节点
  235.             }
  236.         }
  237.  
  238.     }
  239.  
  240.     //添加结点的方法
  241.     //递归的形式添加结点 注意需要满足二叉排序树的要求
  242.     public void add(Node node){
  243.         if (node==null){
  244.             return;
  245.         }
  246.         if(node.value<this.value){
  247.             if (this.left==null){//若当前结点 左子节点为null
  248.                 this.left = node;
  249.             }else{
  250.                 this.left.add(node);//递归的向左子树添加
  251.             }
  252.         }else {//添加的结点的值>当前结点的值
  253.             if(this.right==null){
  254.                 this.right=node;
  255.             }else{
  256.                 this.right.add(node);//递归的向右子树添加
  257.             }
  258.         }
  259.         //当添加完一个结点后 若:右子树的高度-左子树的高度>1，左旋转
  260.         if((RighttHeight()-LeftHeight())>1){
  261.             //若它右子树的左子树的高度大于它的右子树的高度
  262.             if(right!=null&&right.LeftHeight()>right.RighttHeight()){
  263.                 //先对当前结点的左子树 左旋转
  264.                 right.rightRotate();
  265.                 //再对当前结点进行右旋转
  266.                 leftRotate();
  267.             }else {
  268.                 leftRotate();
  269.             }
  270.             return;
  271.         }
  272.         if((LeftHeight()-RighttHeight())>1){
  273.                //若它左子树的右子树的高度大于它的左子树的高度
  274.             if(left!=null&&left.RighttHeight()>left.LeftHeight()){
  275.                 //先对当前结点的左子树 左旋转
  276.                 left.leftRotate();
  277.                 //再对当前结点进行右旋转
  278.                 rightRotate();
  279.             }else {
  280.                 rightRotate();
  281.             }
  282.         return;
  283.         }
  284.     }
  285.  
  286.     public void midOrder(){
  287.         if(this.left!=null){
  288.             this.left. midOrder();
  289.         }
  290.         System.out.println(this);
  291.         if(this.right!=null){
  292.             this.right. midOrder();
  293.         }
  294.     }
  295.  
  296.     public Node(int value) {
  297.         this.value = value;
  298.     }
  299.  
  300.     public int getValue() {
  301.         return value;
  302.     }
  303.  
  304.     public Node getLeft() {
  305.         return left;
  306.     }
  307.  
  308.     public void setLeft(Node left) {
  309.         this.left = left;
  310.     }
  311.  
  312.     public Node getRight() {
  313.         return right;
  314.     }
  315.  
  316.     public void setRight(Node right) {
  317.         this.right = right;
  318.     }
  319.  
  320.     public void setValue(int value) {
  321.         this.value = value;
  322.     }
  323.  
  324.     @Override
  325.     public String toString() {
  326.         return "Node{" +
  327.                 "value=" + value +
  328.                 '}';
  329.     }
  330.  
  331.  
  332. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/858145
推荐阅读
相关标签

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

  

闽ICP备14008679号