次優(yōu)二叉查找樹(shù)（次優(yōu)查找樹(shù))-遞歸和非遞歸實(shí)現(xiàn)

1. 前言

當(dāng)有序表中的各記錄的查找概率相等的時(shí)候，采用折半查找效率可以提升查找性能；如果有序表中的各記錄的查找概率不相等，那么折半查找就不再適用。

如果只考慮查找成功的情況，則使查找性能達(dá)到最佳性能的判定樹(shù)就是帶權(quán)路徑長(zhǎng)度的之和,也即路徑各個(gè)記錄的查找深度與查找權(quán)值的乘積之和，當(dāng)這個(gè)和取得最小值的時(shí)候。
$$PH=\Sigma c_i?w_i,i\in (\mathrm{1....}n)$$
最優(yōu)二叉查找樹(shù)需要利用到動(dòng)態(tài)規(guī)劃的相關(guān)知識(shí)，之前的文章有所涵蓋，有興趣的讀者可查閱之前的文章進(jìn)行理解。本文所闡述的方法，采用的是貪婪的編程思維，構(gòu)建出次優(yōu)二叉查找樹(shù)(Nearly optimal binary search tree)。

2. 問(wèn)題分析

已知一個(gè)按照關(guān)鍵有序的記錄:

(r_l,r_l+1…r_h)

其中關(guān)鍵字為升序排列，對(duì)于每個(gè)記錄的權(quán)值

(w_l,w_l+1…w_h)

現(xiàn)在構(gòu)造一顆二叉樹(shù)，是這顆二叉樹(shù)的帶權(quán)路徑長(zhǎng)度PH在同樣的二叉樹(shù)中近似最小，我們稱這類二叉樹(shù)為次優(yōu)二叉樹(shù)。

利用貪婪方法，構(gòu)造次優(yōu)查找樹(shù)的方法是：首先在序列l(wèi)…h(huán)構(gòu)造根節(jié)點(diǎn)root(i)，使根節(jié)點(diǎn)左右兩顆子樹(shù)的差值取最小值，那么這個(gè)點(diǎn)就是根節(jié)點(diǎn)。采用公式，讓理解更為方便。

Δpi=|Σwj(i+1<j<h)-Σwj(l<j<i-1)|

求得i之后，然后分別對(duì)子序列(r_l,r_l+1…r_i-1)和(r_i+1,r_r+2…r_h)再分別構(gòu)造兩顆次優(yōu)二叉樹(shù)，并設(shè)定其根節(jié)點(diǎn)為root(i)，分別定位root(i)的左子樹(shù)和右子樹(shù)。

根據(jù)上面的分析，引入遞歸算法和非遞歸算法構(gòu)造次優(yōu)二叉書(shū)。

3. 遞歸算法分析

由于構(gòu)造二叉樹(shù)的過(guò)程需要分別對(duì)左右子樹(shù)進(jìn)行處理，所以整體的需要涉及兩次遞歸調(diào)用。二叉樹(shù)的構(gòu)造過(guò)程和遍歷過(guò)程非常類似，都是對(duì)左右子樹(shù)訪問(wèn)的過(guò)程。針對(duì)本問(wèn)題，我們選擇先序遍歷模式完成問(wèn)題的解答。

由于采用遞歸，那么遞歸的結(jié)束條件是什么呢？ 遞歸的結(jié)束條件就是遍歷到葉子結(jié)點(diǎn)，在本問(wèn)題當(dāng)中，可以理解問(wèn)題根節(jié)點(diǎn)的下標(biāo)等于high或者low的時(shí)候，此時(shí)遞歸就滿足結(jié)束條件（不再進(jìn)行入棧操作）。

4. 遞歸代碼C語(yǔ)言實(shí)現(xiàn)

遞歸函數(shù)的操作對(duì)象為記錄的權(quán)值和，在遞歸函數(shù)之前需要求解sw[0…n-1]，我們使用void find_sw(int *sw, SSTable st)函數(shù)完成此項(xiàng)任務(wù)。

遞歸函數(shù)中包含子樹(shù)下標(biāo)的最小值與最大值，在先序遞歸之前，通過(guò)迭代求出根節(jié)點(diǎn)所在位置，然后與high和low進(jìn)行比較，我們使用void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)函數(shù)完成這項(xiàng)任務(wù)。

a.) find_sw函數(shù)實(shí)現(xiàn),注意第1個(gè)元素的sw值為0

void find_sw(int *sw, SSTable st)
{
    int i;

    *(sw + 0) = 0;

    for (i = 1; i <= st.len; i++)
    {
        sw[i] = sw[i - 1] + st.elem[i].value;
    }
}

