基礎知識--二叉樹 AVL樹 紅黑樹

二叉樹

二叉樹定義

二叉樹是每個結點最多有兩個子結點的數結構。

二叉樹的性質

一、度數為0的結點個數等于度數為2的結點個數加一，即n0=n2+1。

解釋：隻有一個根結點時 n0=1, n1=0, n2=0;（初始狀态）。每添加一個結點a于結點b之下，b結點隻存在兩種情況：1、結點b的度數為0；2、結點b的度數為1。

在第1種情況下，n0不變，n1++, n2不變。

在第2中情況下，n0++，n1不變，n2++。

可以發現n0和n2是要麼同時加一，要麼都不加。

是以n0=n2+1;

二、在非空二叉樹中，第n層的結點個數不超過 2n−1 (n>=1)。

解釋：n=1時 結點個數為1（初始狀态）。下一層的結點個數為上一層結點個數的兩倍。是以可以看成為n1=1，q=2。的等比數列。

三、深度為n的二叉樹，其總結點個數不超過 2n−1 (n>=0)。

解釋：由等比數列求和得總結點個數為 2n−1。

四、有n個結點的完全二叉樹各結點如果用順序方式編号，則結點之間的編号關系如下：

若I為該結點編号，其父結點編号為(int)I/2。

若存在左孩子，其編号為 2⋅I 。

若存在右孩子，其編号為 2⋅I+1 。

思路：

父結點和子結點之間的關系可以通過樹的高度建立起，是以通過高度尋找關系。（模棱兩可 @[email protected]）

解釋：

令:編号為I的結點的高度為h，Left為I的左結點的編号，Right為I的右結點的編号。

∵Left=(2h−1)+與I結點同高度卻在I結點前面的個數×2+1

又∵與I結點同高度卻在I結點前面的個數=I−(2h−1−1)−1=I−2h−1

∴Left=(2h−1)+2×(I−2h−1)+1

即Left=2⋅I

又∵Right=Left+1

∴Right=2⋅I+1

AVL樹

要求：任一結點的左子樹的深度和右子樹的深度差的絕對值不超過1。

|LeftNodeDepth−RightNodeDepth|≤1 ，本文中稱LeftNodeDepth - RightNodeDepth為平衡因子

這個要求的目的是使二叉搜尋樹實作平衡

因為一個二叉樹的搜尋算法複雜度與數的高度有關為 O(log2h) ,是以控制二叉樹的平衡型是重要的。

我們在每次插入結點時判斷新加入的結點是否會破壞整顆樹的平衡，如果會破壞就要進行相應的調整。（左旋，右旋等調整）

了解左旋和右旋

左結點偏重時進行左旋，使左結點的深度至少減一，右結點的深度至少加一。反之進行右旋，使左結點的深度至少加一，右結點的深度至少減一。進而起到大緻控制左右結點深度的作用。

圖檔：

過程：

對5結點進行左旋

1、5結點變為3結點的右結點

2、3結點的右結點B變為5結點的左結點

對3結點進行右旋

1、3結點變為5結點的左結點

2、5結點的左結點B變為3結點的右結點

證明：

對5結點進行左旋

1、5結點比3結點要大，是以 {5結點變為3結點的右結點} 這個過程不會破壞順序。

2、B結點比3大比5小，是以B結點成為5結點的左結點也不會破壞順序。

對3結點進行右旋

證明過程同左旋

什麼時候進行左旋或者右旋?

在破壞AVL樹的要求時就要進行相應的調整。在左結點深度減右結點的深度的絕對值大于1時，就破壞了AVL樹的平衡。

• 情況1_1：平衡因子>1時，且其左結點的平衡因子>0，對該結點進行右旋。

  

  圖檔解釋：當插入I結點時，I結點經過的A、B、C結點的平衡因子的值都發生了改變。其中A結點和B結點的平衡因子變為了2，是以對A結點或B結點進行右旋。

  其中對A結點進行右旋在代碼中是不推薦的，因為不是所有情況都存在兩個平衡值為2的結點。而 2、1、0(B結點、C結點、I結點) 才是該情況的特點。

• 情況1_2：平衡因子>1時，且其左結點的平衡因子<0，對該結點的左結點進行左旋，然後對該結點進行右旋。

  對該結點的左結點進行左旋的目的是，讓左結點的平衡因子變為>0的值(就變成情況1_1了)。

• 情況2_1：平衡因子<-1時，且其右結點的平衡因子<0，對該結點進行左旋。

• 情況2_2：平衡因子<-1時，且其右結點的平衡因子>0，對該結點的右結點進行右旋，然後對該結點進行左旋。

  對該結點的右結點進行左旋的目的是，讓右結點的平衡因子變為<0的值(就變成情況2_1了)。

  代碼實作

//資料結構
struct Node{
    int value;//序号
    int balance;//平衡因子
    Node *left;
    Node *right;
}Node;
//所需函數
void LeftRotate(Node*);//左旋
void RightRotate(Node*);//右旋
class AvlTree{
public:
    Node root;
    AvlTree(){};
    void insert(Node* pNode){
        if(pNode -> value < root)
    };
};
           

紅黑樹