"red-black tree" 是什么意思： TreeSet，将其元素存储在红黑树中，根据元素的值对其元素进行排序；
What does "red-black tree" mean in: TreeSet, which stores its elements in a red-black tree, orders its elements based on their values;
我正在阅读 Java Tutorial Oracle 并且遇到了下面的语句。
TreeSet, which stores its elements in a red-black tree, orders its
elements based on their values;
我被短语 "red-black tree" 弄糊涂了，我进行了基本的网络搜索，但没有找到满意的答案。
对我来说，第三个搜索结果是 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree，很好地解释了这个概念。
基本上它是一种保持二叉树几乎平衡的方法，因此与插入顺序无关，它不会退化为链表，同时保持插入（和删除）成本低。
红黑树是一种self-balancing二叉搜索树。 self-balancing树有2-3树、AA树、AVL树、Red-black树等几种。
当您考虑可能存在非self-balancing二叉搜索树的最坏情况时，自平衡树的目的就很明显了。
考虑这种情况：首先将一个整数插入一个空树（非self-balancing）。继续插入整数，每个值都大于前一个。最差的转换检索时间是最后插入的元素，时间复杂度为 O(n)。这是因为您必须遍历整个树才能到达所需的元素，这很像链表。
这比时间复杂度为O(lg n)的平衡二叉搜索树差很多。因此有一些方法，例如 red-black 树，试图确保树是平衡的（意味着每个 child 的权重相同）。
1) 每个节点的颜色不是红色就是黑色，树的根总是黑色。
2）没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，红色需要有黑色父节点）。
3) 从根节点到NIL节点的每条路径都有相同数量的黑色节点。
我正在阅读 Java Tutorial Oracle 并且遇到了下面的语句。
TreeSet, which stores its elements in a red-black tree, orders its elements based on their values;
我被短语 "red-black tree" 弄糊涂了，我进行了基本的网络搜索，但没有找到满意的答案。
对我来说，第三个搜索结果是 https://en.wikipedia.org/wiki/Red%E2%80%93black_tree，很好地解释了这个概念。
基本上它是一种保持二叉树几乎平衡的方法，因此与插入顺序无关，它不会退化为链表，同时保持插入（和删除）成本低。
红黑树是一种self-balancing二叉搜索树。 self-balancing树有2-3树、AA树、AVL树、Red-black树等几种。
当您考虑可能存在非self-balancing二叉搜索树的最坏情况时，自平衡树的目的就很明显了。
考虑这种情况：首先将一个整数插入一个空树（非self-balancing）。继续插入整数，每个值都大于前一个。最差的转换检索时间是最后插入的元素，时间复杂度为 O(n)。这是因为您必须遍历整个树才能到达所需的元素，这很像链表。
这比时间复杂度为O(lg n)的平衡二叉搜索树差很多。因此有一些方法，例如 red-black 树，试图确保树是平衡的（意味着每个 child 的权重相同）。
1) 每个节点的颜色不是红色就是黑色，树的根总是黑色。
2）没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，红色需要有黑色父节点）。
3) 从根节点到NIL节点的每条路径都有相同数量的黑色节点。