高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法4：BST(二叉搜索樹(shù))烘嘱、AVL樹(shù)(平衡二叉樹(shù))

visualgo.net BST AVL

1. 二叉查找樹(shù)

二叉查找樹(shù)(Binary Search Tree)，又被稱為二叉搜索樹(shù)

1. 特點(diǎn)

任意節(jié)點(diǎn)的左子樹(shù)不空, 則左子樹(shù)上所有節(jié)點(diǎn)的key均小于它的根節(jié)點(diǎn)的key
任意節(jié)點(diǎn)的右子樹(shù)不空, 則右子樹(shù)上所有節(jié)點(diǎn)的key均大于它的根節(jié)點(diǎn)的key
任意節(jié)點(diǎn)的左,右子樹(shù)也分別為二叉查找樹(shù)
沒(méi)有key相等的節(jié)點(diǎn)

二叉查找樹(shù)進(jìn)行中序遍歷攘残，可以得到一個(gè)遞增的有序序列

BST的中序遍歷

2. 結(jié)構(gòu)

二叉搜索樹(shù)通常使用鏈?zhǔn)酱鎯?chǔ)孩子表示法拙友。

struct Node {
    int key;
    struct Node* left;
    struct Node* right;
}

3. 操作

3.1 插入

如果二叉查找樹(shù)為空为狸，則直接插入歼郭。
如果插入節(jié)點(diǎn)key小于根結(jié)點(diǎn)key，則插入到左子樹(shù)中辐棒；大于根結(jié)點(diǎn)key病曾，則插入到右子樹(shù)中牍蜂。
依次類推，直到找到插入位置泰涂。

BST默認(rèn)插入新的節(jié)點(diǎn)是葉子節(jié)點(diǎn)鲫竞。

Node* Insert(Node*& node, int key){
    if(NULL == node) node = new Node(key);
    if (key < node->key) node->left = Insert(node->left, key);
    else if (key > node->key) node->right = Insert(node->right,key);    
    return node;
}

3.2 查找

查找指定key的節(jié)點(diǎn)
從根結(jié)點(diǎn)開(kāi)始，若二叉樹(shù)非空逼蒙，將給定值與根結(jié)點(diǎn)的關(guān)鍵字比較从绘，若相等，則查找成功是牢；若不等僵井，則當(dāng)給定值小于根結(jié)點(diǎn)關(guān)鍵字時(shí)，在根結(jié)點(diǎn)的左子樹(shù)中查找驳棱，否則在根結(jié)點(diǎn)的右子樹(shù)中查找批什。
```
Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}
```

查找最大/最小key的節(jié)點(diǎn)

// 最大鍵
Node* Maximum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->right) node = node->right;
    return node;
}

// 最小鍵
Node* Minimum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->left) node = node->left;
    return node;
}

3.3 刪除

二叉查找樹(shù)的刪除操作是相對(duì)復(fù)雜一點(diǎn)，它要按 3 種情況來(lái)處理：

被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)社搅，直接刪除驻债。
結(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)，則讓子樹(shù)替代形葬；
結(jié)點(diǎn)既有左子樹(shù)合呐，又有右子樹(shù)，有兩種處理方式
替代刪除笙以，后繼代替刪除節(jié)點(diǎn)合砂，然后刪除后繼；或者前驅(qū)代替刪除節(jié)點(diǎn)源织，然后刪除前驅(qū)翩伪。
合并刪除，右子樹(shù)合并到左子樹(shù)的最大值的右子樹(shù)上谈息；或者左子樹(shù)合并到右子樹(shù)最小值的左子樹(shù)上缘屹。

合并刪除-增加樹(shù)高.png

Node* Remove(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) node->left = Remove(node->left, key);
    else if (key > node->key) node->right = Remove(node->right, key);
    else {
        if(NULL != node->right && NULL != node->left){// 有兩個(gè)子樹(shù)
            // 最小值刪除
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = Remove(node->right,p->key);
        } else {// 葉子節(jié)點(diǎn)或者只有一個(gè)子樹(shù)
            Node* res = NULL;
            if(NULL != node->right) res = node->right;
            if(NULL != node->left) res = node->left;
            delete node;
            node = NULL;
            return res;
        }
    }
    return node;
}

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

