二叉樹（五）平衡二叉樹（AVL樹）

来源:https://www.cnblogs.com/teternity/archive/2020/02/05/AVLTree.html
-Advertisement-
Play Games

平衡二叉樹（AVL樹）的自平衡（LL->R、RR->L、LR->LR、RL->RL）、增、刪 等操作。 main.cpp： #include <iostream> #include "AVLTree.h" using namespace std; int main() { AVLTree<int> ...


平衡二叉樹（AVL樹）的自平衡（LL->R、RR->L、LR->LR、RL->RL）、增、刪 等操作。

 

 

main.cpp：

#include <iostream>
#include "AVLTree.h"
using namespace std;

int main()
{
    AVLTree<int> avl;

    auto Add = [&avl](int _key)
    {
        cout << "Add " << _key << ":" << endl;
        avl.insert(_key);
        avl.levelTraversal();
        cout << endl << "size: " << avl.size() << "  level: " << avl.level() << endl << endl;
    };
    auto il = { 0,1,4,2,5,3,6 };
    for (auto& key : il)
        Add(key);
    auto Del = [&avl](int _key)
    {
        cout << "Del " << _key << ":" << endl;
        avl.erase(_key);
        avl.levelTraversal();
        cout << endl << "size: " << avl.size() << "  level: " << avl.level() << endl << endl;
    };
    Del(4); Del(1); Del(5); Del(6); Del(2);

    return 0;
}

 

AVLTree.h：

#pragma once
#ifndef __AVLTREE_H__
#define __AVLTREE_H__


#include <queue>
#include <initializer_list>
template<typename _Ty>
class AVLTree
{
private:
    struct Node
    {
        _Ty key;
        int bf = 0;
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
        Node(const _Ty& _key) :key(_key) {}
    };

public:
    AVLTree() = default;
    template<typename _Iter>
    AVLTree(_Iter, _Iter);
    AVLTree(const std::initializer_list<_Ty>&);
    AVLTree(const AVLTree<_Ty>&);
    AVLTree(AVLTree<_Ty>&&) noexcept;

    ~AVLTree() { clear(root); }
    void clear() { clear(root); root = nullptr; }
    bool empty() const { return size_n == 0; }
    size_t size() const { return size_n; }
    Node* getRoot() const { return root; }
    void show() const { show(root); }
    void showPreorder() const { showPreorder(root); }
    void levelTraversal() const { levelTraversal(root); }
    size_t level() const;
    void swap(AVLTree<_Ty>&);

    void insert(const _Ty&);
    template<typename _Iter>
    void insert(_Iter, _Iter);
    size_t erase(const _Ty&);
    void erase(Node*);

    Node* find(const _Ty& _key) const { return find(root, _key); }
    Node* iterative_find(const _Ty& _key) const { return iterative_find(root, _key); }
    Node* maximum() const { return maximum(root); }
    Node* minimum() const { return minimum(root); }

private:
    void copy(Node*);
    void clear(Node*&);
    void show(Node*) const;
    void showPreorder(Node*) const;
    void levelTraversal(Node*) const;
    Node* find(Node*, const _Ty&) const;
    Node* iterative_find(Node*, const _Ty&) const;
    Node* maximum(Node*) const;
    Node* minimum(Node*) const;
    void LL_R(Node*);
    void RR_L(Node*);
    void LR_LR(Node*);
    void RL_RL(Node*);

private:
    size_t size_n = 0;
    Node* root = nullptr;
};

