欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)AVL樹(shù)的示例詳解

 更新時(shí)間:2023年03月03日 11:22:17   作者:叫我小秦就好了  
AVL Tree 是一個(gè)「加上了額外平衡條件」的二叉搜索樹(shù),其平衡條件的建立是為了確保整棵樹(shù)的深度為O(log_2N),本文主要介紹了AVL樹(shù)的實(shí)現(xiàn),需要的可以參考一下

AVL 樹(shù)的概念

也許因?yàn)椴迦氲闹挡粔螂S機(jī),也許因?yàn)榻?jīng)過(guò)某些插入或刪除操作,二叉搜索樹(shù)可能會(huì)失去平衡,甚至可能退化為單鏈表,造成搜索效率低。

AVL Tree 是一個(gè)「加上了額外平衡條件」的二叉搜索樹(shù),其平衡條件的建立是為了確保整棵樹(shù)的深度為 O(log2N)。

AVL Tree 要求任何節(jié)點(diǎn)的左右子樹(shù)高度相差最多為 1。當(dāng)違反該規(guī)定時(shí),就需要進(jìn)行旋轉(zhuǎn)來(lái)保證該規(guī)定。

AVL 樹(shù)的實(shí)現(xiàn)

節(jié)點(diǎn)的定義

AVL 樹(shù)節(jié)點(diǎn)的定義比一般的二叉搜索樹(shù)復(fù)雜,它需要額外一個(gè) parent 指針,方便后續(xù)旋轉(zhuǎn)。并在每個(gè)節(jié)點(diǎn)中引入平衡因子,便于判斷是否需要旋轉(zhuǎn)。

/// @brief AVL 樹(shù)節(jié)點(diǎn)結(jié)構(gòu)
/// @tparam K 節(jié)點(diǎn)的 key 值
/// @tparam V 節(jié)點(diǎn)的 value 值
template <class K, class V>
struct AVLTreeNode {
	AVLTreeNode(const pair<K, V>& kv) 
		: _kv(kv)
		, _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _bf(0)
	{}

	pair<K, V> _kv;
	AVLTreeNode<K, V>* _parent;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
    // 左右子樹(shù)高度相同平衡因子為:0
    // 左子樹(shù)高平衡因子為負(fù)
    // 右子樹(shù)高平衡因子為正
	int _bf;
};

接口總覽

template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;
public:
	Node* Find(const K& key);
	bool Insert(const pair<K, V>& kv);

private:
	void RotateR(Node* parent);
	void RotateL(Node* parent);
	void RotateLR(Node* parent);
	void RotateRL(Node* parent);
private:
	Node* _root = nullptr;
};

查找

AVL 樹(shù)的查找和普通的搜索二叉樹(shù)一樣:

  • 若 key 值大于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的右子樹(shù)中查找
  • 若 key 值小于當(dāng)前節(jié)點(diǎn)的值,在當(dāng)前節(jié)點(diǎn)的左子樹(shù)中查找
  • 若 key 值等于當(dāng)前節(jié)點(diǎn)的值,返回當(dāng)前節(jié)點(diǎn)的地址
  • 若找到空,查找失敗,返回空指針
/// @brief 查找指定 key 值
/// @param key 要查找的 key
/// @return 找到返回節(jié)點(diǎn)的指針,沒(méi)找到返回空指針
Node* Find(const K& key) {
    Node* cur = _root;
    while (cur != nullptr) {
        // key 值與當(dāng)前節(jié)點(diǎn)值比較
        if (key > cur->_kv.first) {
            cur = cur->_right;
        } else if (key < cur->_kv.first) {
            cur = cur->_left;
        } else {
            return cur;
        }
    }
    return nullptr;
}

插入

AVL 的插入整體分為兩步:

  • 按照二叉搜索樹(shù)的方式將節(jié)點(diǎn)插入
  • 調(diào)整節(jié)點(diǎn)的平衡因子

平衡因子是怎么調(diào)整的?

設(shè)新插入的節(jié)點(diǎn)為 pCur,新插入節(jié)點(diǎn)的父節(jié)點(diǎn)為 pParent。在插入之前,pParent 的平衡因子有三種可能:0、-1、1。

插入分為兩種:

  • pCur 插入到 pParent 的左側(cè),將 pParent 的平衡因子減 1
  • pCur 插入到 pParent 的右側(cè),將 pParent 的平衡因子加 1