No.	操作	時(shí)間復(fù)雜度
1	插入	`O(log n)`
2	查找	`O(log n)`
3	插入	`O(log n)`

缺點(diǎn)
二叉搜索樹(shù)構(gòu)造順序影響操作的時(shí)間復(fù)雜度。

參考代碼

#include <iostream>
#include <queue>
using namespace std;

// 節(jié)點(diǎn)
struct Node{
    int key;        ///< 鍵
    Node *left;     ///< 左子節(jié)點(diǎn)
    Node *right;    ///< 右子節(jié)點(diǎn)
    Node(int key) 
    :key(key),left(NULL),right(NULL){}
};

// 輔助操作
Node* Maximum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->right) node = node->right;
    return node;
}
Node* Minimum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->left) node = node->left;
    return node;
}

// 核心操作
Node* Insert(Node*& node, int key){
    if(NULL == node) node = new Node(key);
    if (key < node->key) node->left = Insert(node->left, key);
    else if (key > node->key) node->right = Insert(node->right,key);    
    return node;
}

Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}
Node* Remove(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) node->left = Remove(node->left, key);
    else if (key > node->key) node->right = Remove(node->right, key);
    else {
        if(NULL != node->right && NULL != node->left){// 有兩個(gè)子樹(shù)
            // 最小值刪除
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = Remove(node->right,p->key);
        } else {// 葉子節(jié)點(diǎn)或者只有一個(gè)子樹(shù)
            Node* res = NULL;
            if(NULL != node->right) res = node->right;
            if(NULL != node->left) res = node->left;
            delete node;
            node = NULL;
            return res;
        }
    }
    return node;
}

/////////////////////////////////////////////////////////////
ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key;
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}
void TestInsert(Node*& root){
    Insert(root,1);
    Insert(root,2);
    Insert(root,3);
    Insert(root,4);
    Insert(root,5);
    cout << *root << endl;
}
void TestSearch(Node* root,int key){
    cout <<"Search " << key << ":" << Search(root,key) << endl;
}
void TestRemove(Node*& root,int key){
    root = Remove(root, key);
    cout <<"Remove " << key << ":" ;
    if(NULL != root) cout << *root << endl;
    else cout << "#" << endl;
}
void TestMax(Node* root){
    Node* maxNode = Maximum(root);
    cout << "Max:"<< maxNode->key <<":"<< maxNode <<endl;
}
void TestMin(Node* root){
    Node* minNode = Minimum(root);
    cout << "Min:"<< minNode->key <<":"<< minNode <<endl;
}

int main(){
    Node* root = NULL;
    TestInsert(root);
    TestSearch(root,1);
    TestSearch(root,2);
    TestSearch(root,3);
    TestSearch(root,4);
    TestSearch(root,5);
    TestSearch(root,6);
    TestSearch(root,7);
    TestSearch(root,8);
    TestMax(root);
    TestMin(root);

    // TestRemove(root, 8);
    // TestRemove(root, 7);
    // TestRemove(root, 6);
    // TestRemove(root, 2);
    // TestRemove(root, 5);
    // TestRemove(root, 4);
    // TestRemove(root, 3);
    // TestRemove(root, 1);
    TestRemove(root,1);
    TestRemove(root,2);
    TestRemove(root,3);
    TestRemove(root,4);
    TestRemove(root,5);
}

450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

2. AVL樹(shù)(平衡二叉樹(shù))

BST樹(shù)的缺點(diǎn)不平衡

二叉樹(shù)的平衡.png

平衡二叉樹(shù)/自平衡二叉查找樹(shù)(Balanced Binary Tree)：也稱為AVL樹(shù)(名稱來(lái)自發(fā)明人G.M. Adelson-Velsky 和 E.M. Landis的首字母)侠仇，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1轻姿，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

特點(diǎn)

左右子樹(shù)深度之差的絕對(duì)值不超過(guò)1(任意節(jié)點(diǎn)的兩子樹(shù)的高度最大差別為1).
左右子樹(shù)仍然為平衡二叉樹(shù).

