从平衡二叉搜索树中删除

我想从平衡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

从平衡二叉搜索树中删除

回答

相关问题