红黑树前语
目录
概念
性质
红黑树与AVL树的比较
过两天更新红黑树的模拟实现,中秋快乐各位
概念
1. 概念： 是一种搜索二叉树， 但在每个结点上增加一个存储位表示节点的颜色，可以是Red 或 Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径比其他路径长出两倍，因而是接近平衡的。红黑树达到一个近似平衡(最长路径不超过最短路径的2倍)。
数路径是以NIL为结束来数路径的，下图是有 11 条路径
性质
2. 红黑树的性质：
(1). 每个节点不是红色就是黑色
(2). 根节点是黑色的
(3). 如果一个节点是红色的，则它的两个孩子节点是黑色的。(即一条路径上没有连续的红色节点)
(4). 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均 包含相同数目的黑色节点(每条路径的黑色节点的数量是相等的)
(5). 每个叶子节点都是黑色的(此处的叶子节点指的是空节点，也称为NIL节点)
红黑树与AVL树的比较
3. AVL树和红黑树优缺点：
(1). AVL树 的搜索效率高于红黑树. 因为 AVL是严格平衡，而红黑树是近似平衡，因此对于相同的数据而言，AVL树的高度要小于红黑树的高度，故AVL树的搜索效率高
(2). 红黑树的插入和删除的效率高于AVL树。因为相对于红黑树而言，AVL树 进行 旋转的次数和概率 远高于 红黑树 进行 旋转的次数和概率