如何使用Java的平衡二叉树

这篇文章主要讲解了“如何使用Java的平衡二叉树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何使用Java的平衡二叉树”吧！

二叉排序树可能的问题

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

问题分析：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 左子树全部为空，从形式上看，更像一个单链表;

3. 插入速度没有影响;

4. 查询速度明显降低(因为需要一次比较)，不能发挥BST的优势。因为每次还要比较左子树，其查询速度，比单链表还慢。

5. 解决方案-平衡二叉树(ALV)

基本介绍

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)，又称为AVL树，可以保证查询效率较高。

3. 具有以下特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有  红黑树、AVL、替罪羊树、Treap、伸展树等;

4. 举例说明，下图前两个都是平衡二叉树，第一个左右子树的高度差绝对值是1，第二个左右子树高度差的绝对值是0，而第三个的左右子树高度差的绝对值是2，这样第三个就不是平衡二叉树;

平衡二叉树之左旋转

步骤：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 创建一个新的节点newNode，值等于当前根节点的值。

3. 把新节点的左子树设置成当前节点的左子树。

4. 把新节点的右子树设置成当前节点的右子树的左子树。

5. 把当前节点的值换为当前右子节点的值。

6. 把当前节点的右子树设置成右子树的右子树。

7. 把当前节点的左子树设置为新的节点。

平衡二叉树之右旋转

步骤：

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 创建一个新的节点，值等于当前根的节点的值。

3. 把新节点的右子树设置成当前节点的右子树。

4. 把新节点的左子树设置成当前节点的左子树的右子树。

5. 把当前节点的值换位左子节点的值。

6. 把当前节点的左子树设置成左子树的左子树。

7. 把当前节点的右子树设置为新的节点。

平衡二叉树之双旋转

在某些情况下，单旋转不能完成完成平衡二叉树的转换，需要进行两次旋转。

1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

2. 如果它的右子树的左子树的高度大于它的右子树的右子树的高度，需要先对右子树进行右旋转，再对当前节点进行左旋转。

3. 如果它的左子树的右子树高度大于它的左子树的左子树高度，

4. 需要对左子树先进行左旋转,再对当前节点进行右旋转。

代码案例

