关于AVLTree（C++实现）没有统一旋转操作的问题

2023-08-02 01:02:04 62
最近疫情比较严重，只能在家里休息，利用休息之余，我用C++把AVL树实现了一遍
大学老师只讲一些比较简单的数据结构和算法，这些高级数据结构还是需要自己主动学习并且动手来实现的，
从前只听说过AVLTree，我从看书了解原理到把它一点一点写出来最后在调试一共花了大概3天的时间。应该已经算很长时间了。
一般情况下AVL树是不用我么自己写的，但是为了有一份已经实现的代码作为我以后再来回顾算法实现的依照，我还是决定对自己狠一些把它实现了一遍
以下代码均采用C++11标准
在ubuntu18.04上经过编译和调试
/*
*BinarySearchTree.h
*1.添加元素时需自己做判断元素是否合法
*2.除层序遍历外，本源代码均采用递归遍历，若要减少栈的消耗，应该实现递归遍历
*3.本代码实现的AVL树没有统一旋转操作，采用分情况讨论LL,LR,RR,RL来进行树的平衡
*Createdon:2020年1月29日
*Author:LuYonglei
*/
#ifndefSRC_BINARYSEARCHTREE_H_
#defineSRC_BINARYSEARCHTREE_H_
#include
template
classBinarySearchTree{
public:
BinarySearchTree(int(*cmp)(Elemente1,Elemente2));//比较函数指针
virtual~BinarySearchTree();
intsize();//元素的数量
boolisEmpty();//是否为空
voidclear(){
//清空所有元素
NODE*node=root_;
root_=nullptr;
usingnamespacestd;
queueq;
q.push(node);
while(!q.empty()){
NODE*tmp=q.front();
if(tmp->left!=nullptr)
q.push(tmp->left);
if(tmp->right!=nullptr)
q.push(tmp->right);
deletetmp;
q.pop();
}
}
voidadd(Elemente){
//添加元素
add(e,cmp_);
}
voidremove(Elemente){
//删除元素
remove(Node(e,cmp_));
}
boolcontains(Elemente){
//是否包含某元素
returnNode(e,cmp_)!=nullptr;
}
voidpreorderTraversal(bool(*visitor)(Element&e)){
//前序遍历
if(visitor==nullptr)
return;
boolstop=false;//停止标志，若stop为true，则停止遍历
preorderTraversal(root_,stop,visitor);
}
voidinorderTraversal(bool(*visitor)(Element&e)){
//中序遍历
if(visitor==nullptr)
return;
boolstop=false;//停止标志，若stop为true，则停止遍历
inorderTraversal(root_,stop,visitor);
}
voidpostorderTraversal(bool(*visitor)(Element&e)){
//后序遍历
if(visitor==nullptr)
return;
boolstop=false;//停止标志，若stop为true，则停止遍历
postorderTraversal(root_,stop,visitor);
}
voidlevelOrderTraversal(bool(*visitor)(Element&e)){
//层序遍历，迭代实现
if(visitor==nullptr)
return;
levelOrderTraversal(root_,visitor);
}
intheight(){
//树的高度
returnheight(root_);
}
boolisComplete(){
//判断是否是完全二叉树
returnisComplete(root_);
}
private:
intsize_;
typedefstruct_Node{
Elemente;
_Node*parent;
_Node*left;
_Node*right;
intheight;//节点的高度
_Node(Elemente_,_Node*parent_):
e(e_),parent(parent_),left(nullptr),right(nullptr),height(1){
//节点构造函数
}
inlineboolisLeaf(){
return(left==nullptr&&right==nullptr);
}
inlineboolhasTwoChildren(){
return(left!=nullptr&&right!=nullptr);
}
inlineintbalanceFactor(){
//获得节点的平衡因子
intleftHeight=left==nullptr?0:left->height;//获得左子树的高度
intrightHeight=right==nullptr?0:right->height;//获得右子树的高度
returnleftHeight-rightHeight;
}
inlineboolisBalanced(){
//判断node是否平衡
intbalanceFactor_=balanceFactor();
returnbalanceFactor_>=-1&&balanceFactor_<=1;//平衡因子为-1,0,1则返回true
}
inlinevoidupdateHeight(){
//更新节点的高度
intleftHeight=left==nullptr?0:left->height;//获得左子树的高度
intrightHeight=right==nullptr?0:right->height;//获得右子树的高度
height=1+(leftHeight>rightHeight?leftHeight:rightHeight);//把节点高度更新为左右子树最大的高度+1
}
inlineboolisLeftChild(){
//判断节点是否是父亲节点的左子结点
returnparent!=nullptr&&parent->left==this;
}
inlineboolisRightChild(){
//判断节点是否是父亲节点的右子结点
returnparent!=nullptr&&parent->right==this;
}
inline_Node*tallerChild(){
//获得高度更高的子树
intleftHeight=left==nullptr?0:left->height;//获得左子树的高度
intrightHeight=right==nullptr?0:right->height;//获得右子树的高度
if(leftHeight>rightHeight)
returnleft;
if(leftHeighte);
if(cmp==0)//找到了元素
returnnode;
if(cmp>0){//待寻找元素大于节点存储的元素
node=node->right;
}else{//待寻找元素小于节点存储的元素
node=node->left;
}
}
returnnullptr;
}
NODE*predecessor(NODE*node){
//返回node的前驱节点
if(node==nullptr)
returnnullptr;
//前驱节点在左子树
NODE*tmp=node->left;
if(tmp!=nullptr){
while(tmp->right!=nullptr)
tmp=tmp->right;
returntmp;
}
//从父节点，祖父节点中寻找前驱节点
while(node->parent!=nullptr&&node==node->parent->left){
node=node->parent;
}
returnnode->parent;
}
NODE*successor(NODE*node){
//返回node的后继节点
if(node==nullptr)
returnnullptr;
//后继节点在右子树
NODE*tmp=node->right;
if(tmp!=nullptr){
while(tmp->left!=nullptr)
tmp=tmp->left;
returntmp;
}
//从父节点，祖父节点中寻找后继节点
while(node->parent!=nullptr&&node==node->parent->right){
node=node->parent;
}
returnnode->parent;
}
voidafterRotate(NODE*gNode,NODE*pNode,NODE*child){
//在左旋转与右旋转中统一调用
pNode->parent=gNode->parent;
if(gNode->isLeftChild())
gNode->parent->left=pNode;
elseif(gNode->isRightChild())
gNode->parent->right=pNode;
else
//此时gNode->parent为nullptr，gNode为root节点
root_=pNode;
if(child!=nullptr)
child->parent=gNode;
gNode->parent=pNode;
//左右子树发生变化，所以要更新高度
gNode->updateHeight();
pNode->updateHeight();
}
voidrotateLeft(NODE*gNode){
//对gNode进行左旋转
NODE*pNode=gNode->right;
NODE*child=pNode->left;
gNode->right=child;
pNode->left=gNode;
afterRotate(gNode,pNode,child);
}
voidrotateRight(NODE*gNode){
//对gNode进行右旋转
NODE*pNode=gNode->left;
NODE*child=pNode->right;
gNode->left=child;
pNode->right=gNode;
afterRotate(gNode,pNode,child);
}
voidrebalance(NODE*gNode){
//恢复平衡,grand为高度最低的不平衡节点
NODE*pNode=gNode->tallerChild();
NODE*nNode=pNode->tallerChild();
if(pNode->isLeftChild()){
if(nNode->isLeftChild()){
//LL
/*
*gNode
*/对gNode右旋
*pNode====>pNode
*//\
*nNodenNodegNode
*/
rotateRight(gNode);
}else{
//LR
/*
*gNodegNode
*/对pNode左旋/对gNode右旋
*pNode====>nNode====>nNode
*\//\
*nNodepNodepNodegNode
*/
rotateLeft(pNode);
rotateRight(gNode);
}
}else{
if(nNode->isLeftChild()){
//RL
/*
*gNodegNode
*\对pNode右旋\对gNode左旋
*pNode====>nNode====>nNode
*/\/\
*nNodepNodegNodepNode
*/
rotateRight(pNode);
rotateLeft(gNode);
}else{
//RR
/*
*gNode
*\对gNode左旋
*pNode====>pNode
*\/\
*nNodegNodenNode
*/
rotateLeft(gNode);
}
}
}
voidafterAdd(NODE*node){
//添加node之后的调整
if(node==nullptr)
return;
node=node->parent;
while(node!=nullptr){
if(node->isBalanced()){
//如果节点平衡，则对其更新高度
node->updateHeight();
}else{
//此时对第一个不平衡节点操作，使其平衡
rebalance(node);
//整棵树恢复平衡后,跳出循环
break;
}
node=node->parent;
}
}
voidadd(Elemente,int(*cmp_)(Elemente1,Elemente2)){
//当树为空时，添加的节点作为树的根节点
if(root_==nullptr){
root_=newNODE(e,nullptr);
size_++;
//插入一个根节点之后进行调整
afterAdd(root_);
return;
}
//当添加的节点不是第一个节点
NODE*parent=root_;
NODE*node=root_;
intcmp=0;//比较结果
while(node!=nullptr){
parent=node;//保存父节点
cmp=cmp_(e,node->e);//由函数指针来比较
if(cmp>0){
node=node->right;//添加的元素大于节点中的元素
}elseif(cmp<0){
node=node->left;//添加的元素小于节点中的元素
}else{
node->e=e;//相等时就覆盖
return;//添加的元素等于节点中的元素,直接返回
}
}
//判断要插入父节点的哪个位置
NODE*newNode=newNODE(e,parent);//为新元素创建节点
if(cmp>0){
parent->right=newNode;//添加的元素大于节点中的元素
}else{
parent->left=newNode;//添加的元素小于节点中的元素
}
size_++;
//添加一个新节点之后进行调整
afterAdd(newNode);
}
voidafterRemove(NODE*node){
//删除node之后的调整
if(node==nullptr)
return;
node=node->parent;
while(node!=nullptr){
if(node->isBalanced()){
//如果节点平衡，则对其更新高度
node->updateHeight();
}else{
//此时对不平衡节点操作，使其平衡
rebalance(node);
}
node=node->parent;
}
}
voidremove(NODE*node_){
//删除某一节点
if(node_==nullptr)
return;
size_--;
//优先删除度为2的节点
if(node_->hasTwoChildren()){
NODE*pre=successor(node_);//找到node_的后继节点
node_->e=pre->e;//用后继节点的值覆盖度为2的节点的值
//删除后继节点(后继节点的度只能为1或0)
node_=pre;
}
//此时node_的度必然为0或1
NODE*replacement=node_->left!=nullptr?node_->left:node_->right;
if(replacement!=nullptr){//node_的度为1
replacement->parent=node_->parent;
if(node_->parent==nullptr)//度为1的根节点
root_=replacement;
elseif(node_->parent->left==node_)
node_->parent->left=replacement;
else
node_->parent->right=replacement;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
deletenode_;
}elseif(node_->parent==nullptr){//node_是叶子节点，也是根节点
root_=nullptr;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
deletenode_;
}else{//node_是叶子节点，但不是根节点
if(node_->parent->left==node_)
node_->parent->left=nullptr;
else
node_->parent->right=nullptr;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
deletenode_;
}
}
voidpreorderTraversal(NODE*node,bool&stop,
bool(*visitor)(Element&e)){
//递归实现前序遍历
if(node==nullptr||stop==true)
return;
stop=visitor(node->e);
preorderTraversal(node->left,stop,visitor);
preorderTraversal(node->right,stop,visitor);
}
voidinorderTraversal(NODE*node,bool&stop,bool(*visitor)(Element&e)){
//递归实现中序遍历
if(node==nullptr||stop==true)
return;
inorderTraversal(node->left,stop,visitor);
if(stop==true)
return;
stop=visitor(node->e);
inorderTraversal(node->right,stop,visitor);
}
voidpostorderTraversal(NODE*node,bool&stop,
bool(*visitor)(Element&e)){
//递归实现后序遍历
if(node==nullptr||stop==true)
return;
postorderTraversal(node->left,stop,visitor);
postorderTraversal(node->right,stop,visitor);
if(stop==true)
return;
stop=visitor(node->e);
}
voidlevelOrderTraversal(NODE*node,bool(*visitor)(Element&e)){
if(node==nullptr)
return;
usingnamespacestd;
queueq;
q.push(node);
while(!q.empty()){
NODE*node=q.front();
if(visitor(node->e)==true)
return;
if(node->left!=nullptr)
q.push(node->left);
if(node->right!=nullptr)
q.push(node->right);
q.pop();
}
}
intheight(NODE*node){
//某一节点的高度
returnnode->height;
}
boolisComplete(NODE*node){
if(node==nullptr)
returnfalse;
usingnamespacestd;
queueq;
q.push(node);
boolleaf=false;//判断接下来的节点是否为叶子节点
while(!q.empty()){
NODE*node=q.front();
if(leaf&&!node->isLeaf())//判断叶子节点
returnfalse;
if(node->left!=nullptr){
q.push(node->left);
}elseif(node->right!=nullptr){//node->left==nullptr&&node->right!=nullptr
returnfalse;
}
if(node->right!=nullptr){
q.push(node->right);
}else{//node->right==nullptr
leaf=true;
}
q.pop();
}
returntrue;
}
};
template
BinarySearchTree::BinarySearchTree(int(*cmp)(Elemente1,Elemente2)):
size_(0),root_(nullptr),cmp_(cmp){
//树的构造函数
}
template
BinarySearchTree::~BinarySearchTree(){
//析构函数
clear();
}
template
inlineintBinarySearchTree::size(){
//返回元素个数
returnsize_;
}
template
inlineboolBinarySearchTree::isEmpty(){
//判断是否为空树
returnsize_==0;
}
#endif/*SRC_BINARYSEARCHTREE_H_*/
main方法
/*
*main.cpp
*
*Createdon:2020年1月29日
*Author:LuYonglei
*/
#include"BinarySearchTree.h"
#include
#include
usingnamespacestd;
template
intcompare(Elemente1,Elemente2){
//比较函数,相同返回0,e1e2返回1
returne1==e2?0:(e1
boolvisitor(Elemnet&e){
cout<a(compare);
//a.add(85);
//a.add(19);
//a.add(69);
//a.add(3);
//a.add(7);
//a.add(99);
//a.add(95);
//a.add(2);
//a.add(1);
//a.add(70);
//a.add(44);
//a.add(58);
//a.add(11);
//a.add(21);
//a.add(14);
//a.add(93);
//a.add(57);
//a.add(4);
//a.add(56);
//a.remove(99);
//a.remove(85);
//a.remove(95);
clock_tstart=clock();
for(inti=0;i<1000000;i++){
a.add(i);
}
for(inti=0;i<1000000;i++){
a.remove(i);
}
//a.inorderTraversal(visitor);
clock_tend=clock();
cout<
总结
以上所述是小编给大家介绍的关于AVLTree（C++实现）没有统一旋转操作的问题，希望对大家有所帮助！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
关于AVLTree（C++实现）没有统一旋转操作的问题

热门推荐

随机推荐
