平衡二叉樹——AVL樹的實現

2019-11-10 19:42:58

字體：大中小

來源：轉載

供稿：網友

平衡二叉樹——AVL樹的實現

分類：數據結構 2013-09-05 10:44 48人閱讀評論(0)收藏舉報AVL樹平衡二叉樹數據結構

AVL樹是最先發明的自平衡二叉查找算法，是平衡二叉樹的一種。在AVL中任何節點的兩個兒子子樹的高度最大差別為1，所以它又被成為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來平衡這棵樹。

假設把AVL樹構造過程中需要重新平衡的節點叫做α。由于任意節點最多有兩個兒子，因此高度不平衡時，α點的兩顆子樹的高度差2。這種不平衡可能出現在下面這四種情況：

1）對α的左兒子的左子樹進行一次插入（左旋）

其中D是新插入的節點，紅色節點K2是失去平衡的節點。需要對K1和K2進行左旋調整即將K1作為根，將K2作為K1的左子樹，K1的右子樹調整為K2的左子樹。如下圖所示

進行左旋變換

代碼如下：

[cpp] view plaincopystatic Position SingleRotateWithLeft(Position K2) { Position K1; K1 = K2->Left; K2->Left = K1->Right; K1->Right = K2; //更新節點的高度 return K1; }

2）對α的左兒子的右子樹進行一次插入（左右雙旋）

左右雙旋這里的左右指的是對α的左兒子的右子樹進行插入時需要旋轉。先對K1和K2進行右旋（跟第四種情況類似），然后再對K3和K2進行左旋，最終實現平衡。如下圖所示

進行一次右旋進行一次左旋

代碼如下：

[cpp] view plaincopystatic Position DoubleRotateWithLeft(Position K3) { K3->Left = SingleRotateWithRight(K3->Left); return SingleRotateWithLeft(K3); }

3）對α的右兒子的左子樹進行一次插入（右左雙旋）

右左雙旋：先對K1和K2進行左旋，然后在對K2和K3進行右旋，最終實現平衡。如下圖所示

進行一次左旋進行一次右旋

代碼如下：

[cpp] view plaincopystatic Position DoubleRotateWithRight(Position K3) { K3->Right = SingleRotateWithLeft(K3->Right); return SingleRotateWithRight(K3); }

4）對α的右兒子的右子樹進行一次插入（右旋）

將K2的右子樹更改為K1的左子樹，K1的左子樹更改為K2即完成的右旋，如下圖所示

進行右旋

代碼如下：

[cpp] view plaincopystatic Position SingleRotateWithRight(Position K2) { Position K1; K1 = K2->Right; K2->Right = K1->Left; K1->Left = K2; //更新節點高度 return K1; } 上面講述了AVL樹四種旋轉情況，下面來實現一下AVL樹。AVL樹的實現跟上一章講的二叉查找樹相似，區別在于在插入和刪除節點是需要對樹進行調整以滿足平衡條件。

avltree.h給出函數聲明

[cpp] view plaincopytypedef int ElementType; #ifndef AVLTREE_H #define AVLTREE_H struct TreeNode { ElementType Element; int Height; struct TreeNode *Left; struct TreeNode *Right; }; typedef struct TreeNode *AvlTree; typedef struct TreeNode *Position; AvlTree MakeEmpty(AvlTree T); AvlTree Insert(ElementType X, AvlTree T); Position Find(ElementType X ,AvlTree T); Position FindMax(AvlTree T); Position FindMin(AvlTree T); #endif avltree.c函數實現[cpp] view plaincopy#include "fatal.h" #include "avltree.h" AvlTree MakeEmpty(AvlTree T) { if(T != NULL) { MakeEmpty(T->Left); MakeEmpty(T->Right); free(T); } return NULL; } static int Height(Position P) { if(P == NULL) return -1; else return P->Height; } static int Max(int Lhs, int Rhs) { return Lhs > Rhs ? Lhs : Rhs; } static Position SingleRotateWithLeft(Position K2) { Position K1; K1 = K2->Left; K2->Left = K1->Right; K1->Right = K2; K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1; K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1; return K1; } static Position SingleRotateWithRight(Position K2) { Position K1; K1 = K2->Right; K2->Right = K1->Left; K1->Left = K2; K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1; K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1; return K1; } static Position DoubleRotateWithLeft(Position K3) { K3->Left = SingleRotateWithRight(K3->Left); return SingleRotateWithLeft(K3); } static Position DoubleRotateWithRight(Position K3) { K3->Right = SingleRotateWithLeft(K3->Right); return SingleRotateWithRight(K3); } AvlTree Insert(ElementType X, AvlTree T) { if(T == NULL) { T = (Position)malloc(sizeof(struct TreeNode)); if(T == NULL) FatalError("Out of space"); T->Element = X; T->Height = 0; T->Left = T->Right = NULL; } else if(X < T->Element)//左子樹插入新節點 { T->Left = Insert(X, T->Left); if(Height(T->Left) - Height(T->Right) == 2)//左子樹插入節點所以高度是左子樹高于右子樹 { if(X < T->Left->Element)//對α的左兒子的左子樹進行一次插入，需要左旋 T = SingleRotateWithLeft(T); else //對α的左兒子的右子樹進行一次插入，需要雙旋 T = DoubleRotateWithLeft(T); } } else if(X > T->Element)//右子樹插入新節點 { T->Right = Insert(X, T->Right); if(Height(T->Right) - Height(T->Left) == 2)//因為是右子樹插入新節點，所以高度是右子樹高于左子樹 { if(X > T->Right->Element)//對α的右兒子的右子樹進行一次插入，需要右旋 T = SingleRotateWithRight(T); else//對α的右兒子的左子樹進行一次插入，需要雙旋 T = DoubleRotateWithRight(T); } } T->Height = Max(Height(T->Left), Height(T->Right)) + 1; return T; } Position Find(ElementType X, AvlTree T) { if(T == NULL) return NULL; if(X < T->Element) return Find(X, T->Left); else if(X > T->Element) return Find(X, T->Right); else return T; } Position FindMin(AvlTree T) { if(T == NULL) return NULL; else if(T->Left == NULL) return T; else return FindMin(T->Left); } Position FindMax(AvlTree T) { if(T == NULL) return NULL; else if(T->Right == NULL) return T; else return FindMax(T->Right); }

testavl.c測試AVL樹的實現

[cpp] view plaincopy#include "avltree.h" #include #include void InOrder(AvlTree T) { if(T != NULL) { InOrder(T->Left); 測試：首先插入1到7，然后插入16到10，最后插入8和9。AVL樹的應該為下圖所示