template<typename _Ty>
template<typename _Iter>
AVLTree<_Ty>::AVLTree(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(const std::initializer_list<_Ty>& _il)
{
    for (const auto& key : _il) insert(key);
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(const AVLTree<_Ty>& _right)
{
    copy(_right.getRoot());
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(AVLTree<_Ty>&& _right) noexcept
{
    root = _right.root;
    size_n = _right.size_n;
    _right.root = nullptr;
    _right.size_n = 0;
}

template<typename _Ty>
size_t AVLTree<_Ty>::level() const
{
    if (root == nullptr) 0;
    size_t n = 0;
    std::queue<Node*> nodePointers;
    nodePointers.push(root);
    while (!nodePointers.empty())
    {
        Node* levelBegin = nodePointers.front();
        Node* levelEnd = nodePointers.back();
        Node* cur = levelBegin;
        while (true)
        {
            if (cur->left != nullptr) nodePointers.push(cur->left);
            if (cur->right != nullptr) nodePointers.push(cur->right);
            if (cur == levelEnd)
                break;
            nodePointers.pop();
            cur = nodePointers.front();
        }
        nodePointers.pop();
        ++n;
    }
    return n;
}

template<typename _Ty>
void AVLTree<_Ty>::copy(Node* _node)
{
    if (_node == nullptr) return;
    insert(_node->key);
    copy(_node->left);
    copy(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::clear(Node*& _node)
{
    if (_node == nullptr) return;
    clear(_node->left);
    clear(_node->right);
    delete _node;
    _node = nullptr;
    --size_n;
}

template<typename _Ty>
void AVLTree<_Ty>::show(Node* _node) const
{
    if (_node == nullptr) return;
    show(_node->left);
    std::cout << _node->key << " ";
    show(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::showPreorder(Node* _node) const
{
    if (_node == nullptr) return;
    std::cout << _node->key << " ";
    show(_node->left);
    show(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::levelTraversal(Node* _node) const
{
    if (_node == nullptr) return;
    std::queue<Node*> nodePointers;
    nodePointers.push(_node);
    while (!nodePointers.empty())
    {
        Node* cur = nodePointers.front();
        std::cout << cur->key << " ";
        if (cur->left != nullptr) nodePointers.push(cur->left);
        if (cur->right != nullptr) nodePointers.push(cur->right);
        nodePointers.pop();
    }
}

template<typename _Ty>
void AVLTree<_Ty>::swap(AVLTree<_Ty>& _right)
{
    std::swap(root, _right->root);
    std::swap(size_n, _right->size_n);
}

template<typename _Ty>
void AVLTree<_Ty>::LL_R(Node* _root)
{
    Node* leftNode = _root->left;
    if (_root->parent != nullptr)
    {
        if (_root->parent->left == _root) _root->parent->left = leftNode;
        else _root->parent->right = leftNode;
    }
    else root = leftNode;
    leftNode->parent = _root->parent;
    _root->left = leftNode->right;
    if (leftNode->right != nullptr) leftNode->right->parent = _root;
    _root->parent = leftNode;
    leftNode->right = _root;
    _root->bf = leftNode->bf = 0;
}

template<typename _Ty>
void AVLTree<_Ty>::RR_L(Node* _root)
{
    Node* rightNode = _root->right;
    if (_root->parent != nullptr)
    {
        if (_root->parent->right == _root) _root->parent->right = rightNode;
        else _root->parent->left = rightNode;
    }
    else root = rightNode;
    rightNode->parent = _root->parent;
    _root->right = rightNode->left;
    if (rightNode->left != nullptr) rightNode->left->parent = _root;
    _root->parent = rightNode;
    rightNode->left = _root;
    _root->bf = rightNode->bf = 0;
}

template<typename _Ty>
void AVLTree<_Ty>::LR_LR(Node* _root)
{
    RR_L(_root->left);
    LL_R(_root);
    if (_root->left == nullptr) _root->bf = 1;
}

template<typename _Ty>
void AVLTree<_Ty>::RL_RL(Node* _root)
{

    LL_R(_root->right);
    RR_L(_root);
    if (_root->right == nullptr) _root->bf = -1;
}

template<typename _Ty>
void AVLTree<_Ty>::insert(const _Ty& _key)
{
    ++size_n;
    if (root == nullptr)
    {
        root = new Node(_key);
        return;
    }
    Node* temp = root;
    while (true)
    {
        if (_key == temp->key)
        {
            --size_n;
            return;
        }
        else if (_key < temp->key && temp->left != nullptr)
            temp = temp->left;
        else if (_key < temp->key && temp->left == nullptr)
            break;
        else if (_key > temp->key&& temp->right != nullptr)
            temp = temp->right;
        else
            break;
    }
    Node* newNode = new Node(_key);
    newNode->parent = temp;
    if (_key < temp->key)
    {
        temp->left = newNode;
        temp->bf += -1;
    }
    else
    {
        temp->right = newNode;
        temp->bf += 1;
    }
    if (temp->left != nullptr && temp->right != nullptr) return;
    Node* pa = temp->parent;
    while (pa != nullptr)
    {
        if (temp == pa->left)
            pa->bf += -1;
        else
            pa->bf += 1;
        if (pa->bf == -2)
        {
            if (temp->bf == -1) LL_R(pa);
            else LR_LR(pa);
            break;
        }
        else if (pa->bf == 2)
        {
            if (temp->bf == -1) RL_RL(pa);
            else RR_L(pa);
            break;
        }
        temp = pa;
        pa = pa->parent;
    }
}

template<typename _Ty>
template<typename _Iter>
void AVLTree<_Ty>::insert(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
size_t AVLTree<_Ty>::erase(const _Ty& _key)
{
    size_t n = 0;
    Node* del = find(_key);
    if (del != nullptr)
    {
        ++n;
        erase(del);
    }
    return n;
}

template<typename _Ty>
void AVLTree<_Ty>::erase(Node* _node)
{
    --size_n;
    Node* pa = nullptr;
    Node* temp = nullptr;
    if (_node->left == nullptr && _node->right == nullptr)
    {
        if (_node->parent == nullptr)
        {
            root = nullptr;
            delete _node;
            return;
        }
        if (_node == _node->parent->left)
        {
            _node->parent->left = nullptr;
            _node->parent->bf += 1;
            temp = _node->parent->right;
        }
        else
        {
            _node->parent->right = nullptr;
            _node->parent->bf += -1;
            temp = _node->parent->left;
        }
        pa = _node->parent;
        delete _node;
    }
    else if (!(_node->left != nullptr && _node->right != nullptr))
    {
        if (_node->parent == nullptr)
        {
            if (_node->left != nullptr) root = _node->left;
            else root = _node->right;
            root->parent = nullptr;
            delete _node;
            return;
        }
        if (_node == _node->parent->left)
        {
            _node->parent->left = _node->left == nullptr ? _node->right : _node->left;
            if (_node->left != nullptr) _node->left->parent = _node->parent;
            else _node->right->parent = _node->parent;
            _node->parent->bf += 1;
            temp = _node->parent->right;
        }
        else
        {
            _node->parent->right = _node->left == nullptr ? _node->right : _node->left;
            if (_node->left != nullptr) _node->left->parent = _node->parent;
            else _node->right->parent = _node->parent;
            _node->parent->bf += -1;
            temp = _node->parent->left;
        }
        pa = _node->parent;
        delete _node;
    }
    else
    {
        ++size_n;
        if (_node->right != nullptr)
        {
            Node* de = minimum(_node->right);
            _node->key = de->key;
            erase(de);
        }
        else if (_node->left != nullptr)
        {
            Node* de = maximum(_node->left);
            _node->key = de->key;
            erase(de);
        }
    }
    if (pa != nullptr && pa->bf == 0)
    {
        temp = pa;
        pa = pa->parent;
        if (pa != nullptr)
        {
            if (temp == pa->left)
            {
                temp = pa->right;
                pa->bf += 1;
            }
            else
            {
                temp = pa->left;
                pa->bf += -1;
            }
        }
    }
    while (pa != nullptr)
    {
        if (pa->bf == -2)
        {
            if (temp->bf == -1 || temp->bf == 0) LL_R(pa);
            else LR_LR(pa);
        }
        else if (pa->bf == 2)
        {
            if (temp->bf == -1) RL_RL(pa);
            else RR_L(pa);
        }
        else
            break;
        bool isLeft = temp == pa->left ? 1 : 0;
        pa = temp->parent;
        if (pa != nullptr)
        {
            if (isLeft)
            {
                temp = pa->left;
                pa->bf += -1;
            }
            else
            {
                temp = pa->right;
                pa->bf += 1;
            }
        }
    }
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::find(Node* _node, const _Ty& _key) const
{
    if (_node == nullptr || _node->key == _key)
        return _node;
    if (_key < _node->key)
        return find(_node->left, _key);
    else
        return find(_node->right, _key);
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::iterative_find(Node* _node, const _Ty& _key) const
{
    while (_node != nullptr && _node->key != _key)
    {
        if (_key < _node->key)
            _node = _node->left;
        else
            _node = _node->right;
    }
    return _node;
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::maximum(Node* _node) const
{

    if (_node == nullptr) return _node;
    while (_node->right != nullptr)
        _node = _node->right;
    return _node;
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::minimum(Node* _node) const
{
    if (_node == nullptr) return _node;
    while (_node->left != nullptr)
        _node = _node->left;
    return _node;
}


#endif // !__AVLTREE_H__

 


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

-Advertisement-
Play Games
更多相關文章
  • [Verilog] indexed part-select +:
    That syntax is called an indexed part-select. The first term is the bit offset and the second term is the width. It allows you to specify a variable f ...
  • django中添加日誌功能
    官方文檔 猛戳這裡 在settings中配置以下代碼 #LOGGING_DIR 日誌文件存放目錄 LOGGING_DIR = "logs" # 日誌存放路徑 if not os.path.exists(LOGGING_DIR): os.mkdir(LOGGING_DIR) import loggin ...
  • Python數據分析在互聯網寒冬下，數據分析師還吃香嗎？
    伴隨著移動互聯網的飛速發展，越來越多用戶被互聯網連接在一起，用戶所積累下來的數據越來越多，市場對數據方面人才的需求也越來越大，由此也帶火瞭如數據分析、數據挖掘、演算法等職業，而作為其中入門門檻相對較低、工資高於大多傳統行業崗位的數據分析一職，則成為了許多想轉行進入數據領域的同學的首要選擇。 那麼在現在 ...
  • JVM源碼分析-類載入場景實例分析
    A類調用B類的靜態方法，除了載入B類，但是B類的一個未被調用的方法間接使用到的C類卻也被載入了，這個有意思的場景來自一個提問： "方法中使用的類型為何在未調用時嘗試載入？" 。 場景如下： 添加JVM varbose參數進行執行，輸出是： main方法執行 ，而 方法裡面只有列印語句，所以理論上應該 ...
  • JVM源碼分析-JVM源碼編譯與調試
    要分析JVM的源碼，結合資料直接閱讀是一種方式，但是遇到一些想不通的場景，必須要結合調試，查看執行路徑以及參數具體的值，才能搞得明白。所以我們先來把JVM的源碼進行編譯，並能夠使用GDB進行調試。 編譯環境 本文使用的JDK版本：OpenJDK7，分支b147 下載頁面：https://downlo ...
  • 淺談python的第三方庫——numpy（三）
    numpy庫中矩陣的常用方法 1 矩陣轉置 從上圖可以看出：使用方法a.T可以將矩陣a轉置。 2 均值與方差 註意：方法a.mean()會對矩陣a的所有元素求均值，a.var()也是考慮矩陣a的所有元素求方差。 當然，也可以選取矩陣的某一行或某一列使用mean與var求均值與方差。 3 設置零矩陣 ...
  • java中棧記憶體與堆記憶體（JVM記憶體模型）
    java中棧記憶體與堆記憶體（JVM記憶體模型） Java中堆記憶體和棧記憶體詳解1 和 Java中堆記憶體和棧記憶體詳解2 都粗略講解了棧記憶體和堆記憶體的區別，以及代碼中哪些變數存儲在堆中、哪些存儲在棧中。記憶體中的堆和棧到底是什麼 詳細講述了程式在記憶體中的模型，從可執行文件（ELF）格式的編譯介紹了堆和棧，主要是... ...
  • 文件下載
    文件下載 1.開啟fileinfo擴展 2.fileinfo函數 finfo_open 創建一個fileinfo資源 finfo_close 關閉fileinfo資源 finfo_file 返回一個文件的信息 FILEINFO_MIME_TYPE 返回mime類型 FILEINFO_MIME_TYP ...
一周排行
    -Advertisement-
    Play Games
  • UOS 開啟 VisualStudio 遠程調試 .NET 應用之旅
    前言 在我們開發過程中基本上不可或缺的用到一些敏感機密數據，比如SQL伺服器的連接串或者是OAuth2的Secret等，這些敏感數據在代碼中是不太安全的，我們不應該在源代碼中存儲密碼和其他的敏感數據，一種推薦的方式是通過Asp.Net Core的機密管理器。 機密管理器 在 ASP.NET Core ...
  • C# - 能否讓 SortedSet.RemoveWhere 內傳入的委托非同步執行
    新改進提供的Taurus Rpc 功能，可以簡化微服務間的調用，同時可以不用再手動輸出模塊名稱，或調用路徑，包括負載均衡，這一切，由框架實現並提供了。新的Taurus Rpc 功能，將使得服務間的調用，更加輕鬆、簡約、高效。 ...
  • 順序棧的介面程式
    順序棧的介面程式 目錄順序棧的介面程式頭文件創建順序棧入棧出棧利用棧將10進位轉16進位數驗證 頭文件 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> 創建順序棧 // 指的是順序棧中的元素的數據類型，用戶可以根據需要進行修改 ...
  • mORMot2 獲取數據集1
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • 萬字長文總結與剖析C語言關鍵字 -- <<C語言深度解剖>>
    C總結與剖析:關鍵字篇 -- <<C語言深度解剖>> 目錄C總結與剖析:關鍵字篇 -- <<C語言深度解剖>>程式的本質:二進位文件變數1.變數:記憶體上的某個位置開闢的空間2.變數的初始化3.為什麼要有變數4.局部變數與全局變數5.變數的大小由類型決定6.任何一個變數,記憶體賦值都是從低地址開始往高地 ...
  • 【Flink入門修煉】2-3 Flink Checkpoint 原理機制
    如果讓你來做一個有狀態流式應用的故障恢復，你會如何來做呢？ 單機和多機會遇到什麼不同的問題？ Flink Checkpoint 是做什麼用的？原理是什麼？ ...
  • C++ 多級繼承與多重繼承：代碼組織與靈活性的平衡
    C++ 多級繼承 多級繼承是一種面向對象編程（OOP）特性，允許一個類從多個基類繼承屬性和方法。它使代碼更易於組織和維護，並促進代碼重用。 多級繼承的語法 在 C++ 中，使用 : 符號來指定繼承關係。多級繼承的語法如下： class DerivedClass : public BaseClass1 ...
  • 圖文結合手把手教你創建SpringCloud項目
    前言 什麼是SpringCloud？ Spring Cloud 是一系列框架的有序集合，它利用 Spring Boot 的開發便利性簡化了分散式系統的開發，比如服務註冊、服務發現、網關、路由、鏈路追蹤等。Spring Cloud 並不是重覆造輪子，而是將市面上開發得比較好的模塊集成進去，進行封裝，從 ...
  • 類模板的常見用法
    class_template 類模板和函數模板的定義和使用類似，我們已經進行了介紹。有時，有兩個或多個類，其功能是相同的，僅僅是數據類型不同。類模板用於實現類所需數據的類型參數化 template<class NameType, class AgeType> class Person { publi ...
  • system-v IPC共用記憶體通信
    目錄system v IPC簡介共用記憶體需要用到的函數介面shmget函數--獲取對象IDshmat函數--獲得映射空間shmctl函數--釋放資源共用記憶體實現思路註意 system v IPC簡介 消息隊列、共用記憶體和信號量統稱為system v IPC(進程間通信機制)，V是羅馬數字5，是UNI ...
所有分類