一、平衡二叉树
定义特点是1.满足二叉查找树的特点
=》左子树小于根节点
=》右子树大于根节点
2.它的|左子树、与右子树的深度差|<2
=>目的是要充分的利用二叉查找树的特性，维护深度
二、实现
为了维护它的特性，在插入添加的过程中会变得很复杂。参考
1.首先来看下旋转
=》对于树中的元素，还按照这个规则来重新实现
例如：
2.那么在平衡二叉树的插入过程当中会遇到哪些情况？
（1）LL
解决办法=》找到最根的左、右子树深度不平衡的节点
=》然后根的左子树变根节点
=》然后根可以变成右子树
=》如果根的左子树有右子树，则变为此根的左子树
（2）RR
解决办法：同上相反
（3）LR
解决办法：首先调整成LL情况如何调整？
（4）RL
解决办法：首先调整成RR如何调整那？
三、代码实现
=》节点结构
=》查询
=》添加
=》实例化
=》中序遍历
=》效果图
=》删除节点（实现了在）
//节点结构
class TreeNode{
private int num;
private int diff; //平衡因子
private TreeNode leftChild;
private TreeNode rightChild;
//get /set method
}
//得到当前节点的深度
/*
* This will through recursion to get the deep
* but the deep does not contain the current node
* =>judge is null
* =>null return
* =>is not
* =>get the left and right
* =>judge the left right return the max
* */
public static int getDeep(TreeNode t){
if(t==null)return 0;
int leftDeep=0;
int rightDeep=0;
leftDeep+=getDeep(t.getLeftChild());
rightDeep+=getDeep(t.getRightChild());
return leftDeep>=rightDeep?leftDeep+1:rightDeep+1;
}
//实例化当前的节点的平衡因子
/*
* initialization the node attribute diff
* */
public static void initDiff(TreeNode t){
if(t==null)return;
int leftDeep=getDeep(t.getLeftChild());
int rightDeep=getDeep(t.getRightChild());
t.setDiff(leftDeep-rightDeep);
}
//递归实现插入操作
//解决了插入后平衡因子改变的记录
/*
*How to insert a number
*There have two method to input it
*
*if just insert the BST you can not user the recursion
*you can just get the insert node position
*
*use the recursion can get the path
*that after insert the balance is interrupted
* */
public static TreeNode insertBST(TreeNode t,int num){
//if(searchBST(num))return false;
if(t==null){
t=new TreeNode();
t.setNum(num);
t.setLeftChild(null);
t.setRightChild(null);
t.setDiff(0);
}else{
// if(t.getNum()==num){
// return null;
// }
//there have the recursion
//insert left
if(t.getNum()>num){
t.setLeftChild(insertBST(t.getLeftChild(), num));
initDiff(t);
//left-right=2;
if(t.getDiff()==2){
if(num<t.getLeftChild().getNum())
t=LL(t);
else
t=LR(t);
}
}else if(t.getNum()<num){
t.setRightChild(insertBST(t.getRightChild(),num));
initDiff(t);
if(t.getDiff()==-2){
if(num>t.getRightChild().getNum())
t=RR(t);
else
t=RL(t);
}
}
}
return t;
}
//四个旋转情况
//LL
/*
* c b |
* / /\ |
* b => a c |
* / |
* a |
* */
public static TreeNode LL(TreeNode t){
TreeNode tn=t.getLeftChild();
t.setLeftChild(tn.getRightChild());
tn.setRightChild(t);
initDiff(tn);
initDiff(t);
return tn;
}
//RR
/*
* c d |
* \ /\ |
* d => c e |
* \ |
* e |
*
* */
public static TreeNode RR(TreeNode t){
TreeNode tn=t.getRightChild();
t.setRightChild(tn.getLeftChild());
tn.setLeftChild(t);
initDiff(tn);
initDiff(t);
return tn;
}
//LR
/*
* d d
* / /
* a => b =>
* \ /
* b a
* */
public static TreeNode LR(TreeNode t){
t.setLeftChild(RR(t.getLeftChild()));
return LL(t);
}
//RL
public static TreeNode RL(TreeNode t){
t.setRightChild(LL(t.getRightChild()));
return RR(t);
}
//删除操作
//当时在查询树的时候处理思路是这样的
//获得删除的节点，如果是叶子节点，那么它的父节点直接指向null
//如果只有左子树，则左子树替代位置
//如果只有右子树，右子树替代位置
//如果都有则，要么从最左边找到最大的代替然后，删除它
//或者从最右边找到最小的代替然后删除
//此处的思路是这样的
//如果没有右子树那么 左子树代替了
//如果有右子树，那么找到最小的右子树值，替换，删除
public static TreeNode deleteAVL(TreeNode t,int num){
if(t==null)return null;
else{
if(t.getNum()==num){
//在查询二叉树的时候删除分为了
//叶子节点、只有左子树、只有右子树、有左右子树
//
if(t.getRightChild()==null)t=t.getLeftChild();
else{
TreeNode tn=t.getRightChild();
while(tn.getLeftChild()!=null)
tn=tn.getLeftChild();
t.setNum(tn.getNum());
t.setRightChild(deleteAVL(t.getRightChild(),t.getNum()));
initDiff(t);
t.setDiff(t.getDiff()+1);
}
return t;
}else if(t.getNum()>num){
t.setLeftChild(deleteAVL(t.getLeftChild(),num));
}else{
t.setRightChild(deleteAVL(t.getRightChild(),num));
}
}
initDiff(t);
//删除一个节点结果只有+1 -1
if(t.getDiff()==2){
//必定是+1所致
//删除的是右节点
//判断是LL 偶然LR
if(t.getLeftChild().getDiff()==1)
t=LL(t);
else if(t.getLeftChild().getDiff()==-1)
t=LR(t);
}else if(t.getDiff()==-2){
if(t.getRightChild().getDiff()==-1||t.getRightChild().getDiff()==0)
t=RR(t);
else if(t.getRightChild().getDiff()==1)
t=RL(t);
}
return t;
}
相关推荐
平衡二叉树（Balanced Binary Tree）是数据结构中的一个重要概念，尤其在算法设计和数据库系统中发挥着关键作用。本实验是针对广东工业大学（简称“广工”）学生的一次数据结构课程实践，旨在让学生深入理解平衡...
平衡二叉树，又称自平衡查找树，是一种特殊的二叉树数据结构，它保持了数据的平衡分布，确保了查找、插入和删除等操作的时间复杂度尽可能低，通常为O(log n)。这种特性使得平衡二叉树在大数据量的场景下表现优越，是...
本实验“广工数据结构实验——平衡二叉树”着重探讨了一种特殊类型的数据结构，即平衡二叉树。平衡二叉树是二叉搜索树（Binary Search Tree, BST）的一个变体，它通过保持树的高度平衡来确保查找、插入和删除操作的...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
在IT领域，数据结构是计算机科学的基础，而平衡二叉树是其中一个重要概念，尤其对于高效的数据检索和存储。在这个“数据结构平衡二叉树课程设计”中，我们重点探讨了如何使用C语言实现平衡二叉树，并包含了课程设计...
在数据结构课程设计中，平衡二叉树的实现是一个重要的实践环节，旨在加深对数据结构和算法的理解。平衡二叉树是一种特殊的二叉树，它确保了任何节点的两个子树的高度差不超过1，从而保证了操作如查找、插入和删除的...
（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡...
平衡二叉树是一种特殊的二叉树数据结构，它的左右两个子树的高度差不超过1，并且每个节点的两个子树都是平衡二叉树。这种特性使得平衡二叉树在插入、删除和搜索等操作上的性能比普通二叉树更为优秀，接近于最理想的...
在IT领域，数据结构是计算机科学的基础，而平衡二叉树是其中一个重要概念。平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树结构，它保持了树的高度平衡，从而确保了数据的查找、插入和删除操作具有较高的效率...
平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树特性的同时，通过特定的结构调整策略，确保了树的高度平衡。这样的设计使得在平衡二叉树中执行插入、删除和查找等操作的时间复杂度可以保持为O(log n)，...
在本教程中，我们将深入探讨几个关键的数据结构：栈、队列、二叉树、顺序查找、二分查找以及图的遍历。这些基础知识对于理解和编写高效的算法至关重要。 1. 栈（Stack） 栈是一种后进先出（LIFO）的数据结构，类似...
平衡二叉树（AVL树）是数据结构中的一个重要概念，它是一种自平衡的二叉搜索树，确保了任何节点的两个子树的高度差不超过1。这使得AVL树在查找、插入和删除操作上具有较高的效率。本文将深入探讨平衡二叉树的递归...
总结而言，二叉树是基础且重要的数据结构，平衡二叉树如AVL树和红黑树则通过保持树的平衡优化了操作效率。平均查找长度是衡量查找性能的关键指标，而二叉树的删除操作则需要根据节点的子节点情况灵活处理。源代码...
注意，由于题目中没有明确指出使用平衡二叉树，也可以选择其他数据结构，如哈希表（HashMap）来实现，但平衡二叉树在这种需要高效查找和排序的场景下，通常会表现出更好的性能。在实际编程中，应根据具体需求和性能...
平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树特性的同时，通过特定的结构调整策略，使得树的高度始终保持平衡，从而确保了在插入、删除和查找操作中的效率。这种数据结构在信息技术领域有着广泛的应用...
实现了二叉查找树的查找、插入...实现了平衡二叉树（AVL树）的查找、插入、删除和迭代遍历的完整功能，插入时的各种旋转操作按照经典数据结构教材实现，并有详细的注释和说明。删除操作和相关旋转方法有单独描述文档。
在IT领域，数据结构是计算机科学的基础，而平衡二叉树是其中的一种重要结构，它在数据查询、插入和删除操作中保持了较高的效率。本文将深入探讨如何使用C语言实现平衡二叉树的非递归版本，以提高程序执行性能。 ...
这个过程不仅加深了对二叉树和平衡二叉树的理解，还展示了C++在处理数据结构和算法时的强大能力。在实际编程中，类似的方法也可以应用于其他平衡二叉树类型，比如AVL树或红黑树，只需稍作调整以适应特定树的旋转规则...
哈希表和平衡二叉树是两种在计算机科学中广泛使用的数据结构，它们在存储和检索数据时具有各自的优势。本项目将这两种数据结构用C语言实现，旨在帮助学习者深入理解它们的工作原理以及如何在实际编程中应用。 首先...