hao3100590
- 浏览: 131446 次
- 性别:
- 来自: 成都
-
最新评论
-
yi_chao_jiang：
你好，多谢分享，问个问题，在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709：
为什么我的tabhost显示不出来？ 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴：
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501：
牛死人了！！！
B-树 -
mengsina：
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.问题描述
什么是平衡二叉树？在此就不在赘述，下面主要就几个关键问题进行分析
2.关键问题
a.AVL树的非递归与递归插入
平衡二叉树的非递归的关键:
1.在寻找插入位置和旋转的时候设置其路径上的平衡因子，这个要特别注意
当然非递归比递归复杂的多，但是对于理解其执行过程很有帮助！
2.是旋转之后可能并没有产生效果（实际上是旋转成功，但是输出的树没有变），因为在修改的时候，并没有注意结点的改变，没有使用指针引用，修改原来树的指针，指向旋转之后的新的根结点。
这个在setBF(Node<T>* r);中分了两种情况：a.旋转结点是根结点; b.旋转结点非根结点，必须手动设置pre前序指针指向。
3.是左旋和右旋，这里是将LL,LR都归为L。将RR,RL都归为R
其实处理方式还是很简单的，就是改变指针的指向，稍微复杂些的就是设置平衡因子
图示见下：
a.对于LL以B为支点，B上升一个位置，右子树高度加1，则平衡因子1-->0,同理A：2-->0;
RR也是一样，平衡因子都变为0.
b.就是决定平衡因子主要决定于结点C（C的平衡因子只可能为-1,1,0）,然后分情况讨论，画出实图既可以
决定平衡因子。
平衡二叉树非递归插入算法伪代码：
if(root是空) 插入根结点；
else{
看插入结点是否存在；
if(存在x) 将count++;
else{
看插入结点的位置，是否会增加树的高度（通过判断插入位置是否有兄弟）；
while(结点不空){
查找插入结点位置，并记录其前序结点，如果插入结点会增加树的高度，则在插入过程中
增加结点的平衡因子，并记录到需要旋转的结点。
}
将新结点插入到指定位置；
通过记录的需要旋转的结点，进行LL,RR,LR,RL旋转
}
}
b.平衡因子分析
具体分析如下图：
3.代码
avltree.h
//平衡二叉树（AVL--balanced binary tree）
#ifndef AVLTREE_H
#define AVLTREE_H
template<class T>
struct Data{
T data; //结点数据
int count; //次数
int bf; //平衡因子（对于AVL平衡二叉树是需要的）
};
template<class T>
struct Node{
Data<T> data;
Node<T> *rchild, *lchild;
};
template<class T>
class AVLTree{
public:
AVLTree();
AVLTree(int a[], int n);
~AVLTree();
Node<T>* deleteAVL(T x);//删除结点，返回最新根结点(删除还没完全实现，没有恢复平衡特性)
Node<T>* insertAVL(T x);//插入结点，返回最新根结点
void insertAVL(Node<T>* &root, T x, int *h);//递归插入结点，h是树的高度
Node<T>* searchAVL(T x);
Node<T>* findMin(); //查找最小值
Node<T>* findMax(); //查找最大值
void printAVL();
bool hasSibling(T x); //x是否有兄弟结点,x可能不存在，若不存在则在待插入位置若有兄弟则返回真
int height();
private:
Node<T>* root;
void print(Node<T>* root);
//AVL的调整策略
void lChange(Node<T>* &r);//左旋转(LL--LR),r为旋转的根结点（bf为2，-2）
void rChange(Node<T>* &r);//右旋转(RR--RL),r为旋转的根结点（bf为2，-2）
void create(Node<T>* &root);
void release(Node<T>* &root);
void setBF(Node<T>* r);//设置平衡因子,r为旋转的根结点（bf为2，-2）
int height(Node<T>* root);//树高度
//删除相关
void deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre);//删除结点r,pre是前缀结点,若pre为空，说明删除的是根结点
void changeBF(Node<T>* &root); //重新设置整个树的平衡因子
void resetAVL(Node<T>* &root); //重新设置树为平衡树
};
#endif
b.avltree.cpp
#include <iostream>
#include "avltree.h"
using namespace std;
template<class T>
AVLTree<T>::AVLTree(){
root = NULL;
create(root);
}
template<class T>
AVLTree<T>::AVLTree(int a[], int n){
root = NULL;
if(n <= 0) return;
for(int i=0; i<n; i++){
insertAVL(a[i]);
}
}
template<class T>
AVLTree<T>::~AVLTree(){
release(root);
}
//删除结点，返回最新根结点(删除过程中也可能造成树不平衡)
template<class T>
Node<T>* AVLTree<T>::deleteAVL(T x){
if(!root) return root;
Node<T>* pre = NULL, *r = root;
//查找待删除结点位置(pre是r的前序结点)
while(r){
if((r->data).data == x){
if((r->data).count > 1){
(r->data).count--; return root;
}else{
break;
}
}
pre = r;
r = ((r->data).data > x)?r->lchild:r->rchild;
}
//没找到
if(!r) return root;
//如果pre == NULL说明是root结点
deleteNode(root, r, pre);
//重新设置平衡因子
changeBF(root);
//重新设置树为平衡树
//----------------还没做？-----------------------
resetAVL(root);
return root;
}
//插入结点，返回最新根结点
template<class T>
Node<T>* AVLTree<T>::insertAVL(T x){
Node<T>* r = root;
bool hasSib = false; //**判断待插入位置是否有兄弟（如果有，则树高度不会增加，否则树高度增加平衡因子就要变化）
if(!root){
root = new Node<T>;
root->data.data = x;
root->data.count = 1;
root->data.bf = 0;
root->lchild = root->rchild = NULL;
}else{
Node<T>* pre = r;
Node<T>* n = NULL; //存储的是需要进行旋转的结点及前序结点
//查找待插入结点位置,插入的时候，要设置每个遍历过的结点的平衡因子
Node<T>* m = searchAVL(x); //查找，如果找到（已经存在，直接count++）
if(m){
m->data.count++;
}else{ //肯定没有相等的了，一定会插入新结点
hasSib = hasSibling(x); //看待插入结点是否有兄弟结点，如果无，则在遍历路径过程中平衡因子必然+1或-1，否则不变
while(r){
pre = r;
if(r->data.data > x){
if(!hasSib) r->data.bf++; //待插入结点所在位置无兄弟，树高度增加，路径上的平衡因子要变化
if(r->data.bf == 2) n = r; //记录最近需要旋转的根结点
r = r->lchild;
}else{
if(!hasSib) r->data.bf--;
if(r->data.bf == -2) n = r;
r = r->rchild;
}
}
Node<T>* p = new Node<T>;
p->data.data = x;
p->data.count = 1;
p->data.bf = 0;
p->lchild = p->rchild = NULL;
if((pre->data).data > x){//插入左
if(hasSib) pre->data.bf++;
pre->lchild = p;
}else{
if(hasSib) pre->data.bf--;
pre->rchild = p;
}
//进行平衡旋转
if(n) setBF(n);
}
}
return root;
}
/**插入递归算法
*为什么要设置*h，它决定在出栈进入上次的状态之后，是否需要设置结点的平衡因子，旋转等操作，还是直接继续出栈
*那什么时候需要在弹栈后，还要继续设置上次状态？例如：见图例
*
*/
template<class T>
void AVLTree<T>::insertAVL(Node<T>* &root, T x, int *h){
if(!root){
root = new Node<T>;
root->data.data = x;
root->data.count = 1;
root->data.bf = 0;
*h = 1;
root->lchild = root->rchild = NULL;
}else{
if(x < root->data.data){
insertAVL(root->lchild, x, h);
if(*h){//在左子树中插入了新结点
switch(root->data.bf){
case -1:
root->data.bf = 0;
*h = 0;
break;
case 1:
lChange(root);
*h = 0;
break;
case 0:
root->data.bf = 1;
break;
}
}
}else if(x > root->data.data){
insertAVL(root->rchild, x, h);
if(*h){//在右子树中插入了新结点(往右插入了结点，则平衡因子都要-1)
//下面是设置上一个结点的状态，旋转等,当*h == 0,则返回上一个结点时候直接返回
switch(root->data.bf){
case -1:
*h = 0;
rChange(root);
break;
case 1:
*h = 0;
root->data.bf = 0;
break;
case 0:
root->data.bf = -1;
break;
}
}else{
*h = 0;
root->data.count++;
}
}
}
}
template<class T>
Node<T>* AVLTree<T>::searchAVL(T x){
Node<T>* r = root;
while(r){
if(r->data.data == x) return r;
r = (r->data.data > x)?r->lchild:r->rchild;
}
if(!r) return NULL;
}
template<class T>
void AVLTree<T>::printAVL(){
print(root);
}
template<class T>
Node<T>* AVLTree<T>::findMin(){
Node<T>* r = root;
while(r && r->lchild){
r = r->lchild;
}
return r;
}
template<class T>
Node<T>* AVLTree<T>::findMax(){
Node<T>* r = root;
while(r && r->rchild){
r = r->rchild;
}
return r;
}
template<class T>
void AVLTree<T>::print(Node<T>* root){
if(root){
cout<<root->data.data<<"("<<root->data.count<<","<<root->data.bf<<")"<<" ";
print(root->lchild);
print(root->rchild);
}
}
//左旋转(LL), r为旋转的根结点
template<class T>
void AVLTree<T>::lChange(Node<T>* &r){
Node<T>* p, *q;
p = r->lchild;
//------LL型-------
if(p->data.bf == 1){
cout<<"---LL---"<<endl;
r->lchild = p->rchild;
p->rchild = r;
r->data.bf = 0;
p->data.bf = 0;
r = p;
}
//------LR型--------（p->data.bf == -1）
else{
cout<<"---LR---"<<endl;
q = p->rchild;
p->rchild = q->lchild;
r->lchild = q->rchild;
q->lchild = p;
q->rchild = r;
if(q->data.bf == 1){
p->data.bf = 0;
r->data.bf = -1;
}else if(q->data.bf == -1){
p->data.bf = 1;
r->data.bf = 0;
}else{//q->data.bf == 0
p->data.bf = 0;
r->data.bf = 0;
}
q->data.bf = 0;
r = q;
}
}
//右旋转(RR), r为旋转的根结点
template<class T>
void AVLTree<T>::rChange(Node<T>* &r){
Node<T>* p, *q;
p = r->rchild;
//---------RR型-------------
if(p->data.bf == -1){
cout<<"---RR---"<<endl;
r->rchild = p->lchild;
p->lchild = r;
r->data.bf = 0;
p->data.bf = 0;
r = p;
}
//---------RL型(p->data.bf == 1)-------------
else{
cout<<"---RL---"<<endl;
q = p->lchild;
r->rchild = q->lchild;
p->lchild = q->rchild;
q->lchild = r;
q->rchild = p;
if(q->data.bf == -1){
r->data.bf = 1;
p->data.bf = 0;
}else if(q->data.bf == 1){
r->data.bf = 0;
p->data.bf = -1;
}else if(q->data.bf == 0){
r->data.bf = 0;
p->data.bf = 0;
}
q->data.bf = 0;
r = q;
}
}
template<class T>
void AVLTree<T>::create(Node<T>* &root){
T ch;
cout<<"请输入二叉平衡树的结点（'#'结束）"<<endl;
while(cin>>ch){
if(ch == '#') break;
insertAVL(ch);
//int a = 1;
//insertAVL(root, ch, &a);
}
}
template<class T>
void AVLTree<T>::release(Node<T>* &root){
if(root){
release(root->lchild);
release(root->rchild);
delete root;
}
}
//r为需要旋转的根结点，旋转过程中旋转的树的高度必然减少，故而需要调节其路径中树的平衡因子
template<class T>
void AVLTree<T>::setBF(Node<T>* r){
Node<T>* p = root, *pre = NULL;
//查找旋转结点以及前缀,查找过程中设置旋转结点之上的平衡因子
while(p){
if(p == r) break;
pre = p;
//在旋转结点路径之上的结点的平衡因子要变化（左减右加,左边旋转意味着左子树高度会减1，右边旋转加1）
if(p->data.data > r->data.data){
p->data.bf--;
p = p->lchild;
}else{
p->data.bf++;
p = p->rchild;
}
}
//如果旋转的是根结点
if(!pre){
if(r->data.bf == 2) lChange(root);
else if(r->data.bf == -2) rChange(root);
}
//旋转非根结点，其前缀后的结点改变，故而重新设置指针
else{
if(r->data.bf == 2){
lChange(r);
if(pre->lchild == p) pre->lchild = r;
else pre->rchild = r;
}else if(r->data.bf == -2){
rChange(r);
if(pre->lchild == p) pre->lchild = r;
else pre->rchild = r;
}
}
}
/**
*x是否有兄弟结点
*1.若x存在，如果有兄弟返回true，否则false
*2.若x不存在，则在待插入位置若有兄弟则返回true，否则false
*/
template<class T>
bool AVLTree<T>::hasSibling(T x){
Node<T>* r = root, *pre = NULL;
while(r){
//存在x
if(r->data.data == x){
if(!pre) return false;//root结点
else if(pre->lchild && pre->rchild) return true;
else return false;
}
pre = r;
r = (r->data.data > x)?r->lchild:r->rchild;
}
//r为空，不存在x
if(!r){
if(pre->lchild || pre->rchild) return true;
else return false;
}
return false;
}
template<class T>
int AVLTree<T>::height(){
return height(root);
}
template<class T>
int AVLTree<T>::height(Node<T>* root){
int hl, hr;
if(!root) return 0;
else{
hl = height(root->lchild);
hr = height(root->rchild);
return (hl>hr?hl:hr)+1;
}
}
template<class T>
void AVLTree<T>::deleteNode(Node<T>* &root, Node<T>* r, Node<T>* pre){
Node<T>* p;
if(!r->rchild && !r->lchild){ //如果是叶子结点
if(pre){
if(pre->lchild == r){
pre->lchild = NULL;
}else{
pre->rchild = NULL;
}
}else{
root = NULL;
}
delete r;
}else if(r->rchild && r->lchild){ //如果左右子树都有
p = r;
//寻找右子树的最左结点
r = r->rchild;
while(r->lchild){
r = r->lchild;
}
//将删除结点的左结点接到找到的最左结点之后
r->lchild = p->lchild;
//删除结点(如果pre是空，说明删除结点是根结点,不用改变前序结点指针)
if(pre){
if(pre->lchild == p) pre->lchild = p->rchild;
else pre->rchild = p->rchild;
}else{
root = p->rchild;
}
delete p;
}else if(r->lchild){ //如果只有左子树
p = r;
if(pre){
if(pre->lchild == p) pre->lchild = r->lchild;
else pre->rchild = r->lchild;
}else{
root = r->lchild;
}
delete p;
}else{ //如果只有右子树
p = r;
if(pre){
if(pre->lchild == p) pre->lchild = r->rchild;
else pre->rchild = r->rchild;
}else{
root = r->rchild;
}
delete p;
}
}
template<class T>
void AVLTree<T>::changeBF(Node<T>* &root){
int bl, br;
if(root){
bl = height(root->lchild);
br = height(root->rchild);
root->data.bf = bl - br;
changeBF(root->lchild);
changeBF(root->rchild);
}
}
template<class T>
void AVLTree<T>::resetAVL(Node<T>* &root){
}
c.main.cpp
#include <iostream>
#include "avltree.cpp"
using namespace std;
int main(){
cout<<"----------平衡二叉树的测试----------"<<endl;
AVLTree<int> avl;
//int a[] = {29, 17, 13, 8, 34, 12, 6, 28, 32, 36, 30};
//AVLTree<int> avl(a, 11);
cout<<"tree:";
avl.printAVL();
/*
Node<int>* r;
cout<<"\n搜索8:";
r = avl.searchAVL(8);
if(r) cout<<r->data.data<<endl;
else cout<<"无"<<endl;
cout<<"\n搜索10:";
r = avl.searchAVL(10);
if(r) cout<<r->data.data<<endl;
else cout<<"无"<<endl;
cout<<"\n最小，最大值:";
r = avl.findMin();
cout<<r->data.data<<",";
r = avl.findMax();
cout<<r->data.data<<endl;
cout<<"\n树高度："<<avl.height()<<endl;
cout<<"\n删除17（root）"<<endl;
r = avl.deleteAVL(17);
avl.printAVL();
*/
return 0;
}
分享到：
发表评论
-
排序方法总结
2012-08-12 11:34 1176这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14581.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2833一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 12101.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 13141.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 14051.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
B-树实现
2012-08-10 11:03 16241.什么是B-树？ 这个在我的前一篇博客中已经详细的阐释过： ... -
二叉排序树
2012-08-10 10:25 14751.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56661.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 12291.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12721.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 26021.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 15501.算法描述 a.数据结构与算法（Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 11081.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 18241.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 13321.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9961.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1829参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10301.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2318算法描述:生成前N个整 ...
相关推荐
平衡二叉树是一种特殊类型的二叉树，它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这种数据结构的主要目的是为了保持数据的平衡分布，从而保证在插入、删除和查找操作中的效率。 ...
用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能，目的是把二叉树的平衡算法记录在这里（备忘）。 目前只做了增加删除节点时二叉树自动平衡，保证这棵树什么时候都是平衡状态；如何将一棵不平衡的二叉树...
在IT领域，数据结构是计算机科学的基础，而平衡二叉树是其中一个重要概念，尤其对于高效的数据检索和存储。在这个“数据结构平衡二叉树课程设计”中，我们重点探讨了如何使用C语言实现平衡二叉树，并包含了课程设计...
"平衡二叉树时间复杂度计算1" 在计算机科学中，平衡二叉树是一种特殊的二叉树数据结构，它的时间复杂度计算是非常重要的。下面我们将详细介绍平衡二叉树的时间复杂度计算。 首先，让我们了解什么是平衡二叉树。...
平衡二叉树（Balanced Binary Tree）是数据结构中的一个重要概念，尤其在算法设计和数据库系统中发挥着关键作用。本实验是针对广东工业大学（简称“广工”）学生的一次数据结构课程实践，旨在让学生深入理解平衡...
平衡二叉树是一种特殊的二叉树数据结构，其特性在于左右子树的高度差不超过1，这使得在树中的任何节点上进行查找、插入和删除操作的时间复杂度都能保证为O(log n)。AVL树是最早被提出的自平衡二叉搜索树，由G. M. ...
平衡二叉树是一种特殊的二叉树结构，它的主要特性是左右子树的高度差不超过1，保证了树的形态均匀，从而在查找、插入和删除等操作上的效率接近于最佳的二叉查找树。这种特性使得平衡二叉树在数据结构和算法中占有...
平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树性质的同时，确保了左右子树的高度差不超过1。这样的结构使得在平衡二叉树中的搜索、插入和删除操作的时间复杂度都能保持在O(log n)的水平，大大提高了...
在数据结构课程设计中，平衡二叉树的实现是一个重要的实践环节，旨在加深对数据结构和算法的理解。平衡二叉树是一种特殊的二叉树，它确保了任何节点的两个子树的高度差不超过1，从而保证了操作如查找、插入和删除的...
二叉树和平衡二叉树是数据结构领域中的重要概念，尤其在计算机科学中，它们在数据存储、搜索和排序等方面发挥着关键作用。这里我们将深入探讨这两种数据结构及其C#实现。 首先，二叉树是一种特殊的树形数据结构，...
平衡二叉树是一种特殊的二叉树结构，它的左右两个子树的高度差不超过1，并且左右两个子树都是一棵平衡二叉树。这种数据结构在计算机科学中有着广泛的应用，尤其是在搜索、排序和数据存储等领域。本文将详细介绍平衡...
平衡二叉树是一种特殊的二叉树数据结构，其特性是左右子树的高度差不超过1，这使得在平衡二叉树中的查找、插入和删除操作的时间复杂度都能保持在O(log n)级别，大大提高了效率。在本项目中，我们将探讨如何使用C++...
平衡二叉树是一种特殊的二叉树数据结构，它在保持二叉查找树特性的同时，通过特定的结构调整策略，确保了树的高度平衡。这样的设计使得在平衡二叉树中执行插入、删除和查找等操作的时间复杂度可以保持为O(log n)，...
平衡二叉树是一种特殊的二叉树结构，它的左右子树高度差不超过1，且每个节点的左右子树都是平衡二叉树。这种设计使得在平衡二叉树中进行查找、插入和删除操作的时间复杂度可以达到O(log n)，极大地提高了数据操作的...
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
1. 利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找 插入和删除。 2 .初始，平衡二叉树为空树，操作界面给出查找，插入和删除三种操作供 选择，每种操作均要提示输入关键字，每次插入或删除...
本话题将深入探讨“生成平衡二叉树”的概念，以及如何使用C++语言实现这一过程。平衡二叉树，如AVL树或红黑树，确保了树的高度平衡，从而在查找、插入和删除操作中保持较高的效率。 首先，我们需要了解平衡二叉树的...