有序表

有序表的实现

• 底层：
  • 红黑树
  • AVL树
  • SB树
  • 跳表
• 时间复杂度：O(log(N))
• 红黑树、AVL树、SB树是平衡搜索二叉树

  搜索二叉树的插入和删除

• 插入直接按照大小分支插入即可
• 假如没有子节点的节点直接删除即可
• 假如删除的节点只有一个孩子节点
  • 直接让父节点的指针指向唯一的孩子即可
• 左右双全：
  • 用左树最右的节点或者是右树最左的节点
  • 这样的节点必然不是两个孩子的节点
  • 先将这个节点的子节点（假如存在）移到这个节点原来的位置
  • 然后将这个节点移到被删除的具有两个孩子的节点的位置

    平衡二叉树

• 防止因为用户数据输入顺序的原因导致树左右不平衡使得搜索的时间复杂度上升
• 左树和右树的体量差不多大
• AVL树在增删结点的时候会从这个节点的父节点开始向上查每个节点的平衡性