TreeSet已有序，为何remove方法时间复杂度不是O(log N)？

首先得澄清一个关键点：TreeSet的移除操作本身时间复杂度就是O(logN)，但这可不是只靠二分查找就完事的，你忽略了树结构维护的核心环节。

TreeSet底层是红黑树（一种自平衡的二叉搜索树），把移除操作拆成两步看就清楚了：

• 第一步：定位要移除的元素。这一步确实是类似二分查找的逻辑，沿着树的分支对比元素大小，时间复杂度O(logN)——毕竟红黑树的高度是logN级别，不会出现链表那种极端情况。
• 第二步：删除节点并修复树的平衡。找到节点后不能直接删掉就完事，得根据节点的子节点情况处理：
  • 如果是叶子节点，直接删除就行；
  • 如果节点只有一个子节点，用子节点替换它的位置；
  • 如果节点有两个子节点，得先找它的后继（或前驱）节点来替换，再删除那个后继节点。
    不管哪种情况，删除后都可能打破红黑树的平衡规则（比如颜色、黑高的要求），这时候需要做旋转、重新着色等操作来修复平衡，这些操作的时间复杂度也是O(logN)，因为只需要沿着树的高度层级调整。

你大概率是把TreeSet和有序数组搞混了：有序数组用二分查找找元素是O(logN)，但删除要移动后面的所有元素，所以整体是O(N)；而TreeSet是树结构，删除不需要移动大量元素，只是调整树的分支，整体还是O(logN)。所以不是移除做不到O(logN)，而是这个O(logN)包含了“查找+树平衡维护”两个步骤，不只是单纯的二分查找。

内容的提问来源于stack exchange，提问作者Joseph Jang