AVL树

  • 不平衡情况

    • 插入节点位于左子节点的左子树(左左)
    • 插入节点位于左子节点的右子树(左右)
    • 插入节点位于右子节点的左子树(右左)
    • 插入节点位于右子节点的右子树(右右)
  • 左左、右右为外侧插入,左右、右左为内侧插入
  • 左左:祖父节点右旋
  • 右右:祖父节点左旋
  • 左右:祖父节点右旋,更新祖父节点,祖父节点左旋
  • 右左:祖父节点左旋,更新祖父节点,祖父节点右旋

    RB树

  • 定义
  • 非红即黑
  • 根为黑色
  • 红节点子全黑
  • 任一节点至叶节点路径黑节点数相同

    permutation

  • next_permutation
  • 从后向前找到第一对相邻增序元素
  • 从后向前找到第一个大于相邻元素中前一个元素,并交换两值
  • 将相邻增序中后一个元素到结尾的逆序处理
  • prev_permutation
  • 从后向前找到第一对相邻降序元素
  • 从后向前找到第一个小于相邻元素中前一个元素,并交换两值
  • 将相邻降序中后一个元素到结尾的元素逆序处理

    SORT

  • stl-SORT:
    • 快排
    • 低于门限值使用insert_sort
    • 递归层次过深,使用heap_sort

      STL源码分析-AVL树-RB树-LMLPHP

      STL源码分析-AVL树-RB树-LMLPHP
04-28 15:36