理解红黑树
简介：红黑树是一种自平衡二叉查找树，由鲁道夫·贝尔（Rudolf Bayer）在1972年发明，最初称为“对称二叉B树”。它的设计旨在解决普通二叉查找树在频繁插入和删除操作时可能退化为链表的问题，从而保持高效的查找、插入和删除性能。
演变背景：
- 二叉查找树的局限性：普通二叉查找树在插入有序数据时可能退化为链表，导致操作时间复杂度从O(log n)上升到O(n)。
- 平衡二叉树的提出：为了应对这一问题，平衡二叉树（如AVL树）被提出，通过严格的平衡条件确保树的高度平衡，但频繁的旋转操作增加了维护成本。
- 红黑树诞生：红黑树在平衡性和维护成本之间找到了折中的方案，通过引入颜色标记和特定规则，放款了平衡条件，减少了旋转操作的频率，同时也能保持对数级别的时间复杂度。
红黑树基本原则：
红黑树广泛应用于需要高效查找、插入和删除操作的场景，如：
- C++ STL中的
map和set。 - Java中的
TreeMap和TreeSet。 - Linux内核的进程调度。
插入规则：
删除规则：