此時(shí),pParent 的平衡因子可能有三種情況:0、正負(fù) 1、正負(fù) 2。

  • 0:說(shuō)明插入之前是正負(fù) 1,插入后被調(diào)整為 0,滿足 AVL 性質(zhì)插入成功
  • 正負(fù) 1:說(shuō)明插入之前是 0,插入后被調(diào)整為正負(fù) 1,此時(shí) pParent 變高,需要繼續(xù)向上更新
  • 正負(fù) 2:說(shuō)明插入之前是正負(fù) 1,插入后被調(diào)整為正負(fù) 2,此時(shí)破壞了規(guī)定,需要旋轉(zhuǎn)處理
/// @brief 插入指定節(jié)點(diǎn)
/// @param kv 待插入的節(jié)點(diǎn)
/// @return 插入成功返回 true,失敗返回 false
bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }

    // 先找到要插入的位置
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur != nullptr) {
        if (kv.first > cur->_kv.first) {
            parent = cur;
            cur = cur->_right;
        } else if (kv.first < cur->_kv.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 已經(jīng)存在,插入失敗
            return false;
        }
    }

    // 將節(jié)點(diǎn)插入
    cur = new Node(kv);
    if (kv.first > parent->_kv.first) {
        parent->_right = cur;
        cur->_parent = parent;
    } else {
        parent->_left = cur;
        cur->_parent = parent;
    }

    // 更新平衡因子,直到正常
    while (parent != nullptr) {
        // 調(diào)整父親的平衡因子
        if (parent->_left == cur) {
            --parent->_bf;
        } else {
            ++parent->_bf;
        }

        if (parent->_bf == 0) {
            // 此時(shí)不需要再繼續(xù)調(diào)整了,直接退出
            break;
        } else if (parent->_bf == 1 || parent->_bf == -1) {
            // 此時(shí)需要繼續(xù)向上調(diào)整
            cur = parent;
            parent = parent->_parent;
        } else if (parent->_bf == 2 || parent->_bf == -2) {
            // 此時(shí)需要旋轉(zhuǎn)處理
            if (parent->_bf == -2 && cur->_bf == -1) {
                RotateR(parent);
            } else if (parent->_bf == 2 && cur->_bf == 1) {
                RotateL(parent);
            } else if (parent->_bf == -2 && cur->_bf == 1) {
                RotateLR(parent);
            } else if (parent->_bf == 2 && cur->_bf == -1) {
                RotateRL(parent);
            } else {
                assert(false);
            }
            // 旋轉(zhuǎn)完了就平衡了,直接退出
            break;
        } else {
            // 此時(shí)說(shuō)明之前就處理錯(cuò)了
            assert(false);
        } // end of if (parent->_bf == 0)
    } // end of while (parent != nullptr)
    return true;
}

旋轉(zhuǎn)

假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 X,由于節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn),因此可以分為四種情況:

  • 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的左子樹(shù)——左左:右單旋
  • 插入點(diǎn)位于 X 的左子節(jié)點(diǎn)的右子樹(shù)——左右:左右雙旋
  • 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的右子樹(shù)——右右:左單旋
  • 插入點(diǎn)位于 X 的右子節(jié)點(diǎn)的左子樹(shù)——右左:右左雙旋

右單旋

假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的左子樹(shù)為 subL,subL 的右子樹(shù)為 subLR。

右單旋的操作流程:

  • 讓 subLR 作為 parent 的左子樹(shù)
  • 讓 parent 作為 subL 的右子樹(shù)
  • 讓 subL 作為整個(gè)子樹(shù)的新根
  • 更新平衡因子
/// @brief 進(jìn)行右單旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateR(Node* parent) {
    Node* pParent = parent->_parent;
    Node* subL = parent->_left;
    Node* subLR = parent->_left->_right;

    // 更改鏈接關(guān)系
    // 1. subLR 作為 parent 的左子樹(shù)
    parent->_left = subLR;
    if (subLR != nullptr) {
        subLR->_parent = parent;
    }
    // 2. parent 作為 subL 的右子樹(shù)
    subL->_right = parent;
    parent->_parent = subL;

    // 3. subL 作為整個(gè)子樹(shù)的新根
    if (parent == _root) {
        // parent 為 _root,此時(shí)令 subL 為 _root
        _root = subL;
        subL->_parent = nullptr;
    } else {
        // parent 不為 _root,pParent 也就不為空
        if (parent == pParent->_left) {
            pParent->_left = subL;
        } else {
            pParent->_right = subL;
        }
        subL->_parent = pParent;
    }

    // 4. 更新平衡因子
    // 觀察上圖明顯可知
    subL->_bf = 0;
    parent->_bf = 0;
}

