可以通过两个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)」

(原创请勿转载)