一千萬個為什麽

搜索

創建一個自我排序的二叉樹

我有一個任務,我需要使用二叉搜索樹並將其自行更改為自我排序,以便訪問最多(優先級較高)的項目位於樹頂部,根是訪問最多的節點。

教授給了我BST和節點結構來處理,但試圖讓我的頭腦圍繞算法更新樹,因為插入的東西令我感到困惑。

我知道,隨著插入的發生,它會檢查當前節點的數據是否小於或大於當前節點,然後遞歸地朝正確的方向前進,直到找到空指針並將其插入到那裏。並且在插入之後它將優先級提高1。

template 
void BinarySearchTree ::  insert( const Type & x, BinaryNode * & t )
{
    if( t == NULL )
        t = new BinaryNode( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++; //Duplicate; do nothing for right now
}

現在我需要弄清楚節點何時相等,如何重新排序樹,以便當前節點(等於已存在的節點)找到現有節點,增加該節點的優先級,然後如果根是一個較低的優先級。

我認為我有這樣的想法,即AVL邏輯可以工作,並且當發生轉變時,它將是一個單旋轉右旋或左旋單旋轉。

這是我很困惑的地方,真的不知道從哪裏開始創建算法來解決問題。由於AVL算法跟蹤樹的平衡,然後相應地左右旋轉節點,因此該樹不必擔心被平衡,只是具有最高優先級的節點不具有具有更高優先級的子節點。

最佳答案

只是兩個指針:

  1. 如果你想實際結合優先級隊列和二叉搜索樹的想法,考慮在一個結構中結合堆和BST。
  2. 自組織列表的概念。這個想法是將最近訪問的元素移動到(或走向)前面,以便加速未來對同一元素的訪問,從而隨時間“學習”元素分布(質量取決於具體實現)。也許你可以適應這些樹木?

Spoiler: Follow below links only if you have not been able to come up with something yourself.

1.這稱為搜索
 2. Splay樹實現這個想法。

轉載註明原文: 創建一個自我排序的二叉樹