JAVA TreeSet使用的基本（非立即）支持数据结构是什么？

Question

因此，TreeSet使用TreeMap作为后备数据结构（具有对应于键的虚拟值），而TreeMap又使用Red-Black树，这是一种自平衡BST。

现在，这棵红黑树用作后备数据结构是什么？它是数组还是链表？

我的理解是它是一个链表，因为在TreeSet中，.first（）之类的操作返回最小值，而不是根，并且它具有O（1）时间复杂度。

因此，基本上，它是一个链表以及至少，最大，链表根等一系列指针。我的理解正确吗？

Answer 1

树集红黑树是使用TreeMap实现维护的，该实现内部使用Entry类，该类实际上是双向链接列表的一种行为：

从Entry类挖出的代码段将帮助您理解：

K key;
V value;
TreeMap.Entry<K, V> left;
TreeMap.Entry<K, V> right;
TreeMap.Entry<K, V> parent;