顺序表

顺序查找

对分查找

链表

索引顺序表

倒排表

二叉排序树

定义：

  1. 左子树小于根节点
  2. 右子树大于根节点
  3. 左右子树也是二叉排序树

  • 查找

  • 插入

  • 删除

    左右子树都存在时，删除位置的替换元素：

    1. 左子树最大元素（左子树中序遍历最后一个）
    2. 右子树最小值（中序第一个）
    3. 左子树根节点
    4. 右子树根节点

二叉平衡树

左子树和右子树的高度之差的绝对值不大于1