滿二叉樹

定義

對于國內(nèi)的滿二叉樹

從圖形形態(tài)上看，滿二叉樹外觀上是一個三角形。

從數(shù)學(xué)上看，滿二叉樹的各個層的結(jié)點數(shù)形成一個首項為1，公比為2的等比數(shù)列。

因此由等比數(shù)列的公式，滿二叉樹滿足如下性質(zhì)。

1、一個層數(shù)為k 的滿二叉樹總結(jié)點數(shù)為：。因此滿二叉樹

的結(jié)點數(shù)一定是奇數(shù)個。

2、第i層上的結(jié)點數(shù)為：

3、一個層數(shù)為k的滿二叉樹的葉子結(jié)點個數(shù)（也就是最后一層）：

對于國外的滿二叉樹

滿二叉樹的結(jié)點要么是葉子結(jié)點，度為0，要么是度為2的結(jié)點，不存在度為1的結(jié)點。

因此，圖3中這個二叉樹也是滿二叉樹。但是按照國內(nèi)的定義，它卻不是滿二叉樹。

美國以及國際上所定義的滿二叉樹，即full binary tree,和國內(nèi)的定義不同，美國NIST給出的定義為：A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

滿二叉樹的任意節(jié)點，要么度為0，要么度為2.換個說法即要么為葉子結(jié)點，要么同時具有左右孩子?；舴蚵鼧涫欠线@種定義的，滿足國際上定義的滿二叉樹，但是不滿足國內(nèi)的定義。1

基于滿二叉樹的原地快速排序

一種基于滿二叉樹的原地快速排序算法。 與經(jīng)典快速排序算法相比, 新算法每趟劃分采用動態(tài)樞軸而不是靜態(tài)樞軸, 同時新算法利用滿二叉樹的特點計算下一趟劃分的樞軸位置和元素范圍, 避免使用遞歸或開辟內(nèi)存堆棧。 實驗表明, 新算法的時間性能優(yōu)于最好的原地排序—堆排序。 原地快速排序二叉樹的概念對排序算法的研究和改進具有很好的理論和實用參考價值。

給定一個長度為m的順序表 ,每個元素由一個關(guān)鍵字和其他的相關(guān)信息構(gòu)成 , 排序算法的任務(wù)就是根據(jù)關(guān)鍵字以非降序(或非升序)重新安排數(shù)組中的元素(不失一般性, 以下我們按非降序排序)。排序算法僅允許做關(guān)鍵字比較和元素移動操作, 并用關(guān)鍵字比較次數(shù)和元素移動次數(shù) ,衡量排序算法的時間性能和空間性能 。如果一個算法所使用的額外空間是一個固定常數(shù) ,與處理問題的規(guī)模無關(guān) ,則我們稱該算法是原地的?？焖倥判蛩惴ㄊ亲詈玫呐判蛩惴ㄖ? 它的基本思想是通過若干次劃分得到有序表。一次劃分后樞軸左邊元素的關(guān)鍵字都不大于樞軸的關(guān)鍵字, 樞軸右邊元素的關(guān)鍵字都不小于樞軸的關(guān)鍵字 。然后對樞軸左邊和右邊的元素繼續(xù)劃分 ,直到每個部分都只有1個元素為止。經(jīng)典快速排序或用遞歸函數(shù)實現(xiàn)或自己開辟內(nèi)存堆棧實現(xiàn),需要的額外空間, 都不是嚴(yán)格意義上的原地算法 。在本文中 ,將滿二叉樹的概念引入快速排序中, 利用滿二叉樹的特點計算下一趟劃分的樞軸位置和元素范圍 ,避免了使用遞歸或開辟內(nèi)存堆棧 ,從而將快速排序改造成嚴(yán)格原地的。實驗表明, 該算法的時間性能優(yōu)于最好的原地排序 —堆排序。

二分K-means聚類并行推薦算法

在推薦系統(tǒng)中應(yīng)用K-means算法聚類可有效降維，然而聚類效果往往依賴于選定的初始中心，并且一旦選定目標(biāo)簇后，推薦過程只針對目標(biāo)簇進行，與其他簇?zé)o關(guān)。針對上述兩個問題，提出一種基于滿二叉樹的二分K-means聚類并行推薦算法。該算法首先反復(fù)迭代二分K-means算法，迭代過程中使用簇內(nèi)凝聚度作為分裂閾值，形成一顆滿二叉樹；然后通過層次遍歷將用戶歸入到K個葉子節(jié)點（簇）；最后針對K個簇，應(yīng)用MapReduce框架進行并行推薦預(yù)測。MovieLens上的實驗結(jié)果表明，該算法可大幅度提高推薦系統(tǒng)準(zhǔn)確性，同時增強系統(tǒng)可擴展性。2

基于滿二叉樹的RA碼交織器設(shè)計

為提高輸入信息較長時重復(fù)累積碼的編碼效率，對重復(fù)累積碼的交織器進行優(yōu)化改進。按照滿二叉樹子節(jié)點的奇偶排列方式對交織器的輸入序列依次分組，并利用葉子節(jié)點對分組信息重新組合獲得輸出序列，與S隨機交織器相比，大大降低輸入信息之間的相關(guān)性，避免了RA碼校驗矩陣中I、II類4環(huán)的產(chǎn)生，保證了譯碼的準(zhǔn)確性。仿真結(jié)果表明，在輸入信息序列較長時，改進的交織器編碼速度快且誤碼率遠(yuǎn)低于行列規(guī)則交織器；與S隨機交織器相比，改進的交織器可以顯著提高編碼速率，且在誤碼率同為時約有0.3dB的增益。3