數據結構學習-AVL平衡樹

来源:https://www.cnblogs.com/cyrio/archive/2018/12/16/10125546.html
-Advertisement-
Play Games

環境：C++ 11 + win10 IDE：Clion 2018.3 AVL平衡樹是在BST二叉查找樹的基礎上添加了平衡機制。 我們把平衡的BST認為是任一節點的左子樹和右子樹的高度差為-1,0,1中的一種情況，即不存在相差兩層及以上。 所謂平衡機制就是BST在理想情況下搜索複雜度是o(logn) ...


環境：C++ 11 + win10

IDE：Clion 2018.3

AVL平衡樹是在BST二叉查找樹的基礎上添加了平衡機制。

我們把平衡的BST認為是任一節點的左子樹和右子樹的高度差為-1,0,1中的一種情況，即不存在相差兩層及以上。

所謂平衡機制就是BST在理想情況下搜索複雜度是o(logn)

但是如果在（存在某一節點，該節點的左子樹的高度與右子樹的高度差>1）這種狀況下，複雜度會超過o(logn)

舉個極端的例子如加入1,2,3,4，BST就退化為一個線性的鏈表，複雜度變成了o(n)

為了避免這種情況，我們在BST中引入平衡操作（旋轉操作），使得BST始終不存在左右子樹超過1高度差的節點。

本次代碼基於我的另一篇博客的基礎之上，有需要可以翻看 https://www.cnblogs.com/cyrio/p/10118132.html

平衡機制主要通過反轉完成，經過歸納，可能出現以下四種不平衡的情況：LL、LR、RL、RR

L=left     R=right

我們將不平衡點設為X點，以LR為例，第一個L表示X點的左子樹比右子樹層數多（>1），第二個R表示多出的那部分在X點的左子樹的右子樹。（不管他是在X的左子樹的右子樹的左右哪邊，都稱為LR）

 

如圖：

 

 接下來我們以LL、LR、RR、RL四種情況討論。

1、LL：

通俗的講就是把K2從K1那扯下來，然後把Y移到K2的左子樹，最後把K2移到K1的右子樹。

2、RR：

與LL同理，把K1先扯下來，再把Y接到K1的右側，再把K1作為左子樹接到K2。

 3、LR：

LR需要先做一次RR再做一次LL：

先把K1從K2那扯下來，讓K2和K3連，然後把B作為K1的右子樹，再把K1連到K2的左子樹上。

然後再做LL，把K3從K2上面扯下來，讓C作為K3的左子樹，再把K3連到K2的右子樹。

4、RL：

先LL再RR，與LR同理。

以上是主要思想的分析，除了旋轉操作，我們還需要添加新的方法：

1、求樹的高度：height方法

2、求某節點的左子樹和右子樹的高度差 ：Diff方法      

3、一個對整個樹進行判斷，對裡面的X節點進行對應操作：Balance方法

同時AVL中的Insert（插入某一節點）的方法與BST中也略有不同，需要註意的是AVL種的__Insert（PS：帶"__"的表示私有內部介面）的參數中第一個為bstNode<T> * & root （需要&引用）

具體代碼如下：（此代碼為完整代碼，可以直接複製進自己的項目查看效果）

myBST.h

#ifndef TEST1_MYBST_H
#define TEST1_MYBST_H

#include <iomanip>
#include "bstNode.h"
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;

