红黑树中红色和背景色的用途是什么？

Question

我已经阅读了大量的红黑树（维基百科，...），但仍然不明白这些颜色的背面和红色是什么。
这些颜色的主要目的是什么？为什么需要用这样的颜色来标记我们的节点？如果我们跳过红黑树的这一部分会发生什么？请帮忙。

Answer 1

颜色的目的是确保树保持大致平衡。如果没有颜色或其他不变量来确保，在最坏的情况下，您最终可能会得到退化树，这些树基本上只是效率较低的链表。