数据结构与算法分析 —— C 语言描述：查找树 ADT —— 二

2022-03-30 本文已影响0人 Sun东辉

二叉树的一个重要的应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是，对于树中的每个节点 X，它的左子树中所有关键字值小于 X 的关键字值，而它的右子树中所有关键字值大于 X 的关键字值。注意，这意味着，该树所有的元素可以用某种统一的方式排序。

注意，由于树的递归定义，通常是递归地编写这些操作的例程。因为二叉查找树的平均深度是 $O(log N)$ ，所以我们一般不必担心栈空间被用尽。

一些操作

MakeEmpty

操作主要用于初始化。有些程序设计人员更愿意将第一个元素初始化为单节点树，但是，我们的实现方法更紧密地遵循树的递归定义。如下所示：

SearchTree
MakeEmpty( SearchTree T )
{
    if(T != NULL) {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T )
    }
    return NULL;
}

Find

这个操作一般需要返回指向树 T 中具有关键字 X 的节点的指针，如果这样的节点不存在则返回 NULL。书的结构使这种操作很简单。如果 T 是 NULL，那么我们就可以返回 NULL，否则，如果存储在 T 中的关键字是 X，那么我们可以返回 T。否则，我们对树 T 的左子树或右子树进行一次递归调用，这依赖于 X 与存储在 T 中关键字的关系。如下：

Position
Find( ElementType X, SearchTree T) 
{
    if( T == NULL )
        return NULL;
    if ( X < T->Element )
        return Find( X, T->Left );
    else
    if (X > T-> Element )
        return Find(X, T->Right );
    else
        return T;
}

FindMin & FindMax

这两个例程分别返回树中最小元和最大元的位置。虽然返回这些元素的准确值似乎更合理，但是这将与 Find 操作不相容。重要的是，看起来类似的操作做的工作也是类似的。为执行 FIndMin，从根开始并且只有左儿子就向左进行。终止点是最小的元素。FindMax 例程除分支朝向右儿子外其余过程相同。

这种递归是如此容易以至于许多程序设计员不厌其烦的使用它。我们用两种方法编写这两个例程，用递归编写 FindMin，而用非递归编写 FindMax。

Position
FindMin( SearchTree T ) 
{
    if( T == NULL ) 
        return NULL;
    else
    if( T->Left == NULL )
        return T;
    else 
        return FindMin( T->Left );
}

Position
FindMax( SearchTree T)
{
    if ( T != NULL )
        while( T->Right != NULL )
            T = T->Right;
    return T;
}

注意，我们需要小心的处理空树这种退化的情况。虽然小心总是重要的，但在递归程序中它尤其重要。此外，还要注意，在 FindMax 中对 T 的改变是安全的，因为我们只用拷贝来进行工作。不管怎么说，还是应该随时特别小心，因为诸如 “T→Right = T→Right→Right”这样的语句将会产生一些变化。

Insert

进行插入操作的例程在概念上是简单的。为了将 X 插入到树 “T” 中，你可以像用 Find 那样沿着树查找。如果找到 X，则什么也不用做（或做一些“更新”）。否则，将 X 插入到遍历的路径上最后一点上。

重复元的插入可以通过在节点记录中保留一个附加域以指示发生的频率来处理。这使整棵树增加了某些附加空间，但是，却比将重复信息放到树中要好（它使树的深度变得很大）。当然，如果关键字只是一个更大结构的一部分，那么这种方法行不通，此时我们可以把具有相同关键字的所有结构保留在一个辅助数据结构中，如表或是另一棵查找树中。

SearchTree
Insert( ElementType X, SearchTree T)
{
    if(T == NULL ) 
    {
        /*Create and return a one-node tree */
        T = malloc( sizeof( struct TreeNode ));
        if( T == NULL )
            FatalError( "Out of space!!!");
        else
            T->Element = X;
            T->Left = T->Right = NULL;
    }
    else
    if( X < T->Element )
        T->Left = Insert(X, T->Left);
    else
    if( X > T->Element )
        T->Right = Insert( X, T->Right );
    /* ELse X is the tree already; we'll do nothing */
    
    return  T;/* Do not forget this line!! */
}

Delete

正如许多数据结构一样，最困难的操作是删除。一旦发现要删除的节点，我们就需要考虑几种可能的情况。

如果节点是一片树叶，那么可以立即删除。
如果节点有一个儿子，则该节点可以在其父节点调整指针绕过该节点后删除。注意，所删除的节点现在已不再引用，而该节点只有在指向它的指针已被省去的情况才能删除。
复杂的情况是处理具有两个儿子的节点。一般的删除策略是用其右子树中最小的数据（很容易找到）代替该节点的数据并递归地删除那个节点（现在它是空的）。因为右子树中最小的节点不可能有左儿子，所以第二次 Delete（删除）更容易。

如果删除的次数不多，则通常使用的策略是懒惰删除（lazy deletion）：当一个元素要被删除时，它仍留在树中，只是做了个被删除的记号。这种做法特别是在有重复关键字时很流行，因为此时记录出现频率数的域可以减 1。如果树中的实际节点数和“被删除”的节点数相同，那么树的深度预计只上升一个小的常数。因此，存在一个与懒惰删除相关的非常小的时间损耗。再有，如果被删除的关键字是重新插入的，那么分配一个新的单元的开销就避免了。

平均情形分析

假设所有的树出现的机会均等，则树的所有节点的平均深度为 $O(log N)$ 。此时，除 MakeEmpty 和一些个别情形外，所有操作的平均运行时间都是 $O(log N)$ 的。

一棵树的所有节点的深度的和称为内部路径长（internal path length）。

如果向一棵树输入预先排序的数据，那么一连串 Insert 操作将花费二次时间，而用链表实现 Insert 的代价会非常巨大，因为此时的树将只由那些没有左儿子的节点组成。一种解决办法就是要有一个称为平衡（balance）的附加的结构条件：任何节点的深度均不得过深。

有许多一般的算法可以实现平衡树。但是，大部分算法都要比标准的二叉查找树复杂得多，而且更新要平均花费更长的时间。不过，它们确实防止了处理起来非常麻烦的一些简单情形。例如最老的一种平衡查找树 ALV 树。

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