template <typename T>
class myBST{
private:
    bstNode<T> * root = nullptr;
    bstNode<T> * __search(bstNode<T> * root , const T &key){
        if (nullptr == root)
            return nullptr;
        if (key == root->data)
            return root;
        else if (key < root->data)
            return __search(root->left, key);
        else
            return __search(root->right, key);
    } //查找關鍵字是否存在
    bstNode<T> * __treeMin(bstNode<T> * root , bstNode<T> * &parent){
        bstNode<T> * curr = root;
        while(curr->left!= nullptr){
            parent = curr;
            curr = curr->left;
        }
        return  curr;
    } //返回最小節點（一路向左）
    bstNode<T> * __Insert(bstNode<T> * &root, const T &key){
        if (nullptr == root)
        {
            root = new bstNode<T>(key);
            return root;
        }//遞歸返回條件
        else if (key < root->data)
        {
            root->left = __Insert(root->left,key);//遞歸左子樹
            //balance operation
            root = __Balance(root);//平衡操作包含了四種旋轉
        }
        else if (key>root->data)
        {
            root->right = __Insert(root->right,key);//遞歸右子樹
            //balance operation
            root = __Balance(root);//平衡操作包含了四種旋轉
        }
        return root;
    } //插入指定值
    bool __Delete(const T &key){
        bool found = false;//存儲有沒有找到key的變數
        if(isEmpty()){
            cerr<<"BST為空"<<endl;
            return false;
        }
        bstNode<T> * curr = root;
        bstNode<T> * parrent = nullptr;
        while(curr!= nullptr) {
            if (key == curr->data) {
                found = true;
                break;
            } else {
                parrent = curr;
                if (key < curr->data) curr = curr->left;
                else curr = curr->right;
            }
        }
        if(!found){
            cerr<<"未找到key！"<<endl;
            return false;
        }
        if (parrent == nullptr){//刪除根節點
            root = nullptr;
            delete(curr);
            return true;
        }
        /*
         刪除的節點有三種可能：
         1、葉子結點
         2、一個孩子的節點
         3、兩個孩子的節點
         */
        if (__isLeaf(curr)){ //刪除的點是葉子結點
            if(parrent->left==curr) parrent->left= nullptr;
            else parrent->right= nullptr;
            delete(curr);
            return true;
        }
        else if(__isNodeWithTwoChild(curr)){ //是兩個孩子的節點
            //以當前右子樹中的最小值取代他
            bstNode<T> * parrent = curr;
            bstNode<T> * tmp = __treeMin(curr->right,parrent);
            curr->data = tmp->data;
            if(parrent->right==tmp)
                parrent->right== nullptr;
            else parrent->left== nullptr;
            delete(tmp);
            return true;
        }
        else{ //只有一個孩子的節點
            if(curr->left!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
            if(curr->right!= nullptr){
                if(curr->left == curr){
                    parrent->left=curr->left;
                    delete(curr);
                    return true;
                }
                else{
                    parrent->right=curr->right;
                    delete(curr);
                    return true;
                }
            }
        }
        return false;
    } //刪除指定值
    bool __isLeaf(bstNode<T> * const & root){
        if(root->left== nullptr && root->right== nullptr) return true;
        else return false;
    }//判斷是否是葉子節點
    bool __isNodeWithTwoChild(bstNode<T> * const & root){
        if(root->left!= nullptr && root->right!= nullptr) return true;
        else return false;
    }//判斷是否有兩個孩子
    void __InorderTraversal(bstNode<T> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __InorderTraversal(root->left,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
        __InorderTraversal(root->right,result);
    }//中序遍歷
    void __PreorderTraversal(bstNode<T> *root,std::vector<int>&result){
        if(nullptr == root) return;
        cout<<root->data<<" ";
        result.push_back(root->data);
        __InorderTraversal(root->left,result);
        __InorderTraversal(root->right,result);
    }//前序遍歷
    void __PostorderTraversal(bstNode<T> *root,std::vector<int>&result){
        if(nullptr == root) return;
        __InorderTraversal(root->left,result);
        __InorderTraversal(root->right,result);
        cout<<root->data<<" ";
        result.push_back(root->data);
    }//後序遍歷
    void __DeleteAllNodes(bstNode<T> *root){
        if (root == nullptr) return;
        __DeleteAllNodes(root->left);
        __DeleteAllNodes(root->right);
        __Delete(root->data);
    }//刪除所有節點
    void __BFTraversal(vector<T>&result) {
        deque<bstNode<T> *> TQueue;
        bstNode<T> *pointer = root;
        if (pointer != nullptr) {
            TQueue.push_back(pointer);
        }
        while (!TQueue.empty()) {
            pointer = TQueue.front();
            TQueue.pop_front();
            cout << pointer->data << " ";
            result.push_back(pointer->data);
            if (pointer->left != nullptr) TQueue.push_back(pointer->left);
            if (pointer->right != nullptr) TQueue.push_back(pointer->right);
        }
    } //廣度搜索來進行周游
    void __Graph(int indent,bstNode<T>* root){
        if(root != 0){
            __Graph(indent + 8, root->right);
            cout<<setw(indent)<<" "<<root->data<<endl;
            __Graph(indent + 8, root->left);
        }
    } //橫著畫圖的內部介面
    bstNode<T> * __GetRoot(){
        return root;
    } //返回根節點的內部介面
    //以下為AVL平衡樹新加的方法
    int __height(const bstNode<T>* root){
        if(root == nullptr){
            return 0;
        }
        return max(__height(root->left),__height(root->right))+1;
    } //求樹的高度
    int __diff(const bstNode<T>* root){
        return __height(root->left)-__height(root->right);
    } //求節點的高度差（平衡因數）
    bstNode<T> * __ll__Rotation(bstNode<T> * root){
        bstNode<T> * tmp;
        tmp = root->left;
        root->left = tmp->right;
        tmp->right = root;
        return tmp;
    } //單旋轉-左左
    bstNode<T> * __rr__Rotation(bstNode<T> * root){
        bstNode<T> * tmp;
        tmp = root->right;
        root->right = tmp->left;
        tmp->left = root;
        return tmp;
    } //單旋轉-右右
    bstNode<T> * __lr__Rotation(bstNode<T> * root){
        bstNode<T> * tmp;
        tmp = root->left;
        root->left = __rr__Rotation(tmp);
        return __ll__Rotation(root);
    } //雙旋轉-左右型，先右後左轉（註意此處相反）
    bstNode<T> * __rl__Rotation(bstNode<T> * root){
        bstNode<T> * tmp;
        tmp = root->right;
        root->right = __ll__Rotation(tmp);
        return __rr__Rotation(root);
    } //雙旋轉-右左型，先左後右轉
    bstNode<T> * __Balance(bstNode<T> * root){
        int balanceFactor = __diff(root);//__diff用來計算平衡因數（左右子樹高度差）
        if (balanceFactor > 1)//左子樹高於右子樹
        {
            if (__diff(root->left) > 0)//左左外側
                root=__ll__Rotation(root);
            else//左右內側
                root=__lr__Rotation(root);
        }
        else if (balanceFactor < -1)//右子樹高於左子樹
        {
            if (__diff(root->right) > 0)//右左內側
                root=__rl__Rotation(root);
            else//右右外側
                root=__rr__Rotation(root);
        }
        return root;
    } //平衡的內部操作
public:
    myBST(){
        root = nullptr;
    } //預設構造
    myBST(vector<T> arr){
        root = nullptr;
        for(int i =0;i<(T)arr.size();i++){
            Insert(arr[i]);
        }
    }
    myBST(T * arr,int len){
        root = nullptr;
        for(int i =0;i<len;i++){
            __Insert(*(arr+i));
        }
    }
    ~myBST(){
        bstNode<T> * curr = root;
        __DeleteAllNodes(curr);
    }//析構
    bool isEmpty() const{
        return root == nullptr;
    }//判斷樹空
    bool search(const T &key){
        bstNode<T> * temp = __search(root, key);
        return (temp == nullptr) ? false : true;
    }//查找關鍵字是否存在的對外介面
    bool Insert(const T &key){
        return __Insert(root,key);
    }//插入節點的外部介面
    bool Delete(const T &key){
        return __Delete(key);
    }//刪除節點的外部介面
    void InorderTraversal(vector<T>&result){
        __InorderTraversal(root, result);
    }//中序遍歷的外部介面
    void PreorderTraversal(vector<T>&result){
        __PreorderTraversal(root, result);
    }//前序遍歷的外部介面
    void PostorderTraversal(vector<T>&result){
        __PostorderTraversal(root, result);
    }//後序遍歷的外部介面
    void BFTraversal(vector<T>&result){
        return __BFTraversal(result);
    } //廣度搜索外部介面
    void Graph(int indent,bstNode<T>* root){
        return __Graph(indent,root);
    } //橫著畫圖的外部介面
    bstNode<T> * GetRoot(){
        return __GetRoot();
    } //返回根節點的外部介面
};

#endif //TEST1_MYBST_H

bstNode.h

#ifndef TEST1_BSTNODE_H
#define TEST1_BSTNODE_H
template <typename T>
class bstNode{
public:
    T data;
    bstNode* left;
    bstNode* right;
    bstNode(){
        data = 0;
        left = nullptr;
        right = nullptr;
    }
    bstNode(T val){
        data = val;
        left = nullptr;
        right = nullptr;
    }
};
#endif //TEST1_BSTNODE_H

main.cpp

#include <iostream>
#include <vector>
#include "myBST.h"
#include "bstNode.h"
using namespace std;
int main() {
    vector<int> in = {7,6,5,13,17,22,10,3,2,1};
    myBST<int> bst(in);
    bst.Delete(5);
    bst.Insert(4);
    bool found = bst.search(4);
    if(!found)
        cout<<"not found!"<<endl;
    else
        cout<<"found!"<<endl;
    vector<int> result;
    cout<<"InorderTravelsal:  ";
    bst.InorderTraversal(result);
    cout<<endl<<"PreorderTravelsal:  ";
    bst.PreorderTraversal(result);
    cout<<endl<<"PostorderTraversal:  ";
    bst.PostorderTraversal(result);
    cout<<endl<<"BFTraversal:  ";
    bst.BFTraversal(result);
    cout<<endl<<"Graph:"<<endl;
    bstNode<int>* pointer = bst.GetRoot();
    bst.Graph(0,pointer);
    return 0;
}

 

參考：https://blog.csdn.net/zhangxiao93/article/details/51459743


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 網路協議中HTTP,TCP,UDP,Socket,WebSocket的優缺點/區別
    先說一下網路的層級：由下往上分為 物理層、數據鏈路層、網路層、傳輸層、會話層、表示層和應用層 1、TCP和UDP TCP：是面向連接的一種傳輸控制協議。屬於傳輸層協議。TCP連接之後，客戶端和伺服器可以互相發送和接收消息，在客戶端或者伺服器沒有主動斷開之前，連接一直存在屬於長連接。 優點：安全、傳輸 ...
  • 基於WebGL架構的3D可視化平臺ThingJS-搭建設備管理系統
    國內高層建築不斷興建，它的特點是高度高、層數多、體量大。面積可達幾萬平方米到幾十萬平方米。這些建築都是一個個龐然大物，高高的聳立在地面上，這是它的外觀，而隨之帶來的內部的建築設備也是大量的。為了提高設備利用率，合理地使用能源，加強對建築設備狀態的監視等，自然地就提出了樓宇自動化控制系統。下麵我們將用 ...
  • Bootstrap -- 插件: 模態框、滾動監聽、標簽頁
    Bootstrap -- 插件: 模態框、滾動監聽、標簽頁 1. 模態框（Modal）: 覆蓋在父窗體上的子窗體。 使用模態框： <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/html; cha ...
  • 每天一個設計模式之組合模式
    作者按：《每天一個設計模式》旨在初步領會設計模式的精髓，目前採用 和`python`兩種語言實現。誠然，每種設計模式都有多種實現方式，但此小冊只記錄最直截了當的實現方式 :) 原文地址是： "《每天一個設計模式之組合模式》" 歡迎關註個人技術博客： "godbmw.com" 。每周 1 篇原創技術分 ...
  • 設計模式系列 - 橋接模式
    使用橋接模式可以將類型的抽象和具體實現進行分離，兩者通過橋接模式進行關聯，從而達到解耦 介紹 橋接模式屬於結構型模式。在現實世界中，我們裝修房子時，佈線的工人和安裝空調的工人之間可以同時工作，不用互相依賴。而對於屋主人來講也不用關係他們具體時怎麼工作的，只需要等他們完成即可。在軟體開發中，當我們面對 ...
  • Java建造者模式
    建造者模式 建造者模式適用場景： 建造一個複雜的對象適用，將構建對象的過程分開，每個類單獨構造對象的一部分，最後組裝起來，返回我們需要的對象。 下麵的例子主要講解構造一個飛船 Demo： //要獲得的對象，但是各個組件要拆分開，讓對應的類去實現 class AirShip { private Orb ...
  • 設計模式系列 - 適配器模式
    見名知其意，適配器可用於對多個不相容介面提供適配橋梁 介紹 適配器模式屬於結構型模式。在現實世界中，這個模式適用的較為廣泛，比如 DIY 一些電子產品，主要元器件提供的是標準介面，那麼無論我們購買什麼品牌的元器件，最終都能組裝起來正常運行。 類圖描述 由上圖可知，我們通過定義 IAdvancedMe ...
  • 設計模式7大原則
    面向對象設計原則 概述 對於面向對象軟體系統的設計而言，在支持可維護性的同時，提高系統的可復用性是一個至關重要的問題，如何同時提高一個軟體系統的可維護性和可復用性是面向對象設計需要解決的核心問題之一。在面向對象設計中，可維護性的復用是以設計原則為基礎的。每一個原則都蘊含一些面向對象設計的思想，可以從 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類