溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、AVL樹的插入
(1)、必須追蹤插入路徑，要對bf進行調整，此時不能用遞歸；
(2)、用棧保留路徑信息，每次插入均是以葉子結點插入的;
(3)、插入一個新結點，自身的bf不用調整，其初始化為0；要調整的是棧中的平衡因子，關鍵在雙旋時，平衡因子的調整要小心，還是調整棧中結點的平衡因子;
2、AVL樹的插入算法
思路：
(1)、按照二叉搜索樹的非遞歸實現插入數據；
(2)、 有一個父節點，記錄信息，并且入棧；
(3)、棧非空，出棧，判斷插入是左/右，此時給棧頂的結點平衡因子++/--，
(4)、判斷bf的值，進行不同情況的處理，針對bf不滿足平衡，將根據情況調用4個旋轉函數進行調整；
(5)、最后實行連接工作，看棧，空的話，直接給root，否則讀棧頂，比較數據大小，連接在左/右孩子;
均由C++實現：
要記住的是：棧中只保存的是插入結點的路徑，其余結點的信息不在保存；
如何判斷寫出要用4個旋轉函數，并且此時情形如何？
以上僅僅是一種情況，但是parent和p的指向我們已經理解了，其他的情形就可以看出來了;
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;
}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);
}
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); //插入函數
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;
}
#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]);
}
avl.inOrder();
return 0;
}(3)、測試結果
測試最終形成的AVL樹：
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
