什么是红黑树
红黑树是一种自平衡的二叉查找树，通常用于实现关联容器包括set,map。红黑树通过引入额外的颜色属性，并对插入和删除操作进行旋转和颜色变换，来保持树的平衡。这样可以确保树的高度始终保持在对数级别，从而保证了插入、删除和查找操作的时间复杂度都为 O(log n)。
五个特性
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶子节点是黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色（即不存在连续的红色节点）。
- 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（即黑高相同）。
当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍
ps:
1.红黑树的根节点不能为红色是因为这个限制有助于确保红黑树的性质之一：从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。如果根节点是红色，那么根节点到其子节点的路径上就少了一层黑色节点，这会导致根节点到叶子节点的路径中的黑色节点数目不一致，违反了红黑树的性质。
2.新插入的节点一定是红色节点。因为如果是黑色，那就要满足性质5导致所有路径都需要增加一个黑色节点，就会比较麻烦。
旋转
1.当前节点在左子树，父节点也在左子树：
先把父节点变色，之后再进行旋转
2.当前节点在右子树，父节点在左子树：
当前节点在右，父节点也在右和当前节点在左，父节点在右同理。
