笔试算法题（51）：简介 - 红黑树（RedBlack Tree）

时间：2022-03-10 17:23

红黑树（Red-Black Tree）

红黑树是一种BST，但是每个节点上增加一个存储位表示该节点的颜色（R或者B）；通过对任何一条从root到leaf的路径上节点着色方式的显示，红黑树确保所有路径的差值不会超过一倍，最终使得BST接近平衡；
红黑树内每个节点包含五个属性：color, key, left, right和p，p表示指向父亲节点的指针；一棵BST需要同时满足下述五个性质才能称作红黑树：
每个节点只能是红色或者黑色节点中的一种；

根节点必须是黑色；

每个叶节点（NULL）必须是黑色；

如果一个节点是红色，则它的两个子节点必须是黑色；

对于树中任何一个节点，该节点到其叶节点的所有路径上的黑色节点数相同
红黑树的空间复杂度为O(N)；支持三种操作：search, insert, delete，并且所有操作的时间复杂度都为O(logN)，最好情况跟最坏情况的复杂度相同。对于search操作而言，其依赖BST的性质，所以不需要依赖节点的着色信息；着色信息仅为了保证BST的平衡性，insert和delete操作则可能破坏BST的平衡性，所以这两种操作需要对红黑树中节点的着色信息进行调整。