除二叉树外可实现增删查O(log n)、前后继查询O(1)的数据结构有哪些？

明确结论：存在满足所有要求的非二叉树数据结构，最具代表性的就是跳表（Skip List）。

跳表的性能匹配说明 #

• 插入、删除、查找操作：跳表通过多层有序索引实现，平均时间复杂度均为O(log n)，工业界常用的随机层数实现方案可以将最坏O(n)的概率压到可忽略的程度，实际使用中可稳定达到O(log n)的性能要求。
• 前驱、后继查询操作：跳表最底层是完整的有序双向链表，只要定位到目标节点，直接通过双向链表的前后指针即可获取前驱、后继节点，时间复杂度为O(1)。

其他可选实现方案 #

除跳表外，排序散列结合双向链表的组合结构也可满足要求：散列表部分负责查找（性能甚至优于O(log n)），双向链表维护节点的全局排序关系用于O(1)获取前驱后继，额外加一层非二叉树的有序索引（比如基数树）来保证插入、删除的O(log n)性能。不过这类组合结构实现复杂度比跳表高，工业场景下使用范围不如跳表广。

你提到的两类结构的缺陷确实成立：

双向链表仅在已定位节点的前提下能做到插入删除O(1)，但全量查找复杂度为O(n)，不符合要求；
普通有序数组的二分查找复杂度为O(log n)，但插入删除需要移动大量元素，时间复杂度为O(n)，也不满足要求。

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