关键词：
写在前面
实际上,之前已经更新过一篇关于平衡树的笔记了;—>笔记链接;
学习数据结构笔记(12) — [平衡二叉搜索树(AVLTREE)]之前的实现方式需要计算出当前节点的父节点的索引;…左旋右旋实现方式步骤比较明确;
不足之处是仅实现了添加节点时维持二分树的平衡;
本次的平衡树具体操作方式和之前的那种略有不同;所以记录一下吧…
这里的基础会以之前的二分搜索树实现作为基础,在基础上进行改动;笔记链接—>
数据结构 (五) — [二分搜索树 (Java)]
这里首先会在节点内定义属性height表示高度;
然后在树中定义基础方法来获取树的高度;
基础方法获取树的平衡因子:—>左右子树的高度差;
定义了方法 判断当前树是否为二分搜索树(判断中序遍历的结果是否为由小到大排序);
当前树是否为平衡树(平衡因子是否超过1);
以及添加/删除节点时左旋右旋操作维持二分树的平衡;
如图,这不是平衡树
右旋转
这棵树左子树偏高;要进行右旋转
那么,仅需两步;
首先将取出节点8的右子节点9;将节点10作为节点8的右子节点
然后让
节点9作为节点10的左子节点
左旋转
这棵树右子树偏高,需要左旋转
只需两步;
首先将节点6的左子节点5取出,记录;
将节点4作为节点6的左子节点
然后将节点5作为节点4的右子节点
双旋转
有特殊情况的,就得出动双旋转了;
像下面这种就是需要先进行左旋转处理;然后进行右旋转处理;
先对节点7进行左旋转处理
然后对节点10进行右旋转处理
具体代码
package com.company.e_avltree;
import java.util.*;
/**
* @author 小智RE0
* @Date: 2021/12/10/
*/
//由于二分搜索树,需要对元素的大小进行比较;
public class AVLStartTree<T extends Comparable<T>>
//定义内部类结点;
class Node
T val;
//左子树,右子树;
Node leftNode;
Node rightNode;
//树的高度;
int height;
public Node(T val)
//初始化时,树的高度为1;
this.height = 1;
this.val = val;
this.leftNode = null;
this.rightNode = null;
//定义树的根结点;
private Node root;
//定义树结点的个数;
private int size;
public AVLStartTree()
this.root = null;
this.size = 0;
//判空;
public boolean isEmpty()
return this.root == null;
/**
* 获取以指定结点为树的高度
*
* @param node 节点
*/
public int getHeight(Node node)
if (node == null)
return 0;
else
return node.height;
/**
* 获取到以指定结点出发,树的高度因子;左右子树的高度差;
*/
public int getHeightFactor(Node node)
if (node == null)
return 0;
//这里没有取绝对值,可能会出现高度因子为负数的情况
return getHeight(node.leftNode) - getHeight(node.rightNode);
/**
* 判断是否为二分搜索树;
*/
public boolean isBSTTree()
return isBSTTree(root);
/**
* 判断是否为二分搜索树
*/
private boolean isBSTTree(Node node)
List<T> values = new ArrayList<>();
//调用递归方法;将值存到values里面;
inordertraversal(node, values);
//对遍历的值进行遍历,若为二分树,实际上会由小到大排序,若不符合,直接结束;
//注意;由于是让当前节点和后一个结点进行比较,所以循环的次数实际上会少一次;
for (int i = 0; i < values.size() - 1; i++)
//若出现前面的比后面大,直接返回;
if (values.get(i).compareTo(values.get(i + 1)) > 0)
return false;
return true;
/**
* 中序遍历,将遍历值存入集合
*
* @param node 节点
* @param values 遍历的值
*/
private void inordertraversal(Node node, List<T> values)
//递归终止条件;
if (node == null)
return;
//左中右;
inordertraversal(node.leftNode, values);
values.add(node.val);
inordertraversal(node.rightNode, values);
/**
* 判断是否为平衡树;
*/
public boolean isAVLTree()
return isAVLTree(root);
/**
* 判断是否为平衡树
*
* @param node 节点
*/
private boolean isAVLTree(Node node)
//递归终止的条件;
if (node == null)
return true;
//判断当前节点的平衡因子;
if (Math.abs(getHeightFactor(node)) > 1)
return false;
//递归计算左右子树的高度因子;
return isAVLTree(node.leftNode) && isAVLTree(node.rightNode);
/**
* 左旋转处理
*
* @param curNode 当前节点
*/
public Node RotateLeft(Node curNode)
//取得当前节点的右子节点;
Node rNode = curNode.rightNode;
//将右子节点的左子节点取出,标记;
Node rLNode = rNode.leftNode;
//将当前节点作为它右子节点的左子节点;
rNode.leftNode = curNode;
//将当前节点的右子节点的 左子节点 挂接到当前节点的右子节点下;
curNode.rightNode = rLNode;
//更改树的高度;
curNode.height = Math.max(getHeight(curNode.leftNode), getHeight(curNode.rightNode)) + 1;
rNode.height = Math.max(getHeight(rNode.leftNode), getHeight(rNode.rightNode)) + 1;
return rNode;
/***
* 右旋转处理
* @param curNode 当前节点
*/
public Node RotateRight(Node curNode)
//取得当前节点的左子节点;
Node lNode = curNode.leftNode;
//将左子节点的右子节点取出,标记;
Node lRNode = lNode.rightNode;
//将当前节点作为它左子节点的右子节点;
lNode.rightNode = curNode;
//将当前节点的左子节点 的 右子节点挂接到到当前节点的左子节点下;
curNode.leftNode = lRNode;
//更改树的高度;
curNode.height = Math.max(getHeight(curNode.leftNode), getHeight(curNode.rightNode)) + 1;
lNode.height = Math.max(getHeight(lNode.leftNode), getHeight(lNode.rightNode)) + 1;
return lNode;
/**
* 添加元素
*
* @param ele 指定的元素
*/
public void add(T ele)
//判断节点是否存在;
if (contains(ele) != null)
return;
//每次将创建的根节点返回;
root = add(root, ele);
this.size += 1;
//递归添加元素的底层;
private Node add(Node node, T ele)
//不存在就创建;
if (node == null)
return new Node(ele);
//添加的元素和之前的根结点进行比较;
if (ele.compareTo(node.val) > 0)
node.rightNode = add(node.rightNode, ele);
else
node.leftNode = add(node.leftNode, ele);
//添加之后;需要更新当前树的高度,----->计算左右子树的高度+1 作为当前树的高度;
node.height = Math.max(getHeight(node.leftNode), getHeight(node.rightNode)) + 1;
//左旋转,右旋转,以及左右旋转情况判断;
Node resNode = null;
//维持平衡;
//极度偏左;
if (getHeightFactor(node) > 1 && getHeightFactor(node.leftNode) >= 0)
//直接右旋;
resNode = RotateRight(node);
//极度偏右;
else if (getHeightFactor(node) < -1 && getHeightFactor(node.rightNode) <= 0)
//直接左旋;
resNode = RotateLeft(node);
//左树先偏高,后面右子树偏高;
else if (getHeightFactor(node) > 1 && getHeightFactor(node.leftNode) < 0)
//先左旋后右旋;
node.leftNode = RotateLeft(node.leftNode);
resNode = RotateRight(node);
//右树先偏高,后面左子树偏高;
else if (getHeightFactor(node) < -1 && getHeightFactor(node.rightNode) > 0)
//先右旋再左旋;
node.rightNode = RotateRight(node.rightNode);
resNode = RotateLeft(node);
else
//若平衡,就直接用node节点的值;
resNode = node;
return resNode;
/**
* 删除指定数值;
* @param val 指定数值;
*/
public T removeAssignVal(T val)
if (root == null)
System.out.println("空树不用删除");
return null;
//先去找是否存在; 要去新建方法;
Node node = findAssignNode(root, val);
//是否找到;
if (node != null)
//删除后的剩余结点挂到根结点之后;
root = removeAssignVal(root, val);
//元素个数减少;
this.size -= 1;
return node.val;
return null;
/**
* 删除指定结点的底层实现;在根结点为node的二分树中删除指定结点;
*
* @param node 指定根结点出发
* @param val 指定值
*/
private Node removeAssignVal(Node node, T val)
//找到结点时;
if (node.val.compareTo(val) == 0)
//第一种情况==> 该删除结点的左树为空;
if (node.leftNode == null)
//删除当前的结点后;把原来后面的右子树挂到删了结点的位置;
Node RNode = node.rightNode;
node.rightNode = null;
return RNode;
//第二种情况,右树为空;
else if (node.rightNode == null)
//删除当前的结点后;把原来后面的左子树挂到删了结点的位置;
Node LNode = node.leftNode;
node.leftNode = null;
return LNode;
else
//情况三; 左树 右树 都不为空时,可以选择找前驱结点(左子树那块区域的最大值) 或 后继结点(右子树那块区域的最小值)代替删除结点;
//这里选择找后继节点;
Node minR = findMinNodeRecurve(node.rightNode);
Node minRNode = removeMinNode(node.rightNode);
//后继节点放到删除的结点位置;
minR.leftNode = node.leftNode;
minR.rightNode = minRNode;
node.leftNode = null;
node.rightNode = null;
return minR;
//递归;
//找结点时,若当前的根结点比指定的值还大,就去左边找; 否则去右边找;
if (node.val.compareTo(val) > 0)
node.leftNode = removeAssignVal(node.leftNode, val);
else
node.rightNode = removeAssignVal(node.rightNode, val);
Node resNode = node;
//更新高度;
resNode.height = Math.max(getHeight(resNode.leftNode),getHeight(resNode.rightNode))+1;
//维持平衡操作;
//极度偏左;
if (getHeightFactor(resNode) > 1 && getHeightFactor(resNode.leftNode) >= 0)
//直接右旋;
resNode = RotateRight(resNode);
//极度偏右;
else if (getHeightFactor(resNode) < -1 && getHeightFactor(resNode.rightNode) <= 0)
//直接左旋;
resNode = RotateLeft(resNode);
//左树先偏高,后面右子树偏高;
else if (getHeightFactor(resNode) > 1 && getHeightFactor(resNode.leftNode) < 0)
//先左旋后右旋;
resNode.leftNode = RotateLeft(resNode.leftNode);
resNode = RotateRight(resNode);
//右树先偏高,后面左子树偏高;
else if (getHeightFactor(resNode) < -1 && getHeightFactor(resNode.rightNode) > 0)
//先右旋再左旋;
resNode.rightNode = RotateRight(resNode.rightNode);
resNode = RotateLeft(resNode);
return resNode;
//中序遍历; 稍作修改,让这个遍历结果存入字符串;
public List<String> middleOrder()
//若二叉树为空,则直接返回null空值;
if (root == null)
return null;
//遍历的结果存入集合中;
List<String> list = new ArrayList<>();
middleOrder(root, list);
return list;
//中序遍历底层;
private void middleOrder(Node node, List<String> list)
//递归结束点,若到达最后一层的叶子节点就停止;
if (node == null)
return;
//中序遍历= 先遍历左子树 ==> 获取中间结点 ==> 遍历右子树
middleOrder(node.leftNode, list);
list.add(node.val + "<---高度因子--->" + getHeightFactor(node));
middleOrder(node.rightNode, list);
/**
* 输出打印树的中序遍历信息;
*/
@Override
public String toString()
List<String> list = middleOrder();
list.forEach(a -> System.out.println(a + "\\t"));
return "";
//查询元素;
public Node contains(T ele)
if (root == null)
return null;
return contains(root, ele);
//查询元素的底层;
private Node contains(Node root, T ele)
//递归结束点;
ifavltree(二叉平衡树)底层实现(代码片段)
...3.1右单旋1.3.2左单旋1.3.3左右双旋1.3.4右左双旋1.4完整代码实现及验证1.AVL树的概念如果二叉搜索树的插入序列是有序的或者是接近有序，那么二叉搜索树就会退化为单支树(类似单链表)，查找元素相当于在顺序表中搜索元... 查看详情
学习数据结构笔记(12)---[平衡二叉搜索树(avltree)](代码片段)
B站学习传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）文章目录案例情景引入左旋转图解通过代码实现右旋转图解右旋转的具体实现双旋转处理双旋转具体实现平衡二叉搜索树代码总结案例情景引入比如... 查看详情
avltree(二叉平衡树)底层实现(代码片段)
...3.1右单旋1.3.2左单旋1.3.3左右双旋1.3.4右左双旋1.4完整代码实现及验证1.AVL树的概念如果二叉搜索树的插入序列是有序的或者是接近有序，那么二叉搜索树就会退化为单支树(类似单链表)，查找元素相当于在顺序表中搜索元... 查看详情
二叉平衡树的实现(c语言编程)
...ree外的其他平衡树之一说真的，这个难度不小呀，是高级数据结构中的内容我推荐使用treap,实现起来最容易的一种性能一般，但是挺好用的就在baidu上搜treap可以了参考技术A应该是AVL树吧？实现起来只需注意插入节点时需要旋转... 查看详情
平衡二叉树（avltree）
在学习算法的过程中，二叉平衡树是一定会碰到的，这篇博文尽可能简明易懂的介绍下二叉树的相关概念，然后着重讲下什么事平衡二叉树。（由于作图的时候忽略了箭头的问题，正常的树一般没有箭头，虽然不影响描述的过程... 查看详情
树---数据结构
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。在讲B+树之前必须先了解二叉查找树、平... 查看详情
树的平衡avltree
本篇随笔主要从以下三个方面介绍树的平衡：1）：BST不平衡问题2）：BST旋转3）：AVLTree一：BST不平衡问题的解析之前有提过普通BST的一些一些缺点，例如BST的高度是介于lgN和N之间的，如果是N的的话，显然效率很低，不是我们需... 查看详情
bst,avltree和splaytree的实现(代码片段)
一、定义。1.1BST 二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树： ① 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； ② 若任意节点的右子... 查看详情
day584&585.平衡二叉树-数据结构和算法java(代码片段)
平衡二叉树一、出现的原因解决二叉排序树的问题二、介绍三、平衡思路1、左旋转左旋转思路分析因为左子树高度为1，右子树高度为3，所以要将左侧进行调整，所以进行左旋转代码实现packagecom.achang.avl;/***平衡二叉... 查看详情
[mit6.006]6.avltrees,avlsortavl树，avl排序
...，即从根到叶子结点最长路径的长度。但由于树结构不同平衡情况，高h的结果也不一样，如下图所示： 一、结点的高 由此可以看出，平衡树结构下的高h具有计算性。那么接下来我们再看下各结点的高（heightofnode）... 查看详情
avltree的c++的实现(代码片段)
数据结构之AVL树文章目录前言一、AVL树是什么？1.1AVL树的概念二、AVL树的实现1.AVL树的调整1.1AVL树的底层树调整1.2AVL树的往上层调整1.3AVL树的调整总结2.AVL树的C++实现总结前言数据结构对于每一个编程人员来说都是十分... 查看详情
c++avltree总结(代码片段)
...元素，效率变的很低。我们这里介绍的AVL是一颗高度平衡的二叉搜索树，如果他有n个节点，其高度保持在O(log2n)，搜索时间复杂度为O(log2n)。AVL树的要求是，保证每个节点的左右子树高低之差绝对值不超过1具... 查看详情
将节点插入到平衡二叉搜索树
...【参考方案1】：AVLTree是一个自平衡二叉搜索树。以下是实现的两个资源：1)Resource12)Resource2【讨 查看详情
平衡二叉树(avltree,双链表实现)
首先说下好久没更新了，最近打游戏和工作都有点多，o(^▽^)o。写这个AVL发现自己的代码风格好差，尤其是变量命名这块，后来意识到了，想去改，但是太多了，改了几个就不想改了，做这个是记录下自己的成长吧。另外说下，... 查看详情
c++avltree总结(代码片段)
...元素，效率变的很低。我们这里介绍的AVL是一颗高度平衡的二叉搜索树，如果他有n个节点，其高度保持在O(log2n)，搜索时间复杂 查看详情
数据结构—平衡二叉树
...中了数组的查找优势以及链表的插入、删除优势，因此在数据结构中占有一定的地位。但在一定的情况下二叉排序树又有可能变为链表，例如插入从1~100的数，这时进行数据查找的效率就要降低。为了解决二叉排序树这种左右子... 查看详情
平衡二叉查找树
packageavitree;/***平衡二叉查找树类**@param<T>*/publicclassAvlTree<TextendsComparable<?superT>>{ publicstaticvoidmain(String[]args){ AvlTree<Integer>tree=newAvlTree<Integer>(); 查看详情
数据结构—平衡二叉树
...中了数组的查找优势以及链表的插入、删除优势，因此在数据结构中占有一定的地位。但在一定的情况下二叉排序树又有可能变为链表，例如插入从1~100的数，这时进行数据查找的效率就要降低。为了解决二叉排序树这种左右子... 查看详情