AVL树
- 不平衡情况
- 插入节点位于左子节点的左子树(左左)
- 插入节点位于左子节点的右子树(左右)
- 插入节点位于右子节点的左子树(右左)
- 插入节点位于右子节点的右子树(右右)
- 左左、右右为外侧插入,左右、右左为内侧插入
- 左左:祖父节点右旋
- 右右:祖父节点左旋
- 左右:祖父节点右旋,更新祖父节点,祖父节点左旋
右左:祖父节点左旋,更新祖父节点,祖父节点右旋
RB树
- 定义
- 非红即黑
- 根为黑色
- 红节点子全黑
任一节点至叶节点路径黑节点数相同
permutation
- next_permutation
- 从后向前找到第一对相邻增序元素
- 从后向前找到第一个大于相邻元素中前一个元素,并交换两值
- 将相邻增序中后一个元素到结尾的逆序处理
- prev_permutation
- 从后向前找到第一对相邻降序元素
- 从后向前找到第一个小于相邻元素中前一个元素,并交换两值
将相邻降序中后一个元素到结尾的元素逆序处理
SORT
- stl-SORT:
- 快排
- 低于门限值使用insert_sort
- 递归层次过深,使用heap_sort