平衡因子BF(Balance Factor)：左樹(shù)深度減去右樹(shù)深度的值逻炊。平衡因子BF = 左子樹(shù)深度－右子樹(shù)深度互亮。
平衡二叉樹(shù)每個(gè)結(jié)點(diǎn)的平衡因子只能是1，0余素，-1豹休。若其絕對(duì)值超過(guò)1，則該二叉排序樹(shù)就是不平衡的桨吊。當(dāng)BF為-1威根、0凤巨、1時(shí)，二叉樹(shù)平衡洛搀；反之敢茁，不平衡。

樹(shù)快速查找的關(guān)鍵是高度要低留美，高度低的關(guān)鍵是平衡彰檬。

判斷平衡:BF

判斷平衡二叉樹(shù)

/* 節(jié)點(diǎn) */
struct Node{
    char key;       // 鍵值
    Node* right;    // 右節(jié)點(diǎn)
    Node* left;     // 左節(jié)點(diǎn)
    int height;     // 節(jié)點(diǎn)高度
    Node(char key):key(key),right(NULL),left(NULL),height(0){}
    Node(char key,int height):key(key),right(NULL),left(NULL),height(height){}
};

/*
* 平衡因子:左子樹(shù)樹(shù)高-右子樹(shù)樹(shù)高
*/
int BalanceFactor(const Node* root){
    if(NULL == root) return 0;
    if(NULL == root->left && NULL == root->right) return 0;
    if(NULL == root->left) return -root->right->height;
    if(NULL == root->right) return root->left->height;
    return root->left->height - root->right->height;
}

ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key << "[" << BalanceFactor(curr)<<"]";
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}
int main(){
    {
        //     1
        //    /
        //   2
        //  /
        // 3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.left = &b;
        b.left = &c;
        cout << a << endl;
    }
    {
        // 1
        //  \
        //   2
        //    \
        //     3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.right = &b;
        b.right = &c;
        cout << a << endl;
    }
    {
        //     1
        //    /
        //   2
        //    \
        //     3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.left = &b;
        b.right = &c;
        cout << a << endl;
    }
    {
        // 1
        //  \
        //   2
        //  /
        // 3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.right = &b;
        b.left = &c;
        cout << a << endl;
    }
}

LeetCode 110. 平衡二叉樹(shù)

兩種旋轉(zhuǎn)(左旋/右旋)、三個(gè)節(jié)點(diǎn)(新插入節(jié)點(diǎn)/不平衡節(jié)點(diǎn)/旋轉(zhuǎn)節(jié)點(diǎn))谎砾、四種不平衡(LL/RR/RL/LR)僧叉。

操作

AVL樹(shù)的操作基本和二叉查找樹(shù)一樣，這里我們關(guān)注的是兩個(gè)變化很大的操作：插入和刪除棺榔！

旋轉(zhuǎn)

旋轉(zhuǎn)條件：當(dāng)最小不平衡子樹(shù)根節(jié)點(diǎn)BF>1,右旋瓶堕；BF<-1,左旋。

當(dāng)P的A症歇、B節(jié)點(diǎn)插入新結(jié)點(diǎn)郎笆，導(dǎo)致Q點(diǎn)不平衡，左重右輕忘晤，右旋宛蚓。
當(dāng)Q的B、C節(jié)點(diǎn)插入新結(jié)點(diǎn)设塔，導(dǎo)致P點(diǎn)不平衡凄吏，右重左輕，左旋闰蛔。
旋轉(zhuǎn)點(diǎn)上升痕钢，不平衡點(diǎn)向輕的一側(cè)旋轉(zhuǎn)。

旋轉(zhuǎn)步驟：

獲取旋轉(zhuǎn)節(jié)點(diǎn)
旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)
返回旋轉(zhuǎn)節(jié)點(diǎn)

依次插入1,2,3

依次插入3,2,1

依次插入2,1,3或2,3,1

依次插入1,3,2

依次插入3,1,2

依次插入4,5

依次插入6,7

旋轉(zhuǎn)1→2→3和3→2→1的情況

#include <iostream>
#include <queue>
using namespace std;

