二叉搜索树;自组织搜索/旋转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++

回答

相关问题