c - 从平衡二叉搜索树中删除

Question

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

Answer 1

从平衡二叉树中删除的一种方法是创建函数balance()。这将用于重新平衡树。将二叉树中元素的引用指针复制到按顺序排列的列表中。然后找到列表的中间元素(将列表分为两半)。它将成为您的新根节点。根节点的左子节点将位于列表左半部分的中间，根节点的右子节点将位于列表右半部分的中间。递归地执行此操作以创建平衡树。现在在删除过程中使用此功能。在找到要删除的节点时，跟踪其父节点。现在像 BST 的情况一样构建删除逻辑，但在需要时使用这个balance()函数来重新平衡树。来源:http://www.codeproject.com/Articles/68500/Balanced-Binary-Search-Tree-BST-Search-Delete-InOr

我不确定你如何保持树平衡，但另一种更简单的方法是实现自平衡二叉搜索树，如 AVL 或 R-B 树。