/* 節(jié)點(diǎn) */
struct Node{
    char key;       // 鍵值
    Node* right;    // 右節(jié)點(diǎn)
    Node* left;     // 左節(jié)點(diǎn)
    int height;     // 節(jié)點(diǎn)高度
    Node(char key):key(key),right(NULL),left(NULL),height(0){}
};

ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key;
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->left = pivot->right; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->right = root;       // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn)
}

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->right = pivot->left; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->left = root;        // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn) 
}

int main(){
    {
        Node a('1');
        Node b('2');
        Node c('3');
        a.left = &b;
        b.left = &c;
        cout << a << endl;
        cout << *RightRotate(&a) << endl;
    }
    {
        Node a('1');
        Node b('2');
        Node c('3');
        a.right = &b;
        b.right = &c;
        cout << a << endl;
        cout << *LeftRotate(&a) << endl;
    }
    {
        Node q('Q');
        Node p('P');
        Node c('C');
        Node a('A');
        Node b('B');
        q.left = &p;
        q.right = &c;
        p.left = &a;
        p.right = &b;
        cout << q << endl;
        Node* r = RightRotate(&q);
        cout << *r << endl;
        Node *l = LeftRotate(r);
        cout << *l << endl;
    }
}

四種不平衡

不平衡的四種情況：
LL：插入一個(gè)新節(jié)點(diǎn)到不平衡節(jié)點(diǎn)的左子樹(shù)（Left）的左子樹(shù)（Left）序六，導(dǎo)致不平衡節(jié)點(diǎn)的平衡因子由1變?yōu)?

RR：插入一個(gè)新節(jié)點(diǎn)到不平衡節(jié)點(diǎn)的右子樹(shù)（Right）的右子樹(shù)（Right）任连，導(dǎo)致不平衡節(jié)點(diǎn)的平衡因子由-1變?yōu)?2

LR：插入一個(gè)新節(jié)點(diǎn)到不平衡節(jié)點(diǎn)的左子樹(shù)（Left）的右子樹(shù)（Right），導(dǎo)致不平衡節(jié)點(diǎn)的平衡因子由1變?yōu)?

RL：插入一個(gè)新節(jié)點(diǎn)到不平衡節(jié)點(diǎn)的右子樹(shù)（Right）的左子樹(shù)（Left）例诀，導(dǎo)致不平衡節(jié)點(diǎn)的平衡因子由-1變?yōu)?2

判斷四種不平衡
1→2→3
3→2→1
1→3→2
3→1→2
依次插入：3,4,5,1,2
依次插入：3,4,5,2,1
依次插入：3,4,5,6,7
依次插入：3,4,5,7,6
依次插入：7,4,1,3,2,8,9,5,6

/*
* 檢查是否平衡
*/
void Check(Node* root){
    int nf = BalanceFactor(root);
    if(nf>1){
        int lf = BalanceFactor(root->left);
        if(lf > 0) { // LL
            cout << "LL" << endl;
        } else { // LR
            cout << "LR" << endl;
        }
    }else if(nf < -1){
        int rf = BalanceFactor(root->right);
        if (rf < 0) { // RR
            cout << "RR" << endl;
        } else { // RL
            cout << "RL" << endl;
        }
    }else{// 保持平衡的情況
        cout << "Balance" << endl;
    }
}
int main(){
    {
        //     1
        //    /
        //   2
        //  /
        // 3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.left = &b;
        b.left = &c;
        cout << a << endl;
        Check(&a);
    }

    {
        // 1
        //  \
        //   2
        //    \
        //     3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.right = &b;
        b.right = &c;
        cout << a << endl;
        Check(&a);
    }

    {
        //     1
        //    /
        //   2
        //    \
        //     3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.left = &b;
        b.right = &c;
        cout << a << endl;
        Check(&a);
    }

    {
        // 1
        //  \
        //   2
        //  /
        // 3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.right = &b;
        b.left = &c;
        cout << a << endl;
        Check(&a);
    }

    {
        //     1
        //    / \
        //   2   4
        //  / \
        // 3   5
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        cout << a << endl;
        Check(&a);
    }

    {
        //   1
        //  / \
        // 4   2
        //    / \
        //   5   3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 1);
        a.right = &b;
        a.left = &d;
        b.right = &c;
        b.left = &e;
        cout << a << endl;
        Check(&a);
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //  /
        // 6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 2);
        Node d('4', 1);
        Node e('5', 1);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        c.left = &f;
        cout << a << endl;
        Check(&a);
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //    \
        //     6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 2);
        Node d('4', 1);
        Node e('5', 1);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        c.right = &f;
        cout << a << endl;
        Check(&a);
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //      /
        //     6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 2);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        e.left = &f;
        cout << a << endl;
        Check(&a);
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //        \
        //         6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 2);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        e.right = &f;
        cout << a << endl;
        Check(&a);
    }

    {
        //   1
        //  / \
        // 4   2
        //    / \
        //   5   3
        //  /
        // 6
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 1);
        Node f('6', 1);
        a.right = &b;
        a.left = &d;
        b.right = &c;
        b.left = &e;
        e.left = &f;
        cout << a << endl;
        Check(&a);
    }
}

