二叉搜索樹;自組織搜索/旋轉C++

對於我的項目，我將創建一個自組織二進制搜索樹。我已經成功創建了BST，但由於某種原因，我無法弄清楚如何實現組織部分。二叉搜索樹;自組織搜索/旋轉C++

更具體地說，當我執行一個值的搜索時，我將增加它的搜索計數。一旦搜索計數等於「Thresh保持值」（通過構造函數設置），我將搜索到的節點向上旋轉一個。

我相信我能弄清楚如何進行旋轉，但我的問題出在整型變量SEARCHCOUNT和threshVal。出於某種原因，我無法弄清楚如何獲得SEARCHCOUNT僅增加與所搜索的價值，當我尋找新的價值

例如復位：我有「1 2 3 4 5」在我的BST。我執行搜索的值「3」，我發現它，將搜索計數增加爲1.然後，我執行另一次搜索，這次的值爲「5」。然後searchCount變量再次增加到2，因爲我搜索了一個不同的值，所以它應該是1。

這是我的搜索功能。這是一個很大的.cpp文件，所以我只包含一個函數。

template <typename T> 
bool BST<T>::contains(const T& v, BSTNode *&t) 
{ 
    if (t == nullptr) 
     return false; 
    else if(v < t->data) 
     return contains(v, t->left); 
    else if(t->data < v) 
     return contains(v, t->right); 
    else{ 

     if(t->right == nullptr) 
      return true; 
     /* 
      Problem lies in the following segment, I just added the little 
      rotation portion to try and get something to work for testing 
      purposes. The problem still lies with threshVal and searchCount 
     */ 
     if (searchCount == threshVal){ 
      BSTNode *temp = t->right; 
      t->right = temp->left; 
      temp->left = t; 
      t = temp; 

      if(t == root) 
       searchCount = 0; 
     } 
     return true; 
    } 
}

如果我需要給你們更多的信息，或者可能添加.cpp文件的其餘部分讓我知道。謝謝！

來源

2015-04-01 mrwigglesworth

我建議你在互聯網上搜索「平衡二叉樹」。這可能非常接近你想要達到的目標。 – 2015-04-01 19:47:31

我不能添加評論，但你嘗試給每個節點自己的int數？

例如：

struct treeNode 
    { 
     treeNode* left; 
     treeNode* right; 
     T data; 
     treeNode() {left = NULL; right = NULL;}; 
     treeNode(const T&v, treeNode* l, treeNode* r){data = v; left = l; right = r;}; 
int count = 0; 
    };

當搜索進行遞增。然後該節點的單獨計數？

來源

2015-04-01 18:53:58 TheDude1142

然後當5被搜索並發現你增加節點的數量。當該計數等於計數閾值時，然後旋轉它。 – TheDude1142 2015-04-01 18:55:54

二叉搜索樹;自組織搜索/旋轉C++

回答

相關問題