2011年軟考程序員考試復習筆試知識點整理(20)

　　更多：2011年軟考程序員考試復習筆試知識點整理匯總

　　24、平衡二叉樹

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

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

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

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

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

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

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

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

　　(3)平衡二叉樹

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

　　注意：

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

　�、谌我唤Y(jié)點的左右子樹的高度均相同(如滿二叉樹)，則二叉樹是完全平衡的。通常，只要二叉樹的高度為O(1gn)，就可看作是平衡的。

　　③平衡的二叉排序樹指滿足BST性質(zhì)的平衡二叉樹。

　　④AVL樹中任一結(jié)點的左、右子樹的高度之差的絕對值不超過1。在最壞情況下，n個結(jié)點的AVL樹的高度約為1.44lgn。而完全平衡的二叉樹度高約為lgn，AVL樹是接近最優(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********************************

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

　　2011年上半年軟考報名時間及方式匯總

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