在BST中查找交換的節點

Question

我正在嘗試編寫一個程序，該程序可以檢測並打印已交換的BST中的兩個節點。

在三級樹中，我使用這種方法達到了接近解決方案的程度。

If (!AllSubTreeAreValid()) 
{ 
//Nodes swapped on same side of main root node 
} 
else 
{ 
    int max = getMax(root->left); 
    int min = getMin(root->right); 
    if(max > root->data || min < root->data) 
    { 
    //Nodes swapped on different sides of main root node 
    //Print max and min values 

    } 
else 
{ 
//No node swappped 
} 
} 

//Helper functions 
int GetMaxEle(TreeNode* tree) 
{ 
    while(tree->right!=NULL) 
    { 
     tree=tree->right; 
    } 
    return tree->info; 
} 

int GetMinEle(TreeNode* tree) 
{ 
    while(tree->left!=NULL) 
    { 
     tree=tree->left; 
    } 
    return tree->info; 
} 

但上述方法失敗時，我試圖用四級樹測試。

   20 

     15   30 

    10 17  25  33 

9 16 12 18 22 26 31 34 

在根節點15的右子樹中，12更大（違例）。

在根節點15的左子樹中，16更大（違例）。

因此，16,12是上述BST中的交換元素。我如何通過該程序找到他們？

Answer 1

的一種方法是使用一個事實，即樹的序步行將產生所有排序順序的元素。如果您可以在行走過程中檢測到排序順序的偏差，則可以嘗試找到位於錯誤位置的兩個元素。

讓我們先看看如何對一個簡單的排序數組進行操作，然後使用我們的算法構建一些可以在樹上工作的東西。直觀地說，如果我們從一個有序數組開始，然後交換兩個（不等於！）的元素，那麼我們最終會得到一些不合適的數組元素。例如，給定的陣列

1 2 3 4 5 

如果我們交換2和4，我們結束了這陣：

1 4 3 2 5 

我們如何檢測2和4在這裏換？那麼，因爲4是兩個元素中較大的一個，並且被向下交換，所以它應該大於它周圍的兩個元素。同樣，因爲換了2，它應該比它周圍的兩個元素都要小。由此，我們可以得出結論，2和4被交換。

但是，這並不總是正常工作。例如，假設我們交換1和4：

4 2 3 1 5 

在這裏，既2和1比它們的相鄰的元件越小，並且兩個4和3是比他們大。由此我們可以看出，這四個中的兩個以某種方式交換了，但不清楚我們應該交換哪些。但是，如果我們取這些值的最大值和最小值（分別爲1和4），我們最終得到交換對。

更一般地，發現該序列中被交換的元素，你想找到

• 數組中的最大局部最大值。
• 數組中最小的局部最小值。

這兩個元素不合適，應該交換。

現在，我們來思考如何將它應用到樹上。由於樹的無序行將產生兩個元素無序的排序序列，因此一種選擇是走樹，記錄我們找到的元素的順序序列，然後使用上述算法。例如，考慮你原來BST：

   20 
     /  \ 
     15    30 
    / \  / \ 
    10 17  25  33 
/| /\ /\ | \ 
9 16 12 18 22 26 31 34 

如果我們線性化到一個數組，我們得到

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34 

注意，16比其周圍的元素更大和12小於它。這立即告訴我們，12和16被交換。

因此，解決這個問題的一個簡單算法就是對樹進行一次行走，將其線性化成一個如vector或deque的序列，然後掃描該序列以找到最大的局部最大值和最小值當地最低。這將使用O（n）空間在O（n）時間內運行。一個更復雜但更節省空間的算法是一次只跟蹤三個節點 - 當前節點，它的前任和它的後繼者 - 這將內存使用量減少到O（1）。

希望這會有所幫助！

Answer 2

我猜你getMin等GetMax的工作witht樹是一個BST的假設，所以

T getMax(tree) { 
    return tree -> right == null 
    ? tree -> value 
    : getMax(tree -> right); 
} 

（或循環等價代碼）。 如果是這樣，您的代碼將檢查樹中最多三個值。即使getMax和getMin遍歷完整的樹來獲得實際的最大/最小值，您仍然只會將測試基於兩個比較。如果你想檢查你的樹滿足BST屬性，顯然你必須檢查所有的值。它足以將每個節點與其父節點進行比較。

void CheckIsBst(Tree *tree) { 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left); 
    } 
    // same with -> right, reversing <to> in the test 
} 

編輯：錯了，看評論。我相信這個是好的。

void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) { 
    if(lowerBound!= null && lowerBound -> value > tree -> Value) { 
    //violation 
    } 
    // same for upper bound, check with < 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left, lowerBound, tree); 
    } 
    // same for right, reversing comparison 
    // setting lowerBound to tree instead of upperBound 
} 

從根調用帶有空邊界來思考這個問題

Answer 3

樹遍歷templatetypedef如果你確定只有一個交換，否則，我建議根據您的初始代碼的解決方案：

int GetMax(TreeNode* tree) { 
    int max_right, max_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     max_left = GetMax(tree->left); 
     if (max_left > ret) 
      ret = max_left; 
    } 
    if (tree->right != NULL) { 
     max_right = GetMax(tree->right); 
     if (max_right > ret) 
      ret = max_right; 
    } 

    return ret; 
} 

int GetMin(TreeNode* tree) { 
    int min_right, min_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     min_left = GetMin(tree->left); 
     if (min_left < ret) 
      ret = min_left; 
    } 
    if (tree->right != NULL) { 
     min_right = GetMin(tree->right); 
     if (min_right < ret) 
      ret = min_right; 
    } 

    return ret; 
} 

void print_violations(TreeNode* tree) { 
    if ((tree->left != NULL) && (tree->right != NULL)) { 
     int max_left = GetMax(tree->left); 
     int min_right = GetMin(tree->right); 
     if (max_left > tree->data && min_right < tree->data) { 
      printf("Need to swap %d with %d\n", max_left, min_right); 
     } 
    } 
    if (tree->left != NULL) 
     print_violations(tree->left); 
    if (tree->right != NULL) 
     print_violations(tree->right); 
} 

它是慢，但它打印所有它所標識的互換。可以更改爲打印所有違規（例如，如果（max_left>樹 - >數據）打印違規）。如果您可以將兩個字段添加到TreeNode，併爲該子樹預先計算max和min，則可以提高性能。