二叉查找树

Question

我正在努力实现二叉搜索树。完成实现所需的功能之一是重新平衡功能。

根据规范，该功能的工作方式如下:

rebalance（） 方法应创建一个平衡树，从而将偏度降低为零。平衡树是指在整个树中，左子树和右子树的大小相差不超过1（即，每个子树也是平衡的）。

为了平衡树，rebalance（） 方法应反复将根值移动到较小的子树，并将最小/最大值从较大的子树移动到根，直到树平衡。然后，它应该以递归方式平衡两个子树。

到目前为止，我有以下代码:

    struct treeNode {
    Type value;
    int count;
    treeNode* left;
    treeNode* right;
    };
    treeNode* root;

template <class Type>
void bstree<Type>::rebalance(treeNode* sroot){

    if (root == NULL) {
        throw new underflow_error("tree is empty");
    }

    while (skewness(sroot) != 0)
    {
        if (size(sroot->left) < size(sroot->right))
        {
            sroot->left.insert(sroot->value);
            sroot->left.insert(max(sroot->right));
            sroot->left.insert(min(sroot->right));

        }
        else
        {
            sroot->right.insert(sroot->value);
            sroot->left.insert(max(sroot->left));
            sroot->left.insert(min(sroot->left));
        }
    }

    rebalance(sroot->left);
    rebalance(sroot->right);
}

我不知道我是否正确地遵循了规范。我能得到一些见解或建议，比如我可能做错了什么吗？

Answer 1

您没有正确遵循规格。首先，您的再平衡操作会增加树的大小。另一方面，结果并不总是二叉搜索树。

在尝试实现这些树之前，您必须了解它们是如何工作的。这是没有办法的。我建议你研究你的文本（或维基百科），尝试用铅笔和纸构建和平衡一些树。