不平衡處理方法

單向右旋平衡處理LL
單向左旋平衡處理RR
雙向旋轉(zhuǎn)（先左后右）平衡處理LR
雙向旋轉(zhuǎn)（先右后左）平衡處理RL

image.png

/*
* 平衡
*/
Node* Balance(Node* root){
    Node *res = root;
    int nf = BalanceFactor(root);
    if(nf>1){
        int lf = BalanceFactor(root->left);
        if(lf > 0) { // LL
            cout << "LL" << endl;
            res = RightRotate(root);
        } else { // LR
            cout << "LR" << endl;
            root->left = LeftRotate(root->left);
            res = RightRotate(root);
        }
    }else if(nf <-1){
        int rf = BalanceFactor(root->right);
        if (rf < 0) { // RR
            cout << "RR" << endl;
            res = LeftRotate(root);
        } else { // RL
            cout << "RL" << endl;
            root->right = RightRotate(root->right);
            res = LeftRotate(root);
        }
    }else{
        cout << "Balance" << endl;
        // 保持平衡的情況
    }
    return res;
}
int main(){
    {
        //     1
        //    /
        //   2
        //  /
        // 3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.left = &b;
        b.left = &c;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        // 1
        //  \
        //   2
        //    \
        //     3
        Node a('1',3);
        Node b('2',2);
        Node c('3',1);
        a.right = &b;
        b.right = &c;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //     1
        //    /
        //   2
        //    \
        //     3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.left = &b;
        b.right = &c;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        // 1
        //  \
        //   2
        //  /
        // 3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        a.right = &b;
        b.left = &c;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //     1
        //    / \
        //   2   4
        //  / \
        // 3   5
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //   1
        //  / \
        // 4   2
        //    / \
        //   5   3
        Node a('1', 3);
        Node b('2', 2);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 1);
        a.right = &b;
        a.left = &d;
        b.right = &c;
        b.left = &e;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //  /
        // 6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 2);
        Node d('4', 1);
        Node e('5', 1);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        c.left = &f;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //    \
        //     6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 2);
        Node d('4', 1);
        Node e('5', 1);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        c.right = &f;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //      /
        //     6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 2);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        e.left = &f;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }

    {
        //       1
        //      / \
        //     2   4
        //    / \
        //   3   5
        //        \
        //         6
        Node a('1', 4);
        Node b('2', 3);
        Node c('3', 1);
        Node d('4', 1);
        Node e('5', 2);
        Node f('6', 1);
        a.left = &b;
        a.right = &d;
        b.left = &c;
        b.right = &e;
        e.right = &f;
        cout << a << endl;
        Check(&a);
        cout << *Balance(&a) << endl;
        cout << "----------------" << endl;
    }
}

更新樹(shù)高

/*
* 更新樹(shù)高
*/
int UpdateHeight(Node* root){
    if(NULL == root) return 0;
    if(NULL == root->left && NULL == root->right) {
        root->height = 1;
    } else if(NULL == root->left) {
        root->height = 1 + UpdateHeight(root->right);
    } else if(NULL == root->right) {
        root->height = 1 + UpdateHeight(root->left);
    } else {
        root->height = 1 + max(UpdateHeight(root->left),UpdateHeight(root->right));
    }
    return root->height;
}

插入