左單旋

左單旋與右單旋類似,只是方向不同。

假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的父節(jié)點(diǎn)為 pParent,parent 的右子樹(shù)為 subR,subR 的左子樹(shù)為 subRL。

左單旋的操作流程:

  • 讓 subRL 作為 parent 的右子樹(shù)
  • 讓 parent 作為 subR 的左子樹(shù)
  • 讓 subR 作為整個(gè)子樹(shù)的新根
  • 更新平衡因子
/// @brief 進(jìn)行左單旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateL(Node* parent) {
    Node* pParetn = parent->_parent;
    Node* subR = parent->_right;
    Node* subRL = parent->_right->_left;

    // 更改鏈接關(guān)系
    // 1. subRL 作為 parent 的右子樹(shù)
    parent->_right = subRL;
    if (subRL != nullptr) {
        subRL->_parent = parent;
    }
    // 2. parent 作為 subR 的左子樹(shù)
    subR->_left = parent;
    parent->_parent = subR;

    // 3. subR 作為整個(gè)子樹(shù)的新根
    if (parent == _root) {
        _root = subR;
        subR->_parent = nullptr;
    } else {
        if (parent == pParetn->_left) {
            pParetn->_left = subR;
        } else {
            pParetn->_right = subR;
        }
        subR->_parent = pParetn;
    }

    // 4. 更新平衡因子
    subR->_bf = 0;
    parent->_bf = 0;
}

左右雙旋

假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的左子樹(shù)為 subL,subL 的右子樹(shù)為 subLR。

左右雙旋就是對(duì) subL 進(jìn)行一次左單旋,對(duì) parent 進(jìn)行一次右單旋。雙旋也就完成了,要注意的是雙旋后平衡因子的更新。

此時(shí)分三種情況:

1.新插入的節(jié)點(diǎn)是 subLR 的右子樹(shù)

2.新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù)

3.新插入的是 subLR

結(jié)合上述情況,寫出如下代碼:

/// @brief 進(jìn)行左右雙旋
/// @param parent 平衡因子為正負(fù) 2 的節(jié)點(diǎn)
void RotateLR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = parent->_left->_right;
    int bf = subLR->_bf;

    RotateL(subL);
    RotateR(parent);

    if (bf == 1) {
        // 新插入節(jié)點(diǎn)是 subLR 的右子樹(shù)
        parent->_bf = 0;
        subL->_bf = -1;
        subLR->_bf = 0;
    } else if (bf == -1) {
        // 新插入的節(jié)點(diǎn)是 subLR 的左子樹(shù)
        parent->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
    } else if (bf == 0) {
        // 新插入的節(jié)點(diǎn)是 subLR
        parent->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    } else {
        assert(false);
    }
}

右左雙旋

假設(shè)平衡因子為正負(fù) 2 的節(jié)點(diǎn)為 parent,parent 的右子樹(shù)為 subR,subR 的左子樹(shù)為 subRL。

右左雙旋就是對(duì) subR 進(jìn)行一次右單旋,對(duì) parent 進(jìn)行一次左單旋。流程和左右雙旋一樣,這里就不過(guò)多介紹了。

void RotateRL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = parent->_right->_left;
    int bf = subRL->_bf;

    RotateR(subR);
    RotateL(parent);

    if (bf == 1) {
        // 新插入節(jié)點(diǎn)是 subRL 的右子樹(shù)
        parent->_bf = -1;
        subR->_bf = 0;
        subRL->_bf = 0;
    } else if (bf == -1) {
        // 新插入的節(jié)點(diǎn)是 subRL 的左子樹(shù)
        parent->_bf = 0;
        subR->_bf = 1;
        subRL->_bf = 0;
    } else if (bf == 0) {
        // 新插入的節(jié)點(diǎn)是 subRL
        parent->_bf = 0;
        subR->_bf = 0;
        subRL->_bf = 0;
    } else {
        assert(false);
    }
}

以上就是C++實(shí)現(xiàn)AVL樹(shù)的示例詳解的詳細(xì)內(nèi)容,更多關(guān)于C++ AVL樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評(píng)論