平衡二叉树 (平衡查找树) 小咪咪 2021-10-29 07:24 438阅读 0赞 ## **平衡二叉树(AVL 树)** ## ### 看一个案例(说明二叉排序树可能的问题) ### ![1460404-20190609204205330-1398837969.png][] #### **上边 BST 存在的问题分析:** #### 1. 左子树全部为空,从形式上看,更像一个单链表. 2. 插入速度没有影响 3. 查询速度明显降低(因为需要依次比较), 不能发挥 BST ### **基本介绍** ### 1. 平衡二叉树也叫平衡**二叉搜索树**(Self-balancing binary search tree)又被称为 AVL 树, 可以保证查询效率较高。 2. 具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵。 平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 ### **应用案例-单旋转(左旋转)** ### //左旋转方法 private void leftRotate() { //创建新的结点,以当前根结点的值 Node newNode = new Node(value); //把新的结点的左子树设置成当前结点的左子树 newNode.left = left; //把新的结点的右子树设置成带你过去结点的右子树的左子树 newNode.right = right.left; //把当前结点的值替换成右子结点的值 value = right.value; //把当前结点的右子树设置成当前结点右子树的右子树 right = right.right; //把当前结点的左子树(左子结点)设置成新的结点 left = newNode; } ### **应用案例-单旋转(右旋转)** ### //右旋转 private void rightRotate() { Node newNode = new Node(value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; right = newNode; } ### **应用案例-双旋转** ### #### **解决思路分析** #### 1. 当符合右旋转的条件时 2. 如果它的左子树的右子树高度大于它的左子树的高度 3. 先对当前这个结点的左节点进行左旋转 4. 在对当前结点进行右旋转的操作即可 #### **代码实现\[AVL 树的汇总代码(完整代码)\]** #### package com.kyrie.avl; public class AVLTreeDemo { public static void main(String[] args) { // int[] arr = { 4, 3, 6, 5, 7, 8 }; 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()); System.out.println("左子树高度 = " + avlTree.getRoot().leftHeight()); System.out.println("右子树高度 = " + avlTree.getRoot().rightHeight()); System.out.println("根节点为 = " + avlTree.getRoot()); } } //创建AVL树 AVL:平衡二叉树 (平衡查找树) class AVLTree { private Node root;// 根节点 public Node getRoot() { return root; } // 添加节点的方法 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; } @Override public String toString() { return "Node [value = " + value + "]"; } // 左子树树高 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; } // 左旋转方法 private void leftRotate() { // 创建心得节点,值为当前树的根节点的值 Node newNode = new Node(value); // 把新的节点的左孩子设置成当前节点的左孩子 newNode.left = left; // 把新的节点的右孩子设置成当前节点的右孩子的左孩子 newNode.right = right.left; // 把当前节点的值替换成右孩子的值 value = right.value; // 把当前节点的右孩子设置成当前节点右孩子的右孩子 right = right.right; // 把当前节点的左孩子设置成新的节点 this.left = newNode; } // 右旋转方法 private void rightRotate() { Node newNode = new Node(value); newNode.right = right; newNode.left = left.right; value = left.value; left = left.left; this.right = newNode; } // 添加节点的方法 // 递归实现,且需要满足二叉查找树的特点,左子树全小于根节点,右子树全大于根节点 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); } } // 判断是否满足AVL的定义 : 左右子树的高度差的绝对值不能超过1 // 1.左旋转 : 右子树高度 - 左子树高度 > 1 if ((rightHeight() - leftHeight()) > 1) { // 根节点的右孩子的 左子树的高度 > 根节点的右孩子的右子树高度 if (right != null && right.leftHeight() > right.rightHeight()) { // 先进行右旋转 right.rightRotate(); // 再对根节点进行左旋转 leftRotate(); } else { // 直接进行左旋转 leftRotate(); } return; // 很关键,假如这个已经旋转过了,直接返回就可以了,避免节外生枝 } // 2 右旋转 : 左子树高度 - 右子树高度 > 1 if ((leftHeight() - rightHeight()) > 1) { if (left != null && left.rightHeight() > right.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(); } } } 转载于:https://www.cnblogs.com/kyrie211/p/10994772.html [1460404-20190609204205330-1398837969.png]: /images/20211029/621910e38bd3438598d122a9c896a7c1.png
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 225 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 395 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 266 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 239 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 283 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 323 阅读
相关 二叉树之-平衡二叉查找树 学习顺序 第一篇文章 带着问题去阅读 知识准备:知道什么是二叉查找树,了解节点的前驱和后继的定义,这样有助于理解在旋转的过程中如何处理节点之间的变换 问题一 客官°小女子只卖身不卖艺/ 2021年11月01日 10:56/ 0 赞/ 314 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 439 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 386 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 439 阅读
还没有评论,来说两句吧...