二叉搜索树；自组织 Search/Rotation C++

Question

对于我的项目，我要创建一个自组织二叉搜索树。我已经成功创建了 BST，但出于某种原因我不太清楚如何实现组织部分。

更具体地说，当我执行一个值的搜索时，我将增加它的搜索计数。一旦搜索计数等于 "Thresh hold Value"（通过构造函数设置），我将搜索到的节点向上旋转一个。

我相信我可以弄清楚如何执行旋转，但我的问题在于整数变量 searchCount 和 threshVal。出于某种原因，我无法弄清楚如何让 searchCount 只随搜索到的值递增，并在搜索新值时重置

例如：我的 BST 中有“1 2 3 4 5”。我搜索值“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 文件的其余部分，请告诉我。谢谢！

Answer 1

我无法添加评论，但您是否尝试过为每个节点提供自己的 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;
    };

然后在进行搜索时增加该节点的个体计数？

二叉搜索树；自组织 Search/Rotation C++

Binary Search Tree; Self Organizing Search/Rotation C++

c++

search

binary-search-tree