如何在O(lg(n))内实现这些API ？

Question

原问题的[网址链接]1
http://algs4.cs.princeton.edu...

List. Implement the following list operations: size(), addFront(item),
addBack(item), delFront(item), delBack(item), contains(item),
delete(item), add(i, item), delete(i), iterator(). All operations
should be efficient (logarithmic). Hint: use two symbol tables, one to
find the ith element in the list efficiently, and the other to
efficiently search by item. Java's List interface contains these
methods, but does not supply any implementation that supports all ops
efficiently.

我觉得是不可能在O(lgn)内全部实现的。两个 symbol table. 一个（key = i (the index), value = Item), 另一个 (key = Item, value = i (the index). 这个快速查找倒是能在O(1)实现，java HashMap 一般为 O(1), 这是最好情况，但是删除的时候，比如删除第 i 个，就需要把所有大于 i 的节点都更新一遍（全都减1），这样就成了O(n)了，还有在最前面插入也是这样。不知道大家有什么好办法吗，谢谢大家帮助。
具体要求

Answer 1

可以通过两个Symbol Table实现：

1. 一颗扩展的BBT(Balanced Binary Tree)，用来实现find ith element in the list efficiently

2. 一个HT(Hash Table)，以item为key，用来实现efficiently search by item

---

BBT的要求是，在每个node增加一个记录子树node数目的参数。进行indexing的时候根据子树大小进行二分查找（binary search），这样跟index相关的操作都是可以达到O(lgn)的。至于树具体为什么树没有要求，能有效平衡就行（比如红黑树，AVL，Splay都行），以保证O(lgn)的操作效率。实现上可以参考TreeList

HT的要求是，item为key，item对应在BBT中的结点为value。这样即可以实现快速查找item的index。实现上可以参考各大语言的HashTable实现。这个HT也可以用其他数据结构代替，只要是dictionary-like即可，只不过HT应该是效率最高的。

---

API列表实现细节（为了便于说明，原题中的i重命名为index）。时间复杂度标记在「」内。

• addFront(item) : 调用add(0, item)「O(lgn)」

• addBack(item) : 调用add(size()-1, item)「O(lgn)」

• deleteFront() : 调用delete(0)「O(lgn)」

• deleteBack() : 调用delete(size()-1)「O(lgn)」

• delete(item) : 在HT中寻找item得到对应的node「O(1)」，根据node计算index「O(lgn)」，然后执行delete(index)「O(lgn)」。最后在HT中删掉item「O(1)」。

• add(index, item) : 根据index在树中进行二分查找（如果左子树节点数>index就往左，<index就往右）「O(lgn)」，找到后在BBT和HT中进行插入「≤O(lgn)」

• delete(index) : 根据index在树中进行二分查找（同上），「O(lgn)」，找到后在BBT和HT中删除「≤O(lgn)」

• contains(item) : 在HT中进行查找「O(1)」

• isEmpty() : size()>0「O(1)」

• size() : 返回HT的size「O(1)」

---

记录子树node数目参数是为了用于二分查找，二分查找的过程用下图来描述一下，树以AVL形式为例。图中每个结点下面标的数字是该结点为根的子树中含有的node数目。如B为根的子树中含有的node为BADC，因此子树node数为4。下方的列表为元素在列表中的顺序，虚线表示HT建立的对应关系。

查找这个List中的第四个元素(index=3)可以按照改图所示进行查找，lnum表示左子树结点数目：

• 从根结点E出发，index<lnum=4，因此向左查找

• 到达结点B，index>lnum=1，因此向右查找，并且更新index为index-lnum-1，此处更新后的值为3-1-1=1

• 到达结点D，index=lnum=1，完成查找

---

更加具体的实现细节请自行思考：

• 这颗二叉树与二叉搜索树有什么不同？

• 如何根据node计算item的index（例如，如何根据结点D计算出D在列表中为第四个元素）？「≤O(lgn)」

• 在插入和删除元素后如何更新子树结点数目？「≤O(lgn)」

• 在插入和删除元素后如何保证BBT平衡？「O(lgn)」

(原创请勿转载)

Answer 2

可以用TreeMap或TreeSet来模拟List，这样算法复杂度就是O(logN)的。当然这有点难度。

另外可以研究下一种叫TreeList的结构，详情参阅：
https://commons.apache.org/pr...
它并非像TreeMap一样用红黑树，而是用另一种平衡树：AVL树