赞
踩
关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:
1、每个节点要么是红色,要么是黑色,但根节点永远是黑色的;
2、每个红色节点的两个子节点一定都是黑色;
3、红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);
4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
5、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
6. 红黑树从根到叶子的最长路径不会超过最短路径的两倍
2.在某些情况比如,在红黑树中做插入和删除时候,有时会破坏红黑树特点,使红黑树不成立,为使红黑树保持平衡,需要进行旋转和变色
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。