红黑树：R-B Tree
1）根节点是黑色的；
2）每个叶子结点都是黑色的空节点，也就是说，叶子结点不存储数据
3）任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
4）每个节点，从该节点到达其可达叶子结点的所有路径，都包含相同数目的黑色节点
第二点为简化红黑树的代码实现而设置的
AVL树：对于有频繁的插入删除操作的数据集合，使用AVL树代价有点高
红黑树是一种平衡二叉查找树，它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似log2N，使用它是近似平衡，插入删除查找操作的时间复杂度都是O（logN）
一、插入：规定插入的节点必须是红色的，而且二叉查找树中新插入的节点都是放在叶子节点上
两种情况：
1）如果插入节点的父节点是黑色的，我们什么都不用做，仍然满足红黑树定义
2）如果插入的节点是跟节点，那我们直接改变它的颜色，把它变成黑色即可
网友评论