hao3100590
- 浏览: 128655 次
- 性别:
- 来自: 成都
-
最新评论
-
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 1131这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14161.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11731.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15871.什么是B-树？ 这个在我的前一篇博客中已经详细的阐释过： ... -
二叉排序树
2012-08-10 10:25 14161.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56091.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11871.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25541.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14921.算法描述 a.数据结构与算法（Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10731.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17501.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9531.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 9991.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
用JAVASCRIPT+VML实现平衡二叉树里增加节点删除节点的功能，目的是把二叉树的平衡算法记录在这里（备忘）。 目前只做了增加删除节点时二叉树自动平衡，保证这棵树什么时候都是平衡状态；如何将一棵不平衡的二叉树...
利用平衡二叉树实现一个动态查找表。 （1）实现动态查找表的三种基本功能：查找、插入和删除。 （2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找...
平衡二叉树c++模版，此模版採用二叉链表实现，是本人一个通宵搞出来的。可以提供时间复杂度在nlgn的排序，也可以提供lgn的查询。是一个很不错的数据结构，可是以和其它的现在比较新的一些数据结构比美。虽然有人对其...
（1） 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。 （2） 平衡二叉树的显示采用凹入表现形式。 （3）输入的...
C语言编写的 数据结构 平衡二叉树 演示、含课程设计报告 多种输出平衡二叉树格式
题 目 二叉排序树与平衡二叉树的实现 1、课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 使学生掌握软件设计的基本内容...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
1. 利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找 插入和删除。 2 .初始，平衡二叉树为空树，操作界面给出查找，插入和删除三种操作供 选择，每种操作均要提示输入关键字，每次插入或删除...
平衡二叉树操作的演示的课程设计，包附加的功能。
1. 完成 学生, 课程,选课,成绩 的增删改查 学生ID 学生名 选课名 成绩 001 张三 C++ 60 ...1.采用平衡二叉树的可靠管理，源码规范，文档齐备：80分 2.采用动态数组的可靠管理，源码规范，文档齐备：60分
2015广工数据结构实验--平衡二叉树(包含源码和实验报告
C语言使用递归创建一颗平衡二叉树的源代码文件
二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码 二叉树和平衡二叉树(B树)的C#实现源码
平衡二叉树课程设计 平衡二叉树课程设计 平衡二叉树课程设计
平衡二叉树时间复杂度计算1
数据结构课程设计-平衡二叉树的操作！本人以前做的就是这个，非常不错的，不过就只有代码哦！