二叉查找树（BST）

增加

• 递归对比大小，找到合适位置插入。

删除

• 如果没有孩子结点，直接删除。
• 如果只有一个孩子结点，则将孩子结点替换当前结点即可。
• 如果有两个孩子结点，要么查找左子树上的最大值，要么查找右子树上的最小值，然后将需要删除的结点替换为这个值，最后删除查找到的那个结点。

查找

• 递归查找

遍历

• 中序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之间
• 前序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之前
• 后序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之后

参考

• 算法导论 - 二叉搜索树
• 数据结构与算法JavaScript描述