定义

• 左子树所有节点小于当前节点
• 右子树所有节点大于当前节点
• 左右子树也是二叉排序树

操作

• 增
  • 小于当前节点 $\Rightarrow$ 查左子树
    • 空 $\Rightarrow$ 插入
    • 非空 $\Rightarrow$ 递归
  • 大于当前节点 $\Rightarrow$ 查右子树
    • 空 $\Rightarrow$ 插入
    • 非空 $\Rightarrow$ 递归
• 删
  1. 先删去当前节点
  2. 填补
     • 右子树空 $\Rightarrow$ 左儿子填补
     • 左子树空 $\Rightarrow$ 右儿子填补
     • 子树不空 $\Rightarrow$
       1. 找到右子树中序第一个子女 (右子树最左节点) $n$
       2. 用 $n$ 填补当前节点
       3. 递归执行删除 $n$