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