查找二叉搜索树中第 n 个最小的元素

Question

我编写了一种算法，用于在 BST 中查找第 n 个最小元素，但它返回根节点而不是第 n 个最小元素。因此，如果您按顺序输入节点 7 4 3 13 21 15，则该算法在调用 find(root, 0) 后返回值为 7 而不是 3 的 Node，而对于调用 find(root, 1) 则返回 13 而不是 4。想法？

Binode* Tree::find(Binode* bn, int n) const
{
    if(bn != NULL)
    {

    find(bn->l, n);
    if(n-- == 0)
        return bn;    
    find(bn->r, n);

    }
    else
        return NULL;
}

以及Binode的定义

class Binode
{
public:
    int n;
    Binode* l, *r;
    Binode(int x) : n(x), l(NULL), r(NULL) {}
};

Answer 1

不可能单独有效地检索二叉搜索树中的第 n 个最小元素。但是，如果您在每个节点中保留一个指示其整个子树中的节点数的整数，则这确实成为可能。来自我的通用 AVL 树实现：

static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index)
{
    if (index >= BAVL_Count(o)) {
        return NULL;
    }

    BAVLNode *c = o->root;

    while (1) {
        ASSERT(c)
        ASSERT(index < c->count)

        uint64_t left_count = (c->link[0] ? c->link[0]->count : 0);

        if (index == left_count) {
            return c;
        }

        if (index < left_count) {
            c = c->link[0];
        } else {
            c = c->link[1];
            index -= left_count + 1;
        }
    }
}

上面代码中，

node->link[0]

和

node->link[1]

是

node

的左右孩子，

node->count

是

node

整个子树的节点数。

假设树是平衡的，上述算法的时间复杂度为 O(logn)。另外，如果保留这些计数，则可以进行另一种操作 - 给定指向节点的指针，可以有效地确定其索引（与您要求的索引相反）。在我链接的代码中，此操作称为

BAVL_IndexOf()

。

请注意，随着树的更改，节点计数需要更新；这可以在时间复杂度没有（渐近）变化的情况下完成。

Answer 2

您的代码存在一些问题：

1)

find()

返回一个值（正确的节点，假设函数按预期工作），但您不会将该值传播到调用链，因此顶级调用不知道（可能）找到元素

.

Binode* elem = NULL;
elem = find(bn->l, n);
if (elem) return elem; 
if(n-- == 0) 
    return bn;     
elem = find(bn->r, n); 
return elem; // here we don't need to test: we need to return regardless of the result

2) 即使您在正确的位置减少

n

，更改也不会在调用链中向上传播。您需要通过引用传递参数（请注意函数签名中

&

后面的

int

），因此更改是在原始值上进行的，而不是在它的副本上进行的

.

Binode* Tree::find(Binode* bn, int& n) const

我尚未测试建议的更改，但它们应该会让您朝着正确的方向前进

Answer 3

我们可以使用迭代中序搜索来获取第 n 个最小的元素，如下所示：

void insert(Node*& root, int val)
{
  if(!root) {
    Node* temp = new Node(val);
    root = temp;
    return ;
  }

  if(val < root->val)
    insert(root->left,val);
  else if (val > root->val)
    insert(root->right, val);

}

// Utility function to print inorder traversal
void inorder(Node* root)
{
        Node* temp = root;
        stack<Node*> st;
        int n = 0;
        while (temp != NULL || !st.empty()) {
                if (temp != NULL) {
                        st.push(temp);
                        temp = temp->left;
                }
                else {
                        temp = st.top();
                        st.pop();
                        cout << n++ << ":" << temp->val << " ";
                        temp = temp->right;
                }
        }
}

// Driver code
int main()
{
        Node* root = NULL;
        insert(root, 30);
        insert(root, 50);
        insert(root, 15);
        insert(root, 20);
        insert(root, 10);
        insert(root, 40);
        insert(root, 60);

        // Function call to print the inorder traversal
        inorder(root);

        return 0;
}

输出：0:10 1:15 2:20 3:30 4:40 5:50 6:60