Skip to main content

二叉搜索树

BSTMap（Binary Search Tree，二叉搜索树）

特性：左节点键值比根节点小，右节点键值比根节点大​

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉搜索树

操作​

查找find：​

  • x<根 -> find(左子树)
  • x>根 -> find(右子树)
  • x=根 -> 返回

插入insert：​

  • x<根 && 左子树为null -> 插入左子树
  • x>根 && 右子树为null-> 插入右子树
好的递归
static  BST insert(BST T, Key ik){
  if(T == null)
    return  new BST(ik);
  if(ik ≺ T.key)
    T.left = insert(T.left, ik);
  else if(ik ≻ T.key)
    T.right = insert(T.right, ik);
  return  T;
}

不好的递归
static  BST insert(BST T, Key ik){
  if(T.left == null)
    T.left = new BST(ik);
  else if(T.right == null)
    T.right = new BST(ik);
  if(ik < T.key)
    insert(T.left, ik);
  else if(ik > T.key)
    insert(T.right, ik);
}

删除（x节点）​

  • 删除叶节点：直接删除
  • 删除只有一个子节点：删除x，将x的父节点指向x唯一的子节点
  • 删除有两个子节点：删除掉x，但需要找到一个节点取代x的位置
    • 右子树找最小值 -> 替代x ，该节点有两种情况
      • 叶子节点
      • 只有一个子节点
    • 左子树找最大值 -> 替代x
      • 叶子节点
      • 只有一个子节点