溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、AVL樹刪除
思路：
(1)、首先找到要刪除的結點；沒找到，直接false返回退出即可；
(2)、將其轉化為只有一個分支的結點，前面的路徑都要入棧，
(3)、其父節點(parent)的平衡因子(根據父的左/右=p(要刪除的結點)，修改父的bf)，有幾種情況,i>父節點的bf=1/-1，代表原先有兩個結點，現在剩下一個了，直接退出循環，不用再往上尋找更改bf了；ii>父節點的bf=0；代表此時的往上更改爺爺結點(在此出棧即可，棧中保存了路徑信息)的bf，看情況(bf=2/-2)是否進行旋轉，和要進行相應的旋轉方式。
(4)、判斷棧空，進行相應的連接操作；
(5)、最后刪除這個結點；
相應部分情況：
2、AVL樹刪除代碼
template<typename Type>
bool AVLTree<Type>::remove(AVLNode<Type> *&t, const Type &x){
AVLNode<Type> *p = t;
AVLNode<Type> *parent = NULL; //父結點
AVLNode<Type> *q = NULL; //刪除結點的輔助結點
stack<AVLNode<Type> *> st;
AVLNode<Type> *ppr; //爺爺結點
int flag = 0;
while(p != NULL){
if(p->data == x){
break;
}
parent = p;
st.push(parent);
if(x < p->data){
p = p->leftChild;
}else{
p = p->rightChild;
}
} //以上是：查找刪除點
if(p == NULL){ //沒有要刪除的結點
return false;
}
if(p->leftChild!= NULL && p->rightChild!=NULL){
parent = p;
st.push(parent);
q = p->leftChild;
while(q->rightChild != NULL){
parent = q;
st.push(parent);
q = q->rightChild;
}
p->data = q->data;
p = q;
}
if(p->leftChild != NULL){
q = p->leftChild;
}else{
q = p->rightChild;
}
//以上是：使其要刪除的轉化為只有一個分支的
if(parent == NULL){ //刪除的是根結點，并且無入棧，代表只有一個分支，并沒有尋找
t = q;
}else{
if(parent->leftChild == p){
flag = 0;
parent->leftChild = q;
}else{
flag = 1;
parent->rightChild = q;
}
while(!st.empty()){
parent = st.top();
st.pop();
if(parent->leftChild==q){ //對要刪除的父節點更改bf;
parent->bf++;
}else{
parent->bf--;
}
if(!st.empty()){
ppr = st.top();
if(ppr->leftChild == parent){
flag = 0;
}else{
flag = 1;
}
}
if(parent->bf==-1 || parent->bf==1 ){
break; //刪除前的平衡因子為0，此時不用再調整其它平衡因子,直接退出循環;
}
if(parent->bf == 0){ //原先只有左孩子/右孩子
q = parent; //往上回溯更改爺爺結點的bf；
}else{ //此時到達2,已經不平衡了，的進行旋轉化的調整
if(parent->bf < 0){
flag = -1;
q = parent->leftChild;
}else{
flag = 1;
q = parent->rightChild;
}
if(q->bf == 0){
if(flag == -1){
}
}
if(parent->bf > 0){
q = parent->rightChild;
if(q->bf == 0){
RotateL(parent);
}else if(q->bf > 0){
RotateL(parent);
}else{
RotateRL(parent);
}
}else{
q = parent->leftChild;
if(q->bf == 0){
RotateR(parent);
}else if(q->bf < 0){
RotateR(parent);
}else{
RotateLR(parent);
}
}
}
}
if(st.empty()){
t = parent; //直接更改root
}else{
AVLNode<Type> *tmp = st.top(); //當前的棧頂結點使其的左/右指向parent(是旋轉化后的根);
if(parent->data < tmp->data){
tmp->leftChild = parent;
}else{
tmp->rightChild = parent;
}
}
}
delete p; //刪除結點;
return true;
}3、完整代碼、測試代碼、測試結果
(1)完整代碼
#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_
#include<iostream> //引入頭文件
#include<stack> //要用棧保存路徑信息
using namespace std;
template<typename Type>
class AVLTree;
template<typename Type>
class AVLNode{ //AVL樹的結點
friend class AVLTree<Type>;
public:
AVLNode() : data(Type()), leftChild(NULL), rightChild(NULL), bf(0){}
AVLNode(Type d, AVLNode *left = NULL, AVLNode *right = NULL)
: data(d), leftChild(left), rightChild(right), bf(0){}
~AVLNode(){}
private:
Type data;
AVLNode *leftChild;
AVLNode *rightChild;
int bf; //多了一個平衡因子
};
template<typename Type>
class AVLTree{ //AVL樹的類型
public:
AVLTree() : root(NULL){}
public:
bool insert(const Type &x){
return insert(root, x);
}
bool remove(const Type &x){
return remove(root, x);
}
void inOrder()const{
inOrder(root);
}
protected:
void inOrder(AVLNode<Type> *t)const{
if(t != NULL){
inOrder(t->leftChild);
cout<<t->data<<" : "<<t->bf<<endl;;
inOrder(t->rightChild);
}
}
bool insert(AVLNode<Type> *&t, const Type &x); //插入函數
bool remove(AVLNode<Type> *&t, const Type &x);
void RotateR(AVLNode<Type> *&ptr){ //右旋
AVLNode<Type> *subR = ptr;
ptr = ptr->leftChild;
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
ptr->bf = subR->bf = 0;
}
void RotateL(AVLNode<Type> *&ptr){ //左旋
AVLNode<Type> *subL = ptr;
ptr = subL->rightChild;
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
subL->bf = ptr->bf = 0;
}
void RotateLR(AVLNode<Type> *&ptr){ //先左后右旋轉
AVLNode<Type> *subR = ptr;
AVLNode<Type> *subL = ptr->leftChild;
ptr = subL->rightChild;
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
if(ptr->bf <= 0){
subL->bf = 0;
}else{
subL->bf = -1;
}
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
if(ptr->bf == -1){
subR->bf = 1;
}else{
subR->bf = 0;
}
ptr->bf = 0;
}
void RotateRL(AVLNode<Type> *&ptr){ //先右后左旋轉
AVLNode<Type> *subL = ptr;
AVLNode<Type> *subR = ptr->rightChild;
ptr = subR->leftChild;
subR->leftChild = ptr->rightChild;
ptr->rightChild = subR;
if(ptr->bf >=0){
subR->bf = 0;
}else{
subR->bf = 1;
}
subL->rightChild = ptr->leftChild;
ptr->leftChild = subL;
if(ptr->bf == 1){
subL->bf = -1;
}else{
subL->bf = 0;
}
ptr->bf = 0;
}
private:
AVLNode<Type> *root;
};
template<typename Type>
bool AVLTree<Type>::insert(AVLNode<Type> *&t, const Type &x){
AVLNode<Type> *p = t;
AVLNode<Type> *parent = NULL; // 記錄前驅結點，方便連接和調整平衡因子
stack<AVLNode<Type> *> st; //用棧記錄插入的路徑，方便調整棧中結點的平衡因子;
int sign;
while(p != NULL){
if(x == p->data){ //要插入的數據和AVL樹中的數字相同,則返回失敗！
return false;
}
parent = p;
st.push(parent); //找過的入棧
if(x < p->data){
p = p->leftChild;
}else if(x > p->data){
p = p->rightChild;
}
} // 找插入位置,不用遞歸，就是為了記錄路徑信息
p = new AVLNode<Type>(x);
if(parent == NULL){
t = p; //判斷是不是第一個結點，進行root的連接;
return true;
}
if(x < parent->data){ //此時通過父節點的數據判斷插入的是左還是右
parent->leftChild = p;
}else{
parent->rightChild = p;
}
//新插入點的bf為0,關鍵是棧中的平衡因子的調整
/////////////////////////////////////////////////////// 以上完成插入工作
while(!st.empty()){ //棧不空，出棧頂元素
parent = st.top();
st.pop();
if(p == parent->leftChild){ //判斷插入的是父節點的左/右孩子,
parent->bf--; //讓其bf++/--;
}else{
parent->bf++;
}
//以下判斷棧中的平衡因子，看是否需要進行旋轉調整
if(parent->bf == 0){ //bf=0，直接跳出循環
break;
}
if(parent->bf==1 || parent->bf==-1){
p = parent; //此時在向上走，判斷bf;
}else{ //以下的bf為2/-2;利用標志判斷左右旋;
sign = parent->bf > 0 ? 1 : -1;
if(p->bf == sign){ //符號相同為單旋
if(sign == 1){ //為1左旋
RotateL(parent);
}else{
RotateR(parent); //右旋
}
}else{ //符號不同，為雙旋
if(sign == 1){
RotateRL(parent); //為1右左
}else{
RotateLR(parent);
}
}
/*
以下方法也可以判斷左右旋
else
{
if(parent->bf < 0) //左邊
{
if(p->bf<0 && p==parent->leftChild) // / 只能是左孩子
{
//RotateR(parent);
}
else if(p->bf>0 && p == parent->leftChild) // <
{
//RotateLR(parent);
}
}
else
{
if(p->bf>0 && p==parent->rightChild) // \
{
//RotateL(parent);
}
else if(p->pf<0 && p==parent->rightChild) // >
{
//RotateRL(parent);
}
}
}
*/
break;
}
}
if(st.empty()){ //通過旋轉函數，此時parent指向根節點;
t = parent; //此時調到棧底了，旋轉后將更改root的指向
}else{
AVLNode<Type> *tmp = st.top(); //當前的棧頂結點
if(parent->data < tmp->data){
tmp->leftChild = parent;
}else{
tmp->rightChild = parent;
}
}
return true;
}
template<typename Type>
bool AVLTree<Type>::remove(AVLNode<Type> *&t, const Type &x){
AVLNode<Type> *p = t;
AVLNode<Type> *parent = NULL; //父結點
AVLNode<Type> *q = NULL; //刪除結點的輔助結點
stack<AVLNode<Type> *> st;
AVLNode<Type> *ppr; //爺爺結點
int flag = 0;
while(p != NULL){
if(p->data == x){
break;
}
parent = p;
st.push(parent);
if(x < p->data){
p = p->leftChild;
}else{
p = p->rightChild;
}
} //以上是：查找刪除點
if(p == NULL){ //沒有要刪除的結點
return false;
}
if(p->leftChild!= NULL && p->rightChild!=NULL){
parent = p;
st.push(parent);
q = p->leftChild;
while(q->rightChild != NULL){
parent = q;
st.push(parent);
q = q->rightChild;
}
p->data = q->data;
p = q;
}
if(p->leftChild != NULL){
q = p->leftChild;
}else{
q = p->rightChild;
}
//以上是：使其要刪除的轉化為只有一個分支的
if(parent == NULL){ //刪除的是根結點，并且無入棧，代表只有一個分支，并沒有尋找
t = q;
}else{
if(parent->leftChild == p){
flag = 0;
parent->leftChild = q;
}else{
flag = 1;
parent->rightChild = q;
}
while(!st.empty()){
parent = st.top();
st.pop();
if(parent->leftChild==q){ //對要刪除的父節點更改bf;
parent->bf++;
}else{
parent->bf--;
}
if(!st.empty()){
ppr = st.top();
if(ppr->leftChild == parent){
flag = 0;
}else{
flag = 1;
}
}
if(parent->bf==-1 || parent->bf==1 ){
break; //刪除前的平衡因子為0，此時不用再調整其它平衡因子
}
if(parent->bf == 0){ //原先只有左孩子/右孩子
q = parent; //往上回溯更改爺爺結點的bf；
}else{ //此時到達2,已經不平衡了，的進行旋轉化的調整
if(parent->bf < 0){
flag = -1;
q = parent->leftChild;
}else{
flag = 1;
q = parent->rightChild;
}
if(q->bf == 0){
if(flag == -1){
}
}
if(parent->bf > 0){
q = parent->rightChild;
if(q->bf == 0){
RotateL(parent);
}else if(q->bf > 0){
RotateL(parent);
}else{
RotateRL(parent);
}
}else{
q = parent->leftChild;
if(q->bf == 0){
RotateR(parent);
}else if(q->bf < 0){
RotateR(parent);
}else{
RotateLR(parent);
}
}
}
}
if(st.empty()){
t = parent; //直接更改root
}else{
AVLNode<Type> *tmp = st.top(); //當前的棧頂結點使其的左/右指向parent(是旋轉化后的根);
if(parent->data < tmp->data){
tmp->leftChild = parent;
}else{
tmp->rightChild = parent;
}
}
}
delete p; //刪除結點;
return true;
}
#endif(2)、測試代碼
#include"avlTree.h"
int main(void){
int ar[] = {16, 3, 7, 11, 9, 26, 18, 14, 15,};
int n = sizeof(ar) / sizeof(int);
AVLTree<int> avl;
for(int i = 0; i < n; i++){
avl.insert(ar[i]);
}
cout<<"刪除前: "<<endl;
avl.inOrder();
avl.remove(16);
cout<<"刪除后: "<<endl;
avl.inOrder();
return 0;
}(3)、測試結果
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
