××××××××特别声明×××××××

本文含有大量技术细节，请无技术背景者在专业人员指导下阅读本文。

同时，请对代码不适者不要继续阅读。

××××××××××××××××××××

呃……话说昨天那个很傻的代码不但效率低下，还有一个逻辑错误……唉，不得不说，CLRS的代码实在是太精辟了，完全就是经典级别的（这不是废话么……）。刚才的代码，完全就是CLRS伪代码的具体实现过程……不知道回头我看完了TAOCP以后，会不会也有这种高山仰止的感觉。

先说一下，昨天的两个问题，一个是，堆栈的存在毫无必要，因为，我们需要的父节点只有一个，就是需要移除的Y的父节点，而那个堆栈记录了全部的路径信息，太浪费。同时，我昨天抄CLRS的时候，抄的不认真，导致了一个bug，就是要删除的根节点，我那个会无论根节点是否有孩子，都直接返回一个空节点……

好，先代码再解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <stdlib.h>
#include <stdio.h>
 
 
typedef struct tREE{
      int data;
      struct tREE* left;
      struct tREE* right;
}Tree;
 
 
Tree* delete(Tree *root, int data)
{
      Tree *z=NULL;
      Tree *y=NULL;
      Tree *x=NULL;
      Tree *p=NULL;
 
      if (root==NULL)
      {
            printf("EMPTY TREE\n");
            return NULL;
      }
 
      z=root;
 
      while (z!=NULL)
      {
            if (z->data==data)
                  break;
            p=z;
            if (z->data>data)
                  z=z->left;
            else
                  z=z->right;
      }
 
      if (z==NULL)
      {
            printf ("NO SUCH ELEMENT\n");
            return root;
      }
 
      else
      {
            if (z->left==NULL || z->right==NULL)
                  y=z;
            else
            {
                  p=z;
                  y=z->right;
                  while (y->left!=NULL)
                  {
                        p=y;
                        y=y->left;
                  }
            }
 
            if (y->left==NULL)
                  x=y->right;
            else
                  x=y->left;
 
            if (y!=z)
                  z->data=y->data;
 
            free (y);
 
            if (p==NULL)
                  return x;
 
            if (y==p->left)
                  p->left=x;
            else
                  p->right=x;
 
            return root;
      }
}

再贴一段CLRS的伪代码

TREE-DELETE(T, z)
 1  if left[z] = NIL or right[z] = NIL
 2      then y ← z
 3      else y ← TREE-SUCCESSOR(z)
 4  if left[y] ≠ NIL
 5      then x ← left[y]
 6      else x ← right[y]
 7  if x ≠ NIL
 8      then p[x] ← p[y]
 9  if p[y] = NIL
10      then root[T] ← x
11      else if y = left[p[y]]
12              then left[p[y]] ← x
13              else right[p[y]] ← x
14  if y ≠ z
15      then key[z] ← key[y]
16           copy y's satellite data into z
17  return y

伪代码解释在这里

In lines 1-3, the algorithm determines a node y to splice out. The node y is either the input node z (if z has at most 1 child) or the successor of z (if z has two children). Then, in lines 4-6, x is set to the non-NIL child of y, or to NIL if y has no children. The node y is spliced out in lines 7-13 by modifying pointers in p[y] and x. Splicing out y is somewhat complicated by the need for proper handling of the boundary conditions, which occur when x = NIL or when y is the root. Finally, in lines 14-16, if the successor of z was the node spliced out, y’s key and satellite data are moved to z, overwriting the previous key and satellite data. The node y is returned in line 17 so that the calling procedure can recycle it via the free list. The procedure runs in O(h) time on a tree of height h.

——Introduction to Algorithms,12.3 Insertion and deletion

接下来是我的代码简单说明，

10-17，定义变量，名称抄袭自CLRS，p用来标记y的父节点

19-23，空树，返回

27-36，定位z

38-42，要删除的元素不存在

46-57，对应CLRS伪代码的1-3行

59-62，对应4-6行

64-65，对应14-16行

67，偷偷提前释放了空间
= =#
这样貌似不是常规操作方式，不知道有没有问题。

69-70，对应9-10行

72-75，对应11-13行

77返回。

特别强调下，CLRS的伪代码里的7，8两行我这里没有相对应的代码，因为，我的数据结构里没有父节点。

其实我还扯了更多