通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。...红黑树的规则如下:
每个结点不是红色就是黑色
根结点是黑色
如果一个结点是红色的,则它的子结点一定是黑色
任一结点到NULL(树尾)的任何路径上,所含的黑色结点数一定相同
每个NULL(树尾)空结点都是黑色的...如果我们遇到了插入后违反红黑树规则的情况,那么红黑树的调整规则如下:
插入结点是根节点(即破坏了根节点是黑色的规则)--->解决方法,直接将该节点变黑
插入结点的父节点也是红色(即破坏了红结点的孩子必须是黑色的规则...首先插入第一个结点17:
可以看到,插入根节点时,我们违反了根结点为黑的性质,解决办法也很简单,把根节点变黑就行:
继续插入下一个结点18:...学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!