函數重新平衡二叉搜索樹

Question

我正在實施二叉搜索樹。完成實施所需的功能之一是重新平衡功能。

根據功能的工作方式如下規格：

的再平衡（）方法應該建立一個平衡樹，從而減少偏度到零。平衡樹是其中左右子樹的大小在整個樹中相差不超過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

您沒有按照規格正確操作。首先，您的rebalance操作會增加樹的大小。另一方面，結果並不總是二叉搜索樹。

在嘗試實施這些樹之前，您必須瞭解這些樹是如何工作的。那是沒有辦法的。我建議你研究你的文本（或wikipedia），並嘗試用鉛筆和紙張構建和平衡一些樹木。