與 BST（二叉搜索樹(shù)）中類似随抠，先進(jìn)行一次失敗的查找來(lái)確定插入的位置，插入節(jié)點(diǎn)后根據(jù)平衡因子來(lái)決定是否需要調(diào)整繁涂。

二叉樹(shù)的平衡1-右旋.png

二叉樹(shù)的平衡2-左旋.png

二叉樹(shù)的平衡3-左旋.png

二叉樹(shù)的平衡4-左旋.png

二叉樹(shù)的平衡5-右旋左旋.png

二叉樹(shù)的平衡6-右旋左旋.png

/*
* 插入AVL樹(shù)
*/
bool Insert(Node*& root,char key){
    bool res;
    if (NULL == root){
        root = new Node(key);
        res = true;
    } else if (root->key == key){
        res = false;
    } else if (root->key < key){
        res = Insert(root->right, key);
    } else {
        res = Insert(root->left, key);
    }
    if(res){
        root = Balance(root);
        UpdateHeight(root); // 更新高度
    }
    return res;
}

刪除

刪除情況分析

刪除節(jié)點(diǎn)有三種情況

刪除葉子節(jié)點(diǎn)拱她。
刪除只有一棵子樹(shù)的節(jié)點(diǎn)。
刪除有兩棵子樹(shù)的節(jié)點(diǎn)扔罪。

AVL刪除與BST刪除方式一致秉沼，但是AVL刪除會(huì)導(dǎo)致樹(shù)高以及平衡因子變化，這時(shí)需要沿著被刪除結(jié)點(diǎn)到根的路徑來(lái)調(diào)整這種變化。

復(fù)制刪除.png

合并刪除.png

合并刪除2.png

優(yōu)點(diǎn)

查找氧猬、插入和刪除在平均和最壞情況下都是O(logn)。

缺點(diǎn)

插入和刪除旋轉(zhuǎn)比較耗時(shí)坏瘩，適用于插入和刪除較少的情況盅抚。

參考代碼

#include <iostream>
#include <queue>
using namespace std;

struct Node{
    int key;        ///< 鍵
    Node *left;     ///< 左子節(jié)點(diǎn)
    Node *right;    ///< 右子節(jié)點(diǎn)
    int height;     ///< 節(jié)點(diǎn)高度
    Node(int key, int height) 
    :key(key),left(NULL),right(NULL),height(height){}
};

// 輔助操作
Node* Maximum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->right) node = node->right;
    return node;
}

Node* Minimum(Node* node){
    if (NULL == node) return NULL;
    while (NULL != node->left) node = node->left;
    return node;
}

// 平衡因子:左子樹(shù)樹(shù)高-右子樹(shù)樹(shù)高
int BalanceFactor(const Node* root){
    if(NULL == root) return 0;
    if(NULL == root->left && NULL == root->right) return 0;
    if(NULL == root->left) return -root->right->height;
    if(NULL == root->right) return root->left->height;
    return root->left->height - root->right->height;
}

/*
 * 右旋
 *       Q                  P 
 *      / \                / \ 
 *     P   C  ------->    A   Q 
 *    / \                /   / \ 
 *   A   B              X'  B   C  
 *
 */
Node* RightRotate(Node* root){
    Node* pivot = root->left;  // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->left = pivot->right; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->right = root;       // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn)
}

/*
 * 左旋
 *      P                    Q
 *     / \                  / \ 
 *    A   Q     ----->     P   C 
 *       / \              / \   \ 
 *      B   C            A   B   X'  
 */
Node* LeftRotate(Node* root){
    Node* pivot = root->right; // 獲取旋轉(zhuǎn)節(jié)點(diǎn)
    root->right = pivot->left; // 旋轉(zhuǎn)節(jié)點(diǎn)的子節(jié)點(diǎn)替換父節(jié)點(diǎn)的旋轉(zhuǎn)節(jié)點(diǎn)
    pivot->left = root;        // 旋轉(zhuǎn)節(jié)點(diǎn)父節(jié)點(diǎn)做旋轉(zhuǎn)節(jié)點(diǎn)子節(jié)點(diǎn)
    return pivot;              // 返回旋轉(zhuǎn)節(jié)點(diǎn) 
}

