AVL樹的C++實(shí)現(xiàn)
首先，AVL 樹是二叉查找樹，即任意一個(gè)節(jié)點(diǎn)的左子結(jié)點(diǎn)小于當(dāng)前結(jié)點(diǎn)，右子結(jié)點(diǎn)大于當(dāng)前結(jié)點(diǎn)。
然后，AVL 樹是平衡樹，任意一個(gè)結(jié)點(diǎn)的左子樹和右子樹高度差的絕對(duì)值小于等于 1。
定義
template <typename T>
class AVLTreeNode {
public:
T key;
int height = 1; //樹高
AVLTreeNode* l;
AVLTreeNode* r;
AVLTreeNode(T _key, AVLTreeNode* _l, AVLTreeNode* _r) : key(_key), l(_l), r(_r) {}
};
template <typename T>
class AVLTree {
public:
AVLTreeNode<T>* root;
AVLTree() { this->root = nullptr; }
~AVLTree();
int height(AVLTreeNode<T>* tree);
int height();
void insert(T key);
void remove(T key);
AVLTreeNode<T>* find(T key);
void print();
private:
AVLTreeNode<T>* LLRotation(AVLTreeNode<T>* k2);
AVLTreeNode<T>* LRRotation(AVLTreeNode<T>* k2);
AVLTreeNode<T>* RRRotation(AVLTreeNode<T>* k2);
AVLTreeNode<T>* RLRotation(AVLTreeNode<T>* k2);
AVLTreeNode<T>* insert(T key, AVLTreeNode<T>* root);
AVLTreeNode<T>* remove(AVLTreeNode<T>* del, AVLTreeNode<T>* root);
AVLTreeNode<T>* find(T key, AVLTreeNode<T>* root);
AVLTreeNode<T>* findmax(AVLTreeNode<T>* root);
AVLTreeNode<T>* findmin(AVLTreeNode<T>* root);
};
旋轉(zhuǎn)
AVL 樹的旋轉(zhuǎn)有 4 種，LL,RR,LR,RL。
LL
如圖所示，當(dāng)左子樹的左子樹影響平衡的時(shí)候，我們需要進(jìn)行 LL 旋轉(zhuǎn)。
首先，我們把 k1 提起來 (就像提繩子一樣)，這時(shí)候 k1 是根結(jié)點(diǎn)。但是這時(shí)候會(huì)發(fā)現(xiàn) k1 有三個(gè)子節(jié)點(diǎn)，不符合二叉樹的定義。同時(shí)又因?yàn)?k2 剛好被轉(zhuǎn)過去，沒有左子結(jié)點(diǎn)。所以我們就把 k1 原先的右子樹給 k2 當(dāng)左子樹。
因?yàn)?k2 之前是根節(jié)點(diǎn)，所以 k2>k1 的右子結(jié)點(diǎn) > k1，如上操作之后，符合 AVL 樹的定義。
每次旋轉(zhuǎn)之后都重新計(jì)算樹高。
template <typename T>
AVLTreeNode<T>* AVLTree<T>::LLRotation(AVLTreeNode<T>* k2) {
AVLTreeNode<T>* k1;
k1 = k2->l;
k2->l = k1->r;
k1->r = k2;
k2->height = max(height(k2->l), height(k2->r)) + 1;
k1->height = max(height(k1->l), k2->height) + 1;
return k1;
}
RR
理解 LL 之后，RR 就很好理解。
當(dāng)右子樹的右子樹影響平衡之后，我們首先把 k2 提起來，現(xiàn)在 k1 缺少右子結(jié)點(diǎn)，我們就把 k2 之前的左子樹給過去。
因?yàn)?k2>k2 的左子結(jié)點(diǎn) > k1，操作之后符合 AVL 樹的定義。
template <typename T>
AVLTreeNode<T>* AVLTree<T>::RRRotation(AVLTreeNode<T>* k1) {
AVLTreeNode<T>* k2;
k2 = k1->r;
k1->r = k2->l;
k2->l = k1;
k1->height = max(height(k1->l), height(k1->r)) + 1;
k2->height = max(height(k2->r), k1->height) + 1;
return k2;
}
LR
當(dāng)左子樹的右子樹影響平衡的時(shí)候，我們對(duì)右子樹進(jìn)行一次 RR 旋轉(zhuǎn)，之后就轉(zhuǎn)化為 LL 旋轉(zhuǎn)。
template <typename T>
AVLTreeNode<T>* AVLTree<T>::LRRotation(AVLTreeNode<T>* root) {
root->l = RRRotation(root->l);
return LLRotation(root);
}
RL
理解以上幾個(gè)之后，RL 也就很好理解了，此處不再贅述，請(qǐng)讀者自行思考。
template <typename T>
AVLTreeNode<T>* AVLTree<T>::RLRotation(AVLTreeNode<T>* root) {
root->r = LLRotation(root->r);
return RRRotation(root);
}
插入
我們遞歸查找插入的位置，回溯的過程中發(fā)現(xiàn)不平衡就去進(jìn)行旋轉(zhuǎn)。
template <typename T>
AVLTreeNode<T>* AVLTree<T>::insert(T key, AVLTreeNode<T>* root) {
if (root == nullptr) {
root = new AVLTreeNode<T>(key, nullptr, nullptr);
}
else if (key < root->key) {//插入到左子樹
root->l = insert(key, root->l);
if (height(root->l) - height(root->r) == 2) {
if (key < root->l->key) {
root = LLRotation(root);
}
else {
root = LRRotation(root);
}
}
}
else if (key > root->key) {//插入到右子樹
root->r = insert(key, root->r);
if (height(root->r) - height(root->l) == 2) {
if (key > root->r->key) {
root = RRRotation(root);
}
else {
root = RLRotation(root);
}
}
}
root->height = max(height(root->l), height(root->r)) + 1;
return root;
}
template <typename T>
void AVLTree<T>::insert(T key) {
root = insert(key, root);
}
查找和刪除
template <typename T>
AVLTreeNode<T>* AVLTree<T>::find(T key) {
return find(key, root);
}
template <typename T>
AVLTreeNode<T>* AVLTree<T>::find(T key, AVLTreeNode<T>* root) {
if (root == nullptr)
return root;
if (key > root->key) {
return find(key, root->r);
}
else if (key < root->key) {
return find(key, root->l);
}
else
return root;
}
template <typename T>
AVLTreeNode<T>* AVLTree<T>::findmax(AVLTreeNode<T>* root) {
if (root->r == nullptr)
return root;
return findmax(root->r);
}
template <typename T>
AVLTreeNode<T>* AVLTree<T>::findmin(AVLTreeNode<T>* root) {
if (root->l == nullptr)
return root;
return findmin(root->l);
}
template <typename T>
AVLTreeNode<T>* AVLTree<T>::remove(AVLTreeNode<T>* del, AVLTreeNode<T>* root) {
//沒找到直接返回
if (root == nullptr || del == nullptr)
return root;
if (del->key < root->key) {//需要?jiǎng)h除的結(jié)點(diǎn)在左子樹中
root->l = remove(del, root->l);
if (height(root->r) - height(root->l) == 2) {
if (height(root->r->l) > height(root->r->r)) {
root = RLRotation(root);
}
else {
root = RRRotation(root);
}
}
}
else if (del->key > root->key) {//需要?jiǎng)h除的結(jié)點(diǎn)在右子樹中
root->r = remove(del, root->r);
if (height(root->l) - height(root->r) == 2) {
if (height(root->l->r) > height(root->l->l)) {
root = LRRotation(root);
}
else {
root = LLRotation(root);
}
}
}
else {
//左右子樹都不為空，刪除后，我們可以用左子樹的最大結(jié)點(diǎn)或右子樹的最小結(jié)點(diǎn)來替換這個(gè)結(jié)點(diǎn)
if (root->l != nullptr && root->r != nullptr) {
if (height(root->l) > height(root->r)) {
//用左子樹的最大結(jié)點(diǎn)，好處是刪除后還是平衡的，無需旋轉(zhuǎn)
AVLTreeNode<T>* mx = findmax(root->l);
root->key = mx->key;
root->l = remove(mx, root->l);
}
else {
//用右子樹的最大結(jié)點(diǎn)，好處同上
AVLTreeNode<T>* mn = findmin(root->r);
root->key = mn->key;
root->r = remove(mn, root->r);
}
}
else {
AVLTreeNode<T>* tmp = root;
root = (root->l == nullptr) ? root->r : root->l;
delete tmp;
}
}
return root;
}
template <typename T>
void AVLTree<T>::remove(T key) {
root = remove(find(key), root);
}
總結(jié)
至于析構(gòu)，遍歷等等的代碼和此處不再給出，請(qǐng)參照正常的二叉樹操作自行思考。
AVL 樹的實(shí)現(xiàn)實(shí)際上不難，由于各種教材上冗長(zhǎng)的介紹，使得我們有一種認(rèn)為它難的錯(cuò)覺。
評(píng)論
圖片
表情