- 相關(guān)推薦
AVL樹的c語言實現(xiàn)
導語：C語言的設(shè)計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產(chǎn)生少量的機器碼以及不需要任何運行環(huán)境支持便能運行的編程語言。下面我們來看看AVL樹的c語言實現(xiàn)，希望對大家有所幫助。
AVL樹的c語言實現(xiàn)：在計算機科學中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。
1.節(jié)點
(1)節(jié)點的定義
1 2 3 4 5 6 7 8 9 | typedef int KeyType; typedef struct AvlNode { KeyType key; //數(shù)據(jù) AvlNode *leftchild; //左孩子 AvlNode *rightchild; //右孩子 AvlNode *parent; //雙親結(jié)點 int balance; //平衡因子 }AvlNode,*AvlTree; |
(2)結(jié)點的創(chuàng)建
1 2 3 4 5 6 7 8 9 10 11 12 | 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.旋轉(zhuǎn)
如果在AVL樹中進行插入或刪除節(jié)點后，可能導致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態(tài)：左單旋轉(zhuǎn)，右單旋轉(zhuǎn)，左平衡，右平衡。(1)左單旋轉(zhuǎn)：也叫左左旋轉(zhuǎn)。
【AVL樹的c語言實現(xiàn)】相關(guān)文章：
C語言程序的實現(xiàn)09-27
希爾排序（C語言實現(xiàn)）09-06
PID算法的C語言實現(xiàn)07-19
鏈表的C語言實現(xiàn)方法08-27
如何實現(xiàn)C語言畫圖教程08-08
冒泡排序（C語言實現(xiàn)）08-30
C語言如何實現(xiàn)畫圖教程08-19