b.) second_optimal函數(shù)實(shí)現(xiàn)

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int low, int high)
{
   int min;
   int i;
   int j;
   int dw;
   int delta;

   min=INT_MAX;
   dw=sw[high]+sw[low-1];
   i=low;

   for(j=i;j<=high;j++)
   {
        delta=abs(dw-(sw[j]+sw[j-1]));
        if(delta<min)
        {
            i=j;
            min=delta;
        }
   }

   *bt=(BiTree)malloc(sizeof(BiTNode));
   (*bt)->data=rec[i];

   if(i==low)
   {
        (*bt)->lchild=NULL;
   }
   else
   {
        second_optimal(&((*bt)->lchild),rec,sw,low,i-1);
   }

   if(i==high)
   {
        (*bt)->rchild=NULL;
   }
   else
   {
        second_optimal(&((*bt)->rchild), rec, sw, i + 1, high);
   }
}

5. 非遞歸實(shí)現(xiàn)

為了實(shí)現(xiàn)非遞歸建立次優(yōu)二叉查找樹(shù)，就需要借助棧(stack)的概念，本質(zhì)是就是借助自定義棧來(lái)實(shí)現(xiàn)編譯器中的函數(shù)棧的管理。棧實(shí)際上儲(chǔ)存的是記憶的狀態(tài)，采用“后進(jìn)先出”模式來(lái)模擬編譯器中的函數(shù)棧。我們?cè)诶脳?shí)現(xiàn)功能之前，首先需要定義過(guò)程中需要記憶(保存)哪些參數(shù)。很明顯，對(duì)于本問(wèn)題，我們至少需要保留三個(gè)變量參數(shù)的當(dāng)前狀態(tài)，下一個(gè)待處理二叉樹(shù)結(jié)點(diǎn)的指針（它必定來(lái)自于當(dāng)前結(jié)點(diǎn)的左孩子或者右孩子），子樹(shù)需要處理的范圍，也就是low和high的下標(biāo)位置，有了這些背景分析，定義棧保存的元素：

typedef struct StackNode
{
    BiTree node;
    int    low;
    int    high;
}StackNode;

基于上述定義，非遞歸次優(yōu)二叉樹(shù)實(shí)現(xiàn)函數(shù)如下：

void second_optimal(BiTree *bt, SElemType *rec, int *sw, int len)
{
   int min;
   int i;
   int j;
   int delta;
   int dw;
   int low;
   int high;

   SqStack S;
   StackNode st_node;
   StackNode temp;

   low=1;
   high=len;
   InitStack_Sq(&S);

   st_node.low=low;
   st_node.high=high;
   st_node.node=(BiTree)malloc(sizeof(BiTNode));
   *bt = st_node.node;

   Push_Sq(&S,st_node);

   
   while(!StackEmpty_Sq(S))
   {
        Pop_Sq(&S,&temp);

        low=temp.low;
        high=temp.high;
        i=low;
        min=INT_MAX;
        dw=sw[high]+sw[low-1];

        for(j=i;j<=high;j++)
        {
            delta=abs(dw-sw[j]-sw[j-1]);

            if(delta<min)
            {
                i=j;
                min=delta;
            }
        }

        temp.node->data=rec[i];


        //it should start with from pushing the right child into the stack
        if(i==high)
        {
            temp.node->rchild=NULL;
        }
        else
        {
            st_node.low=i+1;
            st_node.high=high;
            temp.node->rchild=(BiTree)malloc(sizeof(BiTNode));
            st_node.node=temp.node->rchild;

            // here it is st_node.node instead of st_node.node->rchild
            Push_Sq(&S, st_node);
        }

        if (i == low)
        {
            temp.node->lchild = NULL;
        }
        else
        {
            st_node.low = low;
            st_node.high = i - 1;
            temp.node->lchild = (BiTree)malloc(sizeof(BiTNode));
            st_node.node= temp.node->lchild;
            // here it is st_node.node instead of st_node.node->lchild

            Push_Sq(&S, st_node);
        }
   }

}

上述函數(shù)的實(shí)現(xiàn)涉及到棧操作，有興趣的讀者可以參考《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏版自行實(shí)現(xiàn)，在此不再贅述。對(duì)于上述非遞歸代碼，請(qǐng)讀者自行理解。

6. 總結(jié)

次優(yōu)二叉查找樹(shù)是一種基于貪心算法實(shí)現(xiàn)的二叉樹(shù)，它摒棄了動(dòng)態(tài)規(guī)劃建立最優(yōu)二叉樹(shù)的繁瑣流程，同時(shí)又保留了查詢的效率。本文針對(duì)次優(yōu)二叉樹(shù)，采用遞歸和迭代兩種不同的方式加以實(shí)現(xiàn)，加深了對(duì)遞歸的理解，同時(shí)也復(fù)習(xí)了棧(stack)的相關(guān)知識(shí)。

參考資料：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-415370.html

1. 《數(shù)據(jù)結(jié)構(gòu)》-清華大學(xué)，嚴(yán)蔚敏

到了這里，關(guān)于次優(yōu)二叉查找樹(shù)（次優(yōu)查找樹(shù))_遞歸和非遞歸實(shí)現(xiàn)_20230414的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！