红黑树
2018-11-16 本文已影响0人
杨殿生
平衡二叉查找树
二叉树中任意一个结点的左右子树高度相差不能大于1。
AVL树
严格符合定义
红黑树
跟结点是黑色
每个叶子结点都是黑色的空节点，叶子结点不存储数据
任何相邻的结点都不能同时为红色，也就是说，红色结点是被黑色结点隔开的
每个结点，从该结点到达其可达叶子结点的所有路径，都包含相同数目的黑色结点
插入操作平衡调整
红黑树规定，插入节点必须是红色的。而且，二叉查找树种新插入的结点都是放在叶子节点上
如果插入的结点父节点是黑色，什么都不做
如果插入节点是根结点，那直接给变颜色，把他变成黑色
其他情况需要进行调整，左右旋转和改变颜色