// 更新樹(shù)高
int UpdateHeight(Node* root){
    if(NULL == root) return 0;
    if(NULL == root->left && NULL == root->right) {
        root->height = 1;
    } else if(NULL == root->left) {
        root->height = 1 + UpdateHeight(root->right);
    } else if(NULL == root->right) {
        root->height = 1 + UpdateHeight(root->left);
    } else {
        root->height = 1 + max(UpdateHeight(root->left),UpdateHeight(root->right));
    }
    return root->height;
}

// 平衡
Node* Balance(Node* root){
    Node *res = root;
    int nf = BalanceFactor(root);
    if(nf>1){
        int lf = BalanceFactor(root->left);
        if(lf > 0) { // LL
            cout << "LL" << endl;
            res = RightRotate(root);
        } else { // LR
            cout << "LR" << endl;
            root->left = LeftRotate(root->left);
            res = RightRotate(root);
        }
    }else if(nf <-1){
        int rf = BalanceFactor(root->right);
        if (rf < 0) { // RR
            cout << "RR" << endl;
            res = LeftRotate(root);
        } else { // RL
            cout << "RL" << endl;
            root->right = RightRotate(root->right);
            res = LeftRotate(root);
        }
    }else{
        cout << "Balance" << endl;
        // 保持平衡的情況
        // return res;
    }
    UpdateHeight(res);
    return res;
}

// 三個(gè)核心操作
Node* Insert(Node* node, int key){
    if(NULL == node) node = new Node(key,1);
    if (key < node->key) node->left = Insert(node->left, key);
    else if (key > node->key) node->right = Insert(node->right,key);
    node = Balance(node); // 平衡
    return node;
}

Node* Search(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) return Search(node->left, key);
    else if (key > node->key) return Search(node->right, key);
    return node;
}

Node* Remove(Node* node, int key){
    if(NULL == node) return NULL;
    if (key < node->key) node->left = Remove(node->left, key);
    else if (key > node->key) node->right = Remove(node->right, key);
    else {
        if(NULL != node->right && NULL != node->left){// 有兩個(gè)子樹(shù)
            // 最小值刪除
            Node* p = Minimum(node->right);
            node->key = p->key;
            node->right = Remove(node->right,p->key);
        } else {// 葉子節(jié)點(diǎn)或者只有一個(gè)子樹(shù)
            Node* res = NULL;
            if(NULL != node->right) res = node->right;
            if(NULL != node->left) res = node->left;
            delete node;
            node = NULL;
            return res;
        }
    }
    node = Balance(node); // 平衡
    return node;
}
/////////////////////////////////////////////////////////////
ostream& operator<<(ostream& os,const Node root) {
    queue<const Node*> q;
    q.push(&root);
    while(!q.empty()){
        const Node* curr = q.front();
        q.pop();
        if (NULL != curr){
            os << curr->key << '[' << curr->height <<']';
            q.push(curr->left);
            q.push(curr->right);
        } else {
            os << '#';
        }
    }
    return os;        
}
void TestInsert(Node*& root){
    root = Insert(root,1);
    root = Insert(root,2);
    root = Insert(root,3);
    root = Insert(root,4);
    root = Insert(root,5);
    cout << *root << endl;
}
void TestSearch(Node* root,int key){
    cout <<"Search " << key << ":" << Search(root,key) << endl;
}
void TestRemove(Node*& root,int key){
    root = Remove(root, key);
    cout <<"Remove " << key << ":" ;
    if(NULL != root) cout << *root << endl;
    else cout << "#" << endl;
}
void TestMax(Node* root){
    Node* maxNode = Maximum(root);
    cout << "Max:"<< maxNode->key <<":"<< maxNode <<endl;
}
void TestMin(Node* root){
    Node* minNode = Minimum(root);
    cout << "Min:"<< minNode->key <<":"<< minNode <<endl;
}

