查找树

二分查找：静态查找

查找树：动态查找（涉及insert, delete, find）

设计理念：时空 trade off (full order -> half order)

定义：A binary search tree is a binary tree. It may be empty. If it is not empty, it satisfies the following properties：

1. Every node has a key which is an integer, and the keys are distinct
2. The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.
3. The keys in a nonempty right subtree must be larger than the key in the root of the subtree.
4. The left and right subtrees are also binary search trees.

操作：

• SearchTree MakeEmpty( SearchTree T );
• Position Find( ElementType X, SearchTree T );
• Position FindMin( SearchTree T );
• Position FindMax( SearchTree T );
• SearchTree Insert( ElementType X, SearchTree T );
• SearchTree Delete( ElementType X, SearchTree T );
• ElementType Retrieve( Position P );

实现：

• Find

  Position Find( ElementType X, SearchTree T ) {
      if ( T == NULL ) return NULL /* not found in an empty tree */
      if ( X < T->Element ) /* if smaller than root */
          return Find( X, T->Left ); /* search left subtree */
      else if ( X > T->Element ) /* if larger than root */
          return Find( X, T->Right ); /* search right subtree */
      else /* if X == root */
          return T; /* found */
      }
  

  尾递归：可改为循环

  Position  Iter_Find( ElementType X,  SearchTree T ) 
  { 
        /* iterative version of Find */
        while  ( T )   {
            if  ( X == T->Element )  return T ;  /* found */
            if  ( X < T->Element ) T = T->Left ; /*move down along left path */
            else T = T-> Right ; /* move down along right path */
        }  /* end while-loop */
        return  NULL ;   /* not found */
  }
  

  \(T(N) = S (N)=O(d)\) d为X的深度

• FindMin

  Position  FindMin( SearchTree T ) 
  { 
        if ( T == NULL )   
            return  NULL; /* not found in an empty tree */
        else 
            if ( T->Left == NULL )   return  T;  /* found left most */
            else   return  FindMin( T->Left );   /* keep moving to left */
  } 
  

• FindMax

  Position  FindMax( SearchTree T ) { 
      if ( T != NULL ) 
          while ( T->Right != NULL )   
              T = T->Right;   /* keep moving to find right most */
      return T;  /* return NULL or the right most */
  }
  

  父节点观点：需在父节点层次判断终止条件（否则将失去索引，无对fa的链接）

• Insert

  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; } 
      }  /* End creating a one-node tree */
      else  /* If there is a tree */
          if ( X < T->Element ) 
             T->Left = Insert( X, T->Left ); 
          else 
             if ( X > T->Element ) 
                T->Right = Insert( X, T->Right ); 
              /* Else X is in the tree already; we'll do nothing */ 
      return T;   /* Do not forget this line!! */ 
  }
  

  递归插入，当前节点为空的时返回新节点

• Delete

  SearchTree  Delete( ElementType X, SearchTree T ) 
  {   Position  TmpCell; 
      if ( T == NULL )   Error( "Element not found" ); 
      else  if ( X < T->Element )  /* Go left */ 
          T->Left = Delete( X, T->Left ); 
      else  if ( X > T->Element )  /* Go right */ 
          T->Right = Delete( X, T->Right ); 
      else  /* Found element to be deleted */ 
      if ( T->Left && T->Right ) {  /* Two children */ 
          /* Replace with smallest in right subtree */ 
          TmpCell = FindMin( T->Right ); 
          T->Element = TmpCell->Element; 
          T->Right = Delete( T->Element, T->Right );  } /* End if */
      else {  /* One or zero child */ 
          TmpCell = T; 
          if ( T->Left == NULL ) /* Also handles 0 child */ 
              T = T->Right; 
          else  if ( T->Right == NULL )  T = T->Left; 
          free( TmpCell );  }  /* End else 1 or 0 child */
        return  T; 
  }
  

  删除双子节点：继承 左子树最大值 / 右子树最小值（此类节点度至多为1）

懒删除：给元素带上删除标记

复杂度分析：

• find：\(O(\log_2n)\)
• insert：\(O(d)\) ->平均 \(O(\log_2n)\) - 单链退化 \(O(n)\)
• delete：\(O(d)\) ->平均 \(O(\log_2n)\) - 单链退化 \(O(n)\)

解决：调整平衡性

• AVL：高度差小于1
• RBT：最长的不超过最短的1倍
• BT：多叉树