首页  

AVL树与红黑树(RBTree)     所属分类 DS 浏览量 77
平衡二叉树
自平衡二叉树

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

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

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

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

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

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


红黑树的应用场景 C++ STL TreeMap TreeSet 实现 Java TreeMap TreeSet 实现 Linux 进程调度 ,用红黑树管理进程控制块 进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点, 左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间 IO多路复用 epoll 用红黑树组织sockfd,支持快速的增删改查 Nginx 用红黑树管理定时器,有序 ,快速获取到期的事件

上一篇     下一篇
树的定义和术语

算法基础知识

java String indexOf 为何不使用KMP

aerospike lua udf 例子

计算机专业考研信息

栈应用之括号匹配