2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(20)

　　更多：2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理匯總

　　24、平衡二叉樹(shù)

　　(1)定義：平衡二叉樹(shù)又被稱(chēng)為AVL樹(shù)(區(qū)別于A(yíng)VL算法)，它是一棵二叉排序樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

　　(2)構(gòu)造與調(diào)整方法

　　平衡二叉樹(shù)的常用算法有紅黑樹(shù)、AVL、Treap、伸展樹(shù)、左偏樹(shù)等。

　　紅黑樹(shù)：紅黑樹(shù)是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由Rudolf Bayer發(fā)明的，他稱(chēng)之為"對(duì)稱(chēng)二叉B樹(shù)"，它現(xiàn)代的名字是在 LeoJ. Guibas 和 RobertSedgewick 于1978年寫(xiě)的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的: 它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除，這里的n是樹(shù)中元素的數(shù)目。

　　AVL：AVL是最先發(fā)明的自平衡二叉查找樹(shù)算法。在A(yíng)VL中任何節(jié)點(diǎn)的兩個(gè)兒子子樹(shù)的高度最大差別為一，所以它也被稱(chēng)為高度平衡樹(shù)。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。

　　Treap：Treap是一棵二叉排序樹(shù)，它的左子樹(shù)和右子樹(shù)分別是一個(gè)Treap，和一般的二叉排序樹(shù)不同的是，Treap紀(jì)錄一個(gè)額外的數(shù)據(jù)，就是優(yōu)先級(jí)。Treap在以關(guān)鍵碼構(gòu)成二叉排序樹(shù)的同時(shí)，還滿(mǎn)足堆的性質(zhì)(在這里我們假設(shè)節(jié)點(diǎn)的優(yōu)先級(jí)大于該節(jié)點(diǎn)的孩子的優(yōu)先級(jí))。但是這里要注意的是Treap和二叉堆有一點(diǎn)不同，就是二叉堆必須是完全二叉樹(shù)，而Treap可以并不一定是。

　　伸展樹(shù)：伸展樹(shù)(Splay Tree)是一種二叉排序樹(shù)，它能在O(log n)內(nèi)完成插入、查找和刪除操作。它由Daniel Sleator和Robert Tarjan創(chuàng)造。它的優(yōu)勢(shì)在于不需要記錄用于平衡樹(shù)的冗余信息。在伸展樹(shù)上的一般操作都基于伸展操作。

　　左偏樹(shù)：堆結(jié)構(gòu)是一種隱式數(shù)據(jù)結(jié)構(gòu)(implicit data structure)，用完全二叉樹(shù)表示的堆在數(shù)組中是隱式存貯的(即沒(méi)有明確的指針或其他數(shù)據(jù)能夠重構(gòu)這種結(jié)構(gòu))。由于沒(méi)有存貯結(jié)構(gòu)信息，這種描述方法空間利用率很高，事實(shí)上沒(méi)有空間浪費(fèi)。盡管堆結(jié)構(gòu)的時(shí)間和空間效率都很高，但它不適合于所有優(yōu)先隊(duì)列的應(yīng)用，尤其是當(dāng)需要合并兩個(gè)優(yōu)先隊(duì)列或多個(gè)長(zhǎng)度不同的隊(duì)列時(shí)。因此需要借助于其他數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這類(lèi)應(yīng)用，左偏樹(shù)(leftist tree)就能滿(mǎn)足這種要求。

　　(3)平衡二叉樹(shù)

　　為了保證二叉排序樹(shù)的高度為lgn，從而保證然二叉排序樹(shù)上實(shí)現(xiàn)的插入、刪除和查找等基本操作的平均時(shí)間為O(lgn)，在往樹(shù)中插入或刪除結(jié)點(diǎn)時(shí)，要調(diào)整樹(shù)的形態(tài)來(lái)保持樹(shù)的"平衡。使之既保持BST性質(zhì)不變又保證樹(shù)的高度在任何情況下均為O(lgn)，從而確保樹(shù)上的基本操作在最壞情況下的時(shí)間均為O(lgn)。

　　注意：

　�、倨胶舛�叉樹(shù)(BalancedBinary Tree)是指樹(shù)中任一結(jié)點(diǎn)的左右子樹(shù)的高度大致相同。

　　②任一結(jié)點(diǎn)的左右子樹(shù)的高度均相同(如滿(mǎn)二叉樹(shù))，則二叉樹(shù)是完全平衡的。通常，只要二叉樹(shù)的高度為O(1gn)，就可看作是平衡的。

　�、燮胶獾亩�叉排序樹(shù)指滿(mǎn)足BST性質(zhì)的平衡二叉樹(shù)。

　�、蹵VL樹(shù)中任一結(jié)點(diǎn)的左、右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。在最壞情況下，n個(gè)結(jié)點(diǎn)的AVL樹(shù)的高度約為1.44lgn。而完全平衡的二叉樹(shù)度高約為lgn，AVL樹(shù)是接近最優(yōu)的。

　　//AVL代碼

　　#ifndefAVL_TREE_H

　　#defineAVL_TREE_H

　　#include"dsexceptions.h"

　　#include // For NULL

　　usingnamespace std;

　　//AvlTree class

　　//

　　//CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds

　　//

　　//******************PUBLIC OPERATIONS*********************

　　//void insert( x ) --> Insert x

　　//void remove( x ) --> Remove x(unimplemented)

　　//bool contains( x ) --> Return trueif x is present

　　//Comparable findMin( ) --> Returnsmallest item

　　//Comparable findMax( ) --> Returnlargest item

　　//boolean isEmpty( ) --> Return trueif empty; else false

　　//void makeEmpty( ) --> Remove allitems

　　//void printTree( ) --> Print treein sorted order

　　//******************ERRORS********************************

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)