请教一行程序（红黑树删除）

keithnwsuaf_cu

此函数是红黑树的删除实现，tree->parents的类型是TREE_ELEMENT **parents[n]，TREE_ELEMENT为树种节点的类型。

int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
{
  int cmp,remove_colour;
  TREE_ELEMENT *element,***parent, ***org_parent, *nod;
  if (!tree->with_delete)
    return 1;                                        /* not allowed */

  parent= tree->parents;
  *parent= &tree->root; element= tree->root;
  for (;
  {
    if (element == &tree->null_element)
      return 1;                                /* Was not in tree */
    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
                                key)) == 0)
      break;
    if (cmp < 0)
    {
      *++parent= &element->right; element= element->right;
    }
    else
    {
      *++parent = &element->left; element= element->left;
    }
  }
  if (element->left == &tree->null_element)
  {
    (**parent)=element->right;
    remove_colour= element->colour;
  }
  else if (element->right == &tree->null_element)
  {
    (**parent)=element->left;
    remove_colour= element->colour;
  }
  else
  {
    org_parent= parent;
    *++parent= &element->right; nod= element->right;
    while (nod->left != &tree->null_element)
    {
      *++parent= &nod->left; nod= nod->left;
    }
    (**parent)=nod->right;                /* unlink nod from tree */
    remove_colour= nod->colour;
    org_parent[0][0]=nod;                /* put y in place of element */
    org_parent[1]= &nod->right;//这一行是什么意思啊？干什么用的啊？谢谢
    nod->left=element->left;
    nod->right=element->right;
    nod->colour=element->colour;
  }
  if (remove_colour == BLACK)
    rb_delete_fixup(tree,parent);
  if (tree->free)
    (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
  tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
  my_free(element);
  tree->elements_in_tree--;
  return 0;
}

shang2010

你是哪家公司的？还是在读书？？？

hengshan

回复 1# keithnwsuaf_cu


    找《算法导论》看看，时间久了，忘记了

keithnwsuaf_cu

这个和公司应该没有关系吧？

算法导论看了，我感觉那一行逻辑上不对。org_parent[0][0]=nod；已经使nod节点取代了要删除到节点

comoon

回复 4# keithnwsuaf_cu


    你看的是中文的？第几版的？中文的翻译印刷错误较多。。。。最好看英文版的，而且那书1 。2版上确实有些错误，3纠正了很多！你找本英文3版的再看看吧！

   而且你那代码应该不是书上的吧，算法导论上面的代码都是逻辑代码，没有具体到语言实现的。。。你那明显是C。。。

keithnwsuaf_cu

谢谢楼上，翻译书害人啊