网站导航
> 文档中心 > 平衡二叉树(AVL 树)

平衡二叉树(AVL 树)

网友: 文档中心 2022-06-05 08:43:55

平衡二叉树(AVL 树)

看一个案例(说明二叉排序树可能的问题)

给你一个数列{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、伸展树等。
  3. 举例说明, 看看下面哪些AVL树, 为什么?
    平衡二叉树(AVL 树)

应用案例-单旋转(左旋转)

  1. 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8} 2) 思路分析(示意图)
    平衡二叉树(AVL 树)
  2. 代码实现
 public void leftRotate() { //创建新的结点，以当前根结点的值 Node newNode = new Node(value); //把新的结点的左子树设置成当前结点的左子树 newNode.left = left; //把新的结点的右子树设置成带你过去结点的右子树的左子树 newNode.right = right.left; //把当前结点的值替换成右子结点的值 value = right.value; //把当前结点的右子树设置成当前结点右子树的右子树 right = right.right; //把当前结点的左子树(左子结点)设置成新的结点 left = newNode;    }

应用案例-单旋转(右旋转)

  1. 要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
  2. 思路分析(示意图)
    平衡二叉树(AVL 树)
  3. 代码实现
 public void rightRotate() { Node newNode = new Node(value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; right = newNode;    }

应用案例-双旋转

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

  1. 问题分析
    平衡二叉树(AVL 树)
  2. 解决思路分析
  1. 当符号右旋转的条件时
  2. 如果它的左子树的右子树高度大于它的左子树的高度
  3. 先对当前这个结点的左节点进行左旋转
  4. 在对当前结点进行右旋转的操作即可
  1. 代码实现[AVL 树的汇总代码(完整代码)]
package com.iflytek.avl;public class AVLTreeDemo {  public static void main(String[] args) {      int[] arr = {10, 11, 7, 6, 8, 9};      //创建一个 AVLTree 对象      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()); //3      System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2      System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2      System.out.println("当前的根结点=" + avlTree.getRoot());//8  }}//创建AVLTreeclass AVLTree {  private Node root;  public Node getRoot() {      return root;  }  //查找要删除的节点  public Node search(int value) {      if (root == null) {   return null;      } else {   return root.search(value);      }  }  //查找父节点  public Node searchParent(int value) {      if (root == null) {   return null;      } else {   return root.searchParent(value);      }  }  // 编写方法:  // 1. 返回的 以 node 为根结点的二叉排序树的左子树最大结点的值  // 2. 删除 node 为根结点的二叉排序树的左子树最大结点  /**   * @param node 传入的结点(当做二叉排序树的根结点)   * @return 返回的 以 node 为根结点的二叉排序树的最小结点的值   */  public int delLeftTreeMax(Node node) {      Node target = node;      // 循环的查找右子节点，就会找到最大值      while (target.right != null) {   target = target.right;      }      // 这时 target 就指向了最大结点      // 删除最大结点      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 (root.left == null && root.right == null) {root = null;return;   }   // 去找到 targetNode 的父结点   Node parent = searchParent(value);   // 如果要删除的结点是叶子结点   if (targetNode.left == null && targetNode.right == null) {// 判断 targetNode 是父结点的左子结点，还是右子结点if (parent.left != null && parent.left.value == value) {//是左子节点    parent.left = null;} else if (parent.right != null && parent.right.value == value) {//是右子节点    parent.right = null;}   } else if (targetNode.left != null && targetNode.right != null) {// 删除有两颗子树的节点int maxVal = delLeftTreeMax(targetNode.left);targetNode.value = maxVal;   } else {// 删除只有一颗子树的结点// 如果要删除的结点有左子结点if (targetNode.left != null) {    if (parent != null) { // 如果 targetNode 是 parent 的左子结点 if (parent.left.value == value) {     parent.left = targetNode.left; } else {     parent.right = targetNode.left; }    } else { root = targetNode.left;    }} else {// 如果要删除的结点有右子结点    if (parent != null) { // 如果 targetNode 是 parent 的左子结点 if (parent.left.value == value) {     parent.left = targetNode.right; } else {     parent.right = targetNode.right; }    } else { 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("二叉排序树为空，不能遍历");      }  }}//创建Node 结点class Node {  int value;  Node left;  Node right;  public Node(int value) {      this.value = value;  }  @Override  public String toString() {      return "Node{" +"value=" + value +'}';  }  // 返回 以该结点为根结点的树的高度  public int height() {      return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;  }  // 返回右子树的高度  public int rightHeight() {      if (right == null) {   return 0;      }      return right.height();  }  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;  }  // 返回左子树的高度  public int leftHeight() {      if (left == null) {   return 0;      }      return left.height();  }  //查找要删除的结点  /**   * @param value 希望要删除的值   * @return 如果找到返回该结点，否则返回 null   */  public Node search(int value) {      if (this.value == value) {   return this;      } else if (value < this.value) {   if (this.left == null) {return null;   }   return this.left.search(value);      } else {   if (this.right == null) {return null;   }   return this.right.search(value);      }  }  //查找要删除结点的父结点  /**   * @param value 要找到的结点的值   * @return 返回的是要删除的结点的父结点，如果没有就返回 null   */  public Node searchParent(int value) {      //如果当前结点就是要删除的结点的父结点，就返回      //程序是从左往右执行的，必须先判断子节点不为空，然后才能比较值      if ((this.left != null && this.left.value == value) ||(this.right != null && this.right.value == value)) {   return this;      } else {   //如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空   if (this.value > value && this.left != null) {return this.left.searchParent(value);//向左子树递归查找   } else if (this.value <= value && this.right != null) {return this.right.searchParent(value);//向右子树递归查找   } else {return null;// 没有找到父结点   }      }  }  //添加结点的方法  // 递归的形式添加结点，注意需要满足二叉排序树的要求  public void add(Node node) {      if (node == null) {   return;      }      //判断传入的结点的值，和当前子树的根结点的值关系      if (node.value < this.value) {//添加的结点的值小于 当前结点的值   //如果当前结点左子结点为 null   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();      }  }}
网络标签：

相关问题