D&F学数据结构系列—

D&F学数据结构系列——二叉排序树

二叉排序树（Binary Sort Tree）

定义:对于树中的每个结点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。

二叉查找树声明：

 1 #ifndef _Tree_H
 2 
 3 struct TreeNode;
 4 typedef struct TreeNode *Position;
 5 typedef struct TreeNode *SearchTree;
 6 
 7 SearchTree MakeEmpty(SearchTree T);
 8 Position Find(ElementType X,SearchTree T);
 9 Position FindMin(SearchTree T);
10 Position FindMax(SearchTree T);
11 SearchTree Insert(ElementType X,SearchTree T);
12 SearchTree Delete(ElementType X,SearchTree T);
13 ElementType Retrieve(Position P);
14 #endif /*_Tree_H*/

TreeNode结构体定义（二叉树的二叉链表存储表示法）：

1/*Place in the implementation file*/
2 struct TreeNode
3 {
4     ElementType Element;
5     SearchTree Left;
6     SearchTree right;
7 };

建立一棵空树：

 1 SearchTree MakeEmpty(SearchTree T)
 2 {
 3     if(T!=NULL)
 4     {
 5         MakeEmpty(T->Left);
 6         MakeEmpty(T->right);
 7         free(T);
 8     }
 9     return NULL;
10 }

Find操作：

 1 Position Find(ElementType X,SearchTree T)
 2 {
 3     if(T==NULL)
 4       return NULL;
 5     if(X<T->Element)
 6       return Find(X,T->Left);
 7     else if(X>T->Element)
 8       return Find(X,T->Right);
 9     else
10       return T;
11 }

FindMin的递归实现和FindMax的非递归实现：

 1 Position FindMin(SearchTree T)
 2 {
 3     if(T==NULL)
 4       return NULL;
 5     else if(T->Left==NULL)
 6       return T;
 7     else
 8       return FindMin(T->Left);
 9 }
10 
11 Position FindMax(SearchTree T)
12 {
13     if(T!=NULL)
14       while(T->Right!=NULL)
15         T=T->Right;
16     return T;
17 }

FindMax的非递归形式看不懂啊，求大神！T怎么可以被改变，改了之后怎么办，根节点都变了呀？整个树不就变了吗？

Inset操作：

 1 SearchTree Insert(ElementType X,SearchTree T)
 2 {
 3     if(T==NULL)
 4     {
 5         T=malloc(sizeof(struct TreeNode));
 6         if(T==NULL)
 7           FatalError("Out of space!!!");
 8         else
 9         {
10             T->Element=X;
11             T->Left=T->Right=NULL;
12         }
13     }
14     else if(X<T->Element)
15       T->Left=Insert(X,T->Left);
16     else if(X>T->Element)
17       T->Right=Insert(X,T->Right);
18     else ;
19     return T;
20 }

（1）由于T指向该树的根，而根又在第一次插入时变化，因此Insert被写成一个返回指向新树根的指针的函数

（2）第5行malloc函数，生成一个新节点，注意6、7行对新节点是否创建成功的检查

（3）14~17行，递归地插入X到适当位置，并建立新节点与父节点的联系

Delete操作：

删除操作是二叉排序树最困难的操作。仔细分析就会得出，删除操作仅仅包括以下三种情况：

情况一：如果要删除的结点X是一片树叶，没有子女。此时只需要直接将这个结点删除即可，不需要其它操作。

情况二：如果要删除的结点X只有一个子女。此时令X的子女直接成为X的双亲结点F的子树，然后删掉X即可。

情况三：如果要删除的结点X有两个子女。一般的策略是用X的右子树的最小结点（《算法导论》中称其为X的后继，若想了解后继这个概念，我的博文http://www.cnblogs.com/sage-blog/p/3865260.html），代替X并递归地删除那个结点。

 1 SearchTree Delete(ElementType X,SearchTree T)
 2 {
 3     Position TmpCell;
 4     if(T==NULL)
 5       Error("Elment not found!!!");
 6     else if(X<T->Element)                         //向左寻找
 7       T->Left=Delete(X,T->Left);
 8     else if(X>T->Element)                         //向右寻找
 9       T->Right=Delete(X,T->Right);
10     else if(T->Left&&T->Right)                    //找到结点，并且它有两个子女
11     {
12         TmpCell=FindMin(T-Right);
13         T->Element=TmpCell->Element;
14         T->Right=Delete(T->Element,T->Right);
15     }
16     else                                           //找到结点，并且它只有一个子女或它没有子女
17     {
18         TmpCell=T;
19         if(T->Left==NULL)
20           T=T->Right;
21         else if(T->Right==NULL)
22           T=T->Left;
23         free(TmpCell);
24     }
25     return T;
26 }

时间复杂度分析：

（1）假设所有树出现的机会均等，则树的所有节点的平均深度为O(log N)

（2）在某种情况下，上面描述的算法有助于使得左子树比右子树深度深，因为我们总是用右子树的一个节点来代替删除的节点，造成树的不平衡。

存在的问题：

（1）如果向一棵树中输入预先排好序的数据（例如数据是递增的），那么一连串的Insert操作将花费二次时间，因为此时只由那些没有左儿子的结点组成。一种解决的办法就是要有一个称为平衡（balance）的附件的结构条件：任何节点的深度均不能过深。

实现树的平衡：平衡二叉树，也称之为AVL树（Adelson-Velskii和Landis），详见我的博客：http://www.cnblogs.com/sage-blog/p/3866008.html

（2）另外，较新的方法是放弃平衡条件，允许树有任意深度，但是在每次操作之后要使用一个调整规则进行调整，使得后面的操作效率更高。这种类型的数据一般属于自调整（self-adjusting）类结构。在二叉查找树的情况下，对于任意单个运算我们不再保证O(log N)的时间界，但是任意连续M次操作在最坏情况下花费时间为O(Mlog N)。

这种数据结构叫做伸展树（splay tree），详见我的博客：***