AVL樹的c語言實現
導語：C語言的設計目標是提供一種能以簡易的方式編譯、處理低階儲存器、產生少量的機器碼以及不需要任何執行環境支援便能執行的程式設計語言。下面我們來看看AVL樹的c語言實現，希望對大家有所幫助。
AVL樹的c語言實現：在計算機科學中，AVL樹是最先發明的自平衡二元搜尋樹。在AVL樹中任何節點的.兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查詢、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。
1.節點
(1)節點的定義
| 123456789 | typedef int KeyType; typedef struct AvlNode { KeyType key; //資料 AvlNode *leftchild; //左孩子 AvlNode *rightchild; //右孩子 AvlNode *parent; //雙親結點 int balance; //平衡因子 }AvlNode,*AvlTree; |
(2)結點的建立
| 123456789101112 | AvlNode *BuyNode() { AvlNode *p =(AvlNode *)malloc(sizeof(AvlNode)); if( p != NULL) { p->leftchild = NULL; p->rightchild = NULL; p->parent = NULL; p->balance = 0; } return p; } |
2.旋轉
如果在AVL樹中進行插入或刪除節點後，可能導致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態：左單旋轉，右單旋轉，左平衡，右平衡。(1)左單旋轉：也叫左左旋轉。
