红黑树

有时候想想,打篮球跟编程有相似的地方。单纯的投篮,是个人多练练就没问题,就跟平时工作中做业务开发似的,写的多了足以应付。但是想要打比赛,想要进高难度的球,那就需要有扎实的基本功了,跟编程中不会数据结构和算法一样,关键时刻就不行了。

一、概念

  1. 红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外,一棵红黑树还需要满足这样几个要求:
    • 根节点是黑色的;
    • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
    • 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
    • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;