從平衡二叉搜索樹中刪除

我想從平衡BST中刪除一個節點。我寫了下面的代碼，它在刪除一個孩子時起作用，但是當我想用兩個孩子刪除一個節點時，鏈接被恢復，但是我失去了另一個節點。這是我的代碼：從平衡二叉搜索樹中刪除

Nod* minValue(Nod *p) 
{ 
    Nod *q = p; 

    while (q->stg != NULL) 
     q = q->stg; 

    return q; 
} 

Nod* os_delete(Nod *p, int k) 
{ 
    if (p == NULL) 
     return p; 

    if (k < p->ch) 
    { 
    p->stg = os_delete(p->stg, k); 
    } 

    else if (k > p->ch) 
    { 
    p->dr = os_delete(p->dr, k); 
    } 

    else 
    { 
     p->size--; 
     if (p->stg = NULL) 
     { 
      Nod* aux = p->dr; 
      free(p); 
      return aux; 
     } 
     else if (p->dr == NULL) 
     { 
      Nod* aux = p->stg; 
      free(p); 
      return aux; 
     } 

     Nod* aux = minValue(p->dr); 
     p->ch = aux->ch; 
     p->dr = os_delete(p->dr, aux->ch); 
    } 
    return p;

}

例如：

  9 
    4   15 
1  7 10  18

如果我想用鍵4，刪除節點，結果樹將是：

 9 
7   15 
      10  18

編輯：

typedef struct nod 
{ 
    int ch, size; // ch - key of the node; size - size of node's subtree 
    struct nod *stg, *dr; // stg - left; dr - right 
}Nod;

來源

2016-04-14 Altair2033

[二進制搜索樹中的刪除]可能有重複（http://stackoverflow.com/questions/7606185/deletion-in-binary-search-tree） – EOF

s/childs/children /。 :-) –

'Nod'結構/類是什麼樣的？ –

從平衡二叉樹中刪除的一種方法是創建一個函數balance（）。這將用於重新平衡樹。將二叉樹中元素的引用指針複製到Inorder中的列表中。然後找到列表的中間元素（將列表分成兩部分）。這將是你的新根節點。根節點的左側子節點將位於列表左半部分的中間，根節點的右側子節點將位於列表的右半部分的中間位置。以遞歸方式執行此操作以創建平衡樹。現在在刪除過程中使用此功能。找到要刪除的節點時，請跟蹤它的父節點。現在就像在BST的情況下一樣構建刪除邏輯，但是使用這個balance（）函數來根據需要重新平衡樹。來源：http://www.codeproject.com/Articles/68500/Balanced-Binary-Search-Tree-BST-Search-Delete-InOr

我不知道你如何努力保持樹平衡，但另一種更簡單的方法是實現自平衡二叉搜索樹，如AVL或R-B樹。

來源

2016-04-15 05:14:38

從平衡二叉搜索樹中刪除

回答

相關問題