int main(){
    Node* root = NULL;
    TestInsert(root);
    TestSearch(root,1);
    TestSearch(root,2);
    TestSearch(root,3);
    TestSearch(root,4);
    TestSearch(root,5);
    TestSearch(root,6);
    TestSearch(root,7);
    TestSearch(root,8);
    TestMax(root);
    TestMin(root);

    // TestRemove(root, 8);
    // TestRemove(root, 7);
    // TestRemove(root, 6);
    TestRemove(root, 2);
    TestRemove(root, 5);
    TestRemove(root, 4);
    TestRemove(root, 3);
    TestRemove(root, 1);
    // TestRemove(root,1);
    // TestRemove(root,2);
    // TestRemove(root,3);
    // TestRemove(root,4);
    // TestRemove(root,5);
}

BST與AVL比較

最后編輯于：2021.07.27 15:38:51

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市倔矾，隨后出現(xiàn)的幾起案子妄均，更是在濱河造成了極大的恐慌，老刑警劉巖哪自，帶你破解...
沈念sama閱讀 206,311評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件丰包，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡壤巷，警方通過(guò)查閱死者的電腦和手機(jī)邑彪，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,339評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)胧华，“玉大人寄症，你說(shuō)我怎么就攤上這事【囟” “怎么了有巧？”我有些...
開(kāi)封第一講書人閱讀 152,671評(píng)論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)悲没。經(jīng)常有香客問(wèn)我篮迎，道長(zhǎng)，這世上最難降的妖魔是什么示姿？我笑而不...
開(kāi)封第一講書人閱讀 55,252評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任甜橱，我火速辦了婚禮，結(jié)果婚禮上栈戳，老公的妹妹穿的比我還像新娘渗鬼。我一直安慰自己，他們只是感情好荧琼，可當(dāng)我...
茶點(diǎn)故事閱讀 64,253評(píng)論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布譬胎。她就那樣靜靜地躺著，像睡著了一般命锄。火紅的嫁衣襯著肌膚如雪堰乔。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書人閱讀 49,031評(píng)論 1贊 285
城市分裂傳說(shuō)
那天脐恩，我揣著相機(jī)與錄音镐侯，去河邊找鬼。笑死，一個(gè)胖子當(dāng)著我的面吹牛苟翻，可吹牛的內(nèi)容都是我干的韵卤。我是一名探鬼主播，決...
沈念sama閱讀 38,340評(píng)論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼崇猫，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼沈条！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起诅炉，我...
開(kāi)封第一講書人閱讀 36,973評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤蜡歹，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后涕烧，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體月而，經(jīng)...
沈念sama閱讀 43,466評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,937評(píng)論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年议纯，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了父款。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,039評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡瞻凤，死狀恐怖铛漓，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情鲫构，我是刑警寧澤浓恶，帶...
沈念sama閱讀 33,701評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站结笨，受9級(jí)特大地震影響包晰，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜炕吸，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,254評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一伐憾、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧赫模，春花似錦树肃、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,259評(píng)論 0贊 19
一樁弒父案胸嘴，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至斩祭，卻和暖如春劣像，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背摧玫。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,485評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工耳奕，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人。一個(gè)月前我還...
沈念sama閱讀 45,497評(píng)論 2贊 354
代替公主和親
正文我出身青樓屋群，卻偏偏與公主長(zhǎng)得像闸婴，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子芍躏，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,786評(píng)論 2贊 345

高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法4：BST(二叉搜索樹(shù))、AVL樹(shù)(平衡二叉樹(shù))

高級(jí)數(shù)據(jù)結(jié)構(gòu)和算法4：BST(二叉搜索樹(shù))烘嘱、AVL樹(shù)(平衡二叉樹(shù))

1. 二叉查找樹(shù)

1. 特點(diǎn)

2. 結(jié)構(gòu)

3. 操作

3.1 插入

3.2 查找

3.3 刪除

優(yōu)缺點(diǎn)

參考代碼

98. 驗(yàn)證二叉搜索樹(shù)

700. 二叉搜索樹(shù)中的搜索

701. 二叉搜索樹(shù)中的插入操作

450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)

2. AVL樹(shù)(平衡二叉樹(shù))

特點(diǎn)

操作

旋轉(zhuǎn)

四種不平衡

插入

刪除

優(yōu)點(diǎn)

缺點(diǎn)

參考代碼

BST與AVL比較

推薦閱讀更多精彩內(nèi)容