package com.xie.avl;  public class AVLTreeDemo {     public static void main(String[] args) {         int[] arr = {4, 3, 6, 5, 7, 8};         AVLTree avlTree = new AVLTree();         for (int i = 0; i < arr.length; i++) {             avlTree.add(new Node(arr[i]));         }         System.out.println("中序遍历");         avlTree.infixOrder();         System.out.println("在没有平衡处理前~~");         System.out.println("树的高度=" + avlTree.getRoot().height());         System.out.println("树的左子树的高度=" + avlTree.getRoot().leftHeight());         System.out.println("树的右子树的高度=" + avlTree.getRoot().rightHeight());     } }  class AVLTree {     private Node root;      public Node getRoot() {         return root;     }      public void setRoot(Node root) {         this.root = root;     }      //查找要删除的节点的父节点     public Node searchParent(Node node) {         if (root != null) {             return root.searchParent(node);         } else {             return null;         }     }      //查找要删除的节点     public Node search(int value) {         if (root == null) {             return null;         } else {             return root.search(value);         }     }      /**      * 找到以node 根的二叉排序树的最小值，并删除以node 为根节点的二叉排序树的最小节点      *      * @param node 传入节点（当做二叉排序树的根节点)      * @return 返回以node为根节点的二叉排序树的最小节点值      */     public int delRightTreeMin(Node node) {         Node target = node;         //循环查找左节点         while (target.left != null) {             target = target.left;         }         //删除最小节点         delNode(target.value);         return target.value;     }      /**      * 找到以node 根的二叉排序树的最大值，并删除以node 为根节点的二叉排序树的最大节点      *      * @param node 传入节点（当做二叉排序树的根节点)      * @return 返回以node为根节点的二叉排序树的最大节点值      */     public int delLeftTreeMax(Node node) {         Node target = node;         while (target.right != null) {             target = target.right;         }          //删除最大节点         delNode(target.value);         return target.value;     }      //删除节点     public void delNode(int value) {         if (root == null) {             return;         } else {             Node targetNode = search(value);             if (targetNode == null) {                 return;             }             if (targetNode == root) {                 root = null;                 return;             }             Node parentNode = searchParent(targetNode);              if (targetNode.left == null && targetNode.right == null) {                 //如果要删除的节点是叶子节点                 if (parentNode.left != null && parentNode.left.value == targetNode.value) {                     parentNode.left = null;                 }                 if (parentNode.right != null && parentNode.right.value == targetNode.value) {                     parentNode.right = null;                 }             } else if (targetNode.left != null && targetNode.right != null) {                 //如果要删除的节点是有两个子树的节点                 int minValue = delRightTreeMin(targetNode.right);                 targetNode.value = minValue;                 //上下代码删除效果一样                 //int maxValue = delLeftTreeMax(targetNode.left);                 //targetNode.value = maxValue;             } else {                 //要删除的节点是只有左子节点                 if (targetNode.left != null) {                     if (parentNode != null) {                         if (parentNode.left == targetNode) {                             parentNode.left = targetNode.left;                         } else {                             parentNode.right = targetNode.left;                         }                     } else {                         //如果父节点是空，让root换位                         root = targetNode.left;                     }                 } else {//要删除的节点是只有右子节点                     if (parentNode != null) {                         if (parentNode.left == targetNode) {                             parentNode.left = targetNode.right;                         } else {                             parentNode.right = targetNode.right;                         }                     } else {                         //如果父节点是空，让root换位                         root = targetNode.right;                     }                  }             }         }     }      //添加节点     public void add(Node node) {         if (root == null) {             root = node;         } else {             root.add(node);         }     }      //中序遍历     public void infixOrder() {         if (root != null) {             root.infixOrder();         } else {             System.out.println("二叉排序为空，不能遍历");         }     } }  class Node {     int value;     Node left;     Node right;      public Node(int value) {         this.value = value;     }      /**      * 返回左子树的高度      *      * @return      */     public int leftHeight() {         if (left == null) {             return 0;         }         return left.height();     }      /**      * 返回右子树的高度      *      * @return      */     public int rightHeight() {         if (this.right == null) {             return 0;         }         return right.height();     }      /**      * 返回以该节点为根节点的树的高度      *      * @return      */     public int height() {         return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1;     }      /**      * 左旋转      */     public void leftRotate() {         //创建新的节点，以当前根节点的值         Node newNode = new Node(value);         //把新的节点的左子树设置为当前节点的左子树         newNode.left = left;         //把新的右子树设置为当前节点的右子树的左子树         newNode.right = right.left;         //把当前节点的值替换成右子节点的值         value = right.value;         //把当前节点的右子树设置成当前节点的右子节点的右子树         right = right.right;         //把当前的节点的左子节点(左子树),设置成新的节点         left = newNode;     }      /**      * 右旋转      */     public void rightRotate() {         //创建新的节点，以当前根节点的值         Node newNode = new Node(value);         //把新的节点的右子树设置成当前节点的右子树         newNode.right = right;         //把新的节点的左子树设置为当前节点左子树的右子树         newNode.left = left.right;         //把当前节点的值换为左子节点的值         value = left.value;         //把当前节点左子树设置成左子树的左子树         left = left.left;         //把当前节点的右子树设置新节点         right = newNode;     }      /**      * 查找要删除节点的父节点      *      * @param node 要删除的节点      * @return 要删除节点的父节点      */     public Node searchParent(Node node) {         //如果当前节点就是要删除节点的父节点就返回         if ((this.left != null && this.left.value == node.value) ||                 (this.right != null && this.right.value == node.value)) {             return this;         } else {             if (this.left != null && node.value < this.value) {                 //如果查找的节点的值小于当前节点的值，向左子树递归查找                 return this.left.searchParent(node);             } else if (this.right != null && value >= this.value) {                 //如果查找的节点的值小于当前节点的值，向左子树递归查找                 return this.right.searchParent(node);             } else {                 return null;             }         }     }      /**      * 查找要删除的节点      *      * @param value 要删除的节点的值      * @return 删除的节点      */     public Node search(int value) {         if (value == this.value) {             return this;         } else if (value < this.value) {             if (this.left != null) {                 return this.left.search(value);             } else {                 return null;             }         } else {             if (this.right != null) {                 return this.right.search(value);             } else {                 return null;             }         }     }      //递归的形式添加节点，满足二叉排序树的要求     public void add(Node node) {         if (node == null) {             return;         }         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.rightRotate();                 leftRotate();             }else{                 //直接进行左旋转即可                 leftRotate();             }             return;         }          //当添加完一个节点后，如果（左子树高度-右子树高度）> 1 ，进行右旋转         if (leftHeight() - rightHeight() > 1) {             //如果它的左子树的右子树高度大于它的左子树的左子树高度，需要对左子树先进行左旋转,再对当前节点进行右旋转             if(left != null && left.rightHeight() > left.leftHeight()){                 left.leftRotate();                 rightRotate();             }else{                 //直接进行右旋转即可                 rightRotate();             }          }     }      //中序遍历     public void infixOrder() {         if (this.left != null) {             this.left.infixOrder();         }         System.out.println(this);         if (this.right != null) {             this.right.infixOrder();         }     }      @Override     public String toString() {         return "Node{" +                 "value=" + value +                 '}';     } }

感谢各位的阅读，以上就是“如何使用Java的平衡二叉树”的内容了，经过本文的学习后，相信大家对如何使用Java的平衡二叉树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！