平衡二叉树
自平衡二叉树

自平衡实现方式 旋转 
旋转四种类型
LL型（右旋）  在左子树的左孩子上添加新的节点
RR型（左旋）  在右子树的右孩子上添加新的节点
LR型  先左旋 再右旋  在左子树的右孩子上添加新节点
RL型（先右旋 再左旋）在右子树的左孩子上添加新节点

AVL树 平衡二叉查找树，左右子树树高不超过1
是严格的平衡二叉树 也称为高度平衡树

红黑树是一种弱平衡二叉树

AVL树和红黑树的插入和删除操作都需要通过树的旋转来维持平衡

AVL树适合用于插入与删除比较少的情况

相对于要求严格的AVL树来说，红黑树的旋转次数少
插入、删除操作较多的情况下 适合用 红黑树



红黑树的应用场景

C++ STL TreeMap TreeSet 实现
Java TreeMap  TreeSet 实现

Linux 进程调度 ，用红黑树管理进程控制块
进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，
左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间

IO多路复用 epoll  用红黑树组织sockfd，支持快速的增删改查

Nginx 用红黑树管理定时器，有序 ，快速获取到期的事件