二叉搜索树
在其他语言中阅读： 葡萄牙语
在计算机科学中，二叉搜索树（BST），有时称为有序或排序二叉树，是一种特殊的容器： 用于存储“项目”（如数字、名称等）的内存数据结构。它们允许快速查找、添加和删除项目，并且可以用来实现动态项目集合，或者通过键查找项目的查找表（例如，通过姓名查找人的电话号码）。
二叉搜索树保持其键的排序顺序，以便查找和其他操作可以使用二分搜索原则： 当在树中查找键（或插入新键）时，它们从根到叶遍历树，与存储在树节点中的键进行比较，并根据比较结果决定继续在左子树还是右子树上搜索。平均而言，这意味着每次比较可以让操作跳过大约一半的树，因此每个查找、插入或删除操作的时间与树中存储的项目数量的对数成比例。这比在（未排序的）数组中按键查找项目所需的线性时间要好得多，但比哈希表上的相应操作要慢。
一个大小为9，深度为3的二叉搜索树，根上有8个节点。 叶子节点未绘制。
使用okso.app制作*
基本操作的伪代码
插入
insert(value)
预处理：value已通过自定义类型检查，类型为T
后处理：value已放置在树中的正确位置
如果root为空
root←节点(value)
否则
insertNode(root, value)
结束如果
end insert
insertNode(current, value)
预处理：current是从哪里开始节点
后处理：value已放置在树中的正确位置
如果value<当前.value
如果当前.left为空
当前.left←节点(value)
否则
插入Node(current.left, value)
结束如果
否则
如果当前.right为空
当前.right←节点(value)
否则
插入Node(current.right, value)
结束如果
结束如果
end insertNode
查找
contains(root, value)
预处理：root是树的根节点，value是我们想要定位的值
后处理：value要么找到，要么找不到
如果root为空
返回false
结束如果
如果root.value=value
返回true
否则如果value<root.value
返回contains(root.left, value)
否则
返回contains(root.right, value)
结束如果
end 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
while 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
end remove
查找节点的父节点
findParent(value, root)
预处理：value是我们要找的节点的值，root是BST的根节点且不等于ø
后处理：如果找到value的父节点，则返回父节点的引用；否则返回ø
如果value=root.value
返回ø
结束如果
如果value<root.value
如果root.left=ø
返回ø
否则如果root.left.value=value
返回root
否则
返回findParent(value, root.left)
结束如果
否则
如果root.right=ø
返回ø
否则如果root.right.value=value
返回root
否则
返回findParent(value, root.right)
结束如果
结束如果
end findParent
查找节点
findNode(root, value)
预处理：value是我们要找的节点的值，root是BST的根节点
后处理：如果找到value的节点，则返回该节点的引用；否则返回ø
如果root=ø
返回ø
结束如果
如果root.value=value
返回root
否则如果value<root.value
返回findNode(root.left, value)
否则
返回findNode(root.right, value)
结束如果
end findNode
查找最小值
findMin(root)
预处理：root是BST的根节点
root=ø
后处理：BST中最小值已找到
如果root.left=ø
返回root.value
结束如果
findMin(root.left)
end findMin
查找最大值
findMax(root)
预处理：root是BST的根节点
root=ø
后处理：BST中最大值已找到
如果root.right=ø
返回root.value
结束如果
findMax(root.right)
end findMax
遍历
中序遍历
inorder(root)
预处理：root是BST的根节点
后处理：BST中的节点已按中序遍历
如果root≠ø
inorder(root.left)
输出root.value
inorder(root.right)
结束如果
end inorder
前序遍历
preorder(root)
预处理：root是BST的根节点
后处理：BST中的节点已按前序遍历
如果root≠ø
输出root.value
preorder(root.left)
preorder(root.right)
结束如果
end preorder
后序遍历
后序遍历(root)
预处理：root是二叉搜索树（BST）的根节点
后处理：二叉搜索树中的节点已按后序遍历顺序访问
如果根节点不为空
后序遍历(root的左子树)
后序遍历(root的右子树)
输出root的值
结束条件
end 后序遍历
复杂度分析
时间复杂度
| 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
空间复杂度
O(n)