数据结构-二叉搜索树

本文写于 2020 年 3 月 26 日，2022 年 3 月 20 日重新整理

二叉搜索树 (Binary Search Tree) 又称为二叉查找树。二叉搜索树本质上是一颗二叉树，在非空时它具有以下性质：

左子树的所有键值 key 小于根节点键值
右子树的所有键值 key 大于根节点键值
左子树和右子树也是二叉搜索树
（每个节点的键值是唯一的）

操作集

//从二叉搜索树中找出键值为key的节点地址
BinarySearchTree *find(BinarySearchTree *tree, KeyType key);
//找出二叉搜索树的最小键值节点
BinarySearchTree *findMin(BinarySearchTree *tree);
//找出二叉搜索树的最大键值节点
BinarySearchTree *findMax(BinarySearchTree *tree);
//向二叉搜索树插入键值为key的节点
BinarySearchTree *insert(BinarySearchTree *tree, KeyType key);
//从二叉搜索树删除键值为key的节点
BinarySearchTree *delete (BinarySearchTree *tree, KeyType key);

实现

• find

  查找的操作较为简单
  若树为空，返回 NULL
  若树非空，将 key 与根节点的 key 进行比较：

  • 若大于根节点的 key ，说明待查找节点在根节点的右侧，在右子树中继续查找
  • 若小于根节点的 key ，说明待查找节点在根节点的左侧，在左子树中继续查找
  • 若等于根节点的 key ，说明待查找节点已找到，直接返回跟节点

  //递归实现
  BinarySearchTree *find(BinarySearchTree *tree, KeyType key)
  {
      if (tree == NULL)
          return NULL;
      if (key > tree->key)
      {
          return find(tree->right, key);
      }
      else if (key < tree->key)
      {
          return find(tree->left, key);
      }
      else
      {
          return tree;
      }
  }

  上述尾递归实现效率不高而且有爆栈的风险，下面是将尾递归展开为循环的实现。

  //循环实现
  BinarySearchTree *find(BinarySearchTree *tree, KeyType key)
  {
      if (tree == NULL)
          return NULL;
      BinarySearchTree *temp = tree;
      while (temp)
      {
          if (key > temp->key)
              temp = temp->right;
          else if (key < temp->key)
              temp = temp->left;
          else
              return temp;
      }
  }

• findMin

  观察二叉查找树的结构特点，容易知道其最小的元素一定在树的最左侧。

  BinarySearchTree *findMin(BinarySearchTree *tree)
  {
      if (tree == NULL)
          return NULL;
      BinarySearchTree *temp = tree;
      while (temp->left)
      {
          temp = temp->left;
      }
      return temp;
  }

  //递归实现
  BinarySearchTree *findMin(BinarySearchTree *tree)
  {
      if(tree==NULL) return NULL;
      if(tree->left) return findMin(tree->left);
      else return tree;
  }

• findMax

  同理，最大元素一定在二叉搜索树的最右侧。

• insert

  插入操作较为复杂，先找到要插入的位置，然后构造节点将节点插入合适的位置。

  首先看简单的递归实现

  BinarySearchTree *insert(BinarySearchTree *tree, KeyType key)
  {
      if (tree == NULL)
      {
          tree = (BinarySearchTree *)malloc(sizeof(BinarySearchTree));
          tree->key = key;
          tree->left = tree->right = NULL;
          return tree;
      }
      if (key > tree->key)
          return insert(tree->right, key);
      else if (key < tree->key)
          return insert(tree->left, key);
      //else key==tree->key; do nothing
  }

  循环实现：

  //循环实现
  BinarySearchTree *insert(BinarySearchTree *tree, KeyType key)
  {
      BinarySearchTree *temp = tree;
      while (temp)
      {
          if (key > temp->key)
              temp = temp->right;
          else if (key < temp->key)
              temp = temp->left;
          else
              break; //if equals,I dont know what's right,lets just rewrite it.
      }
      //when break out while loop,temp must be NULL
      temp = (BinarySearchTree *)malloc(sizeof(BinarySearchTree));
      temp->key = key;
      temp->left = temp->right = NULL;
      return temp;
  }

• delete

  删除操作是最为复杂的，因为被删除的节点处在不同位置时，操作的行为也是不同的。首先找到要删除的节点

  • 若删除的节点是叶节点，可以直接将其置为NULL

  • 若删除的节点有一个子节点，可以使用它的孩子节点代替被删除的节点

  • 若删除的节点有两个子节点，则有两种选择：

    • 使用被删除节点的左子树的最大值节点代替被删除节点
    • 使用被删除节点的右子树的最小值节点代替被删除节点
    • 然后还需要删除左子树/右子树中那个拿去代替被删除节点的节点，过程较为复杂，删除子树节点的操作需要递归完成（其他的实现不会😁）

    BinarySearchTree *delete (BinarySearchTree *tree, KeyType *key)
    {
        BinarySearchTree *target = find(tree, key);
        if (target == NULL)
            return NULL;
        if (target->left && target->right)
        {                                              //both left child and right child are valid
            KeyType min = findMin(target->right)->key; //or findMax(target->left)
            target->key = min;
            delete (target->right, min);
        }
        else
        {
            BinarySearchTree *temp = target; //copy target address,it need to be freed
            if (target->left != NULL)
            { //only left child
                target = target->left;
            }
            else if (target->right != NULL)
            { //only right child
                target = target->right;
            }
            //else no child,just free the node will be fine
            free(temp);
        }
        return tree;
    }

最后

注意到根据二叉搜索树的插入规则，假如要插入的元素一个比一个大，则树的右侧将形成一个长链，高度会迅速增加。为了解决这个问题，应该在插入时引入一种尽量平衡的插入规则，这就是平衡二叉树。