二叉搜索树

二叉搜索树的节点包含键及其关联内容，并有通往左右子树的链接。对任意节点，左子树的全部键较小，右子树的全部键较大；约束并不只比较紧邻的两个孩子，而是覆盖它下面的完整子树。

查找从根开始比较目标键。相等时找到对应项，小于当前键时转入左子树，大于时转入右子树；如果所需链接为空，则说明当前树里没有该键。相同规则也决定一个新键应当接入的位置。

参考：[1]

先访问左子树、再访问节点本身、最后访问右子树，称为中序遍历。因为各子树都遵守键顺序，这样访问便能按键从小到大列出内容，而不需要在输出前重新排序整批键。

删除有两个孩子的节点时，可以用右子树中最小键的后继节点代替它，再从原位置移走该后继并接回适当子树。替换后的链接仍须满足相同有序不变量；只删去一个节点而不处理两支内容，会丢失结构。

参考：[1]

一次查找可能沿根到叶的路径前进，时间因此与树高相关。若按已经排好序的键建立一个没有平衡措施的树，节点可能形成近似单链，最坏查找就会经过几乎全部元素。

随机插入模型能得到有利的平均分析，却不等于对任意输入都有对数上界。需要稳定的最坏性能时，可以使用维持平衡的搜索树；“每个节点至多两个孩子”和“整棵树的高度是对数级”是不同性质。

参考：[1]