跳至主要內容

二叉搜索树(Binary Search Tree)

linwu大约 6 分钟

二叉搜索树(Binary Search Tree)

在计算机科学中,二叉搜索树(Binary Search Tree,BST),有时也被称为有序或排序二叉树,是一种特殊的容器数据结构,用于在内存中存储“项”(例如数字、名称等)。它们允许快速查找、添加和删除项,并可用于实现动态集合或查找表,通过键(例如通过名称查找人的电话号码)来查找项。

二叉搜索树保持其键的有序性,以便查找和其他操作可以利用二分查找的原理:在树中从根到叶子进行遍历,通过与树节点中存储的键进行比较,并根据比较结果决定是继续在左子树还是右子树中查找。平均而言,这意味着每次比较可以跳过树的大约一半的节点,因此每次查找、插入或删除的时间与存储在树中的项的数量的对数成比例。这比在(未排序的)数组中按键查找项所需的线性时间要好得多,但比哈希表的相应操作要慢。

一个大小为9、深度为3的二叉搜索树,根节点为8。 未绘制叶子节点。

二叉搜索树
二叉搜索树

基本操作的伪代码

插入

insert(value)
  前置条件:value已通过自定义类型检查,类型为T
  后置条件:value已放置在树的正确位置
  如果 root = ø
    root ← 节点(value)
  否则
    insertNode(root, value)
  结束如果
结束插入
insertNode(current, value)
  前置条件:current为起始节点
  后置条件:value已放置在树的正确位置
  如果 value < current.value
    如果 current.left = ø
      current.left ← 节点(value)
    否则
      InsertNode(current.left, value)
    结束如果
  否则
    如果 current.right = ø
      current.right ← 节点(value)
    否则
      InsertNode(current.right, value)
    结束如果
  结束如果
结束insertNode

查找

contains(root, value)
  前置条件:root为树的根节点,value为要查找的值
  后置条件:确定value是否被找到
  如果 root = ø
    返回 false
  结束如果
  如果 root.value = value
    返回 true
  否则,如果 value < root.value
    返回 contains(root.left, value)
  否则
    返回 contains(root.right, value)
  结束如果
结束contains

删除

remove(value)
  前置条件:value为要删除的节点的值,root为BST的根节点,count为BST中的项数
  后置条件:如果找到并删除了值为value的节点,则返回true;否则返回false
  nodeToRemove ← findNode(value)
  如果 nodeToRemove = ø
    返回 false
  结束如果
  parent ← findParent(value)
  如果 count = 1
    root ← ø
  否则,如果 nodeToRemove.left = ø 并且 nodeToRemove.right = ø
    如果 nodeToRemove.value < parent.value
      parent.left ←  nodeToRemove.right
    否则
      parent.right ← nodeToRemove.right
    结束如果
  否则,如果 nodeToRemove.left != ø 并且 nodeToRemove.right != ø
    next ← nodeToRemove.right
    当 next.left != ø
      next ← next.left
    结束循环
    如果 next != nodeToRemove.right
      remove(next.value)
      nodeToRemove.value ← next.value
    否则
      nodeToRemove.value ← next.value
      nodeToRemove.right ← nodeToRemove.right.right
    结束如果
  否则
    如果 nodeToRemove.left = ø
      next ← nodeToRemove.right
    否则
      next ← nodeToRemove.left
    结束如果
    如果 root = nodeToRemove
      root = next
    否则,如果 parent.left = nodeToRemove
      parent.left = next
    否则,如果 parent.right = nodeToRemove
      parent.right = next
    结束如果
  结束如果
  count ← count - 1
  返回 true
结束remove