1、題目描述

設(shè)計(jì)一個(gè)結(jié)構(gòu)包含如下三個(gè)方法：

void add(int index, int num); //把num加入到index位置
int get(int index); //取出index位置的值（是自然序的index位置，非排序后）
void remove(int index); //把index位置上的值刪除

要求三個(gè)方法時(shí)間復(fù)雜度 $O(logN)$

2、思路分析

ArrayList 中刪除一個(gè)元素需要將其后的元素全部往前移動(dòng)一位，時(shí)間復(fù)雜度為 $O(N)$；LinkedList 中雖然刪除一個(gè)元素的時(shí)間復(fù)雜度很低$O(1)$，但是要找到這個(gè)待刪除的元素得從頭開(kāi)始遍歷，所以整體時(shí)間復(fù)雜度仍然為 $O(N)$。

腳本語(yǔ)言中使用的“數(shù)組”好像什么功能都能完成，且很高效，是因?yàn)樵摂?shù)組底層并不是單純的數(shù)組或雙鏈表，只是高度改進(jìn)后起名為“數(shù)組”。

題目補(bǔ)充說(shuō)明：add(int index, int num) 方法在 index 位置加入 num，意思是假設(shè)原數(shù)組是 [3, 5, 2, 4]，如果在 1 位置加入 7，則數(shù)組變成 [3, 7, 5, 2, 4]。

使用有序表可以設(shè)計(jì)出題目要求的復(fù)雜度的三個(gè)方法的結(jié)構(gòu)。但是要注意：

1. 為了區(qū)分值相同的兩個(gè)數(shù)，在外面再封裝一層。也就是說(shuō)如果有多個(gè)相同的值，在樹(shù)上就會(huì)有多個(gè)值相同的節(jié)點(diǎn)，通過(guò)內(nèi)存地址區(qū)分開(kāi)。每個(gè)節(jié)點(diǎn)記錄的size 就是平衡因子，即以該節(jié)點(diǎn)為根的樹(shù)上的節(jié)點(diǎn)個(gè)數(shù)。

2. 改進(jìn)的有序表并不是按照 key 進(jìn)行排序的，而是按照自然時(shí)序。即當(dāng)前節(jié)點(diǎn)的左樹(shù)的自然時(shí)序都早于當(dāng)前節(jié)點(diǎn)，右樹(shù)的自然時(shí)序都晚于當(dāng)前節(jié)點(diǎn)。

3. 如果能維持一個(gè)以自然時(shí)序排列的樹(shù)，無(wú)論左旋還是右旋，自然時(shí)序都維持正確，即不會(huì)改變這些數(shù)的相對(duì)次序。

4. 對(duì)于一棵已經(jīng)生成的樹(shù)，加入新的數(shù)后無(wú)論如何旋轉(zhuǎn)都不會(huì)改變它的相對(duì)次序，那么新加入的數(shù)應(yīng)該掛在樹(shù)的哪個(gè)位置上呢？

以自然時(shí)序排列組織的樹(shù) 以及 旋轉(zhuǎn)后相對(duì)次序沒(méi)有發(fā)生改變 舉例：

輸入的數(shù)依次為[5, 3, 5]

再舉例add 和 remove 操作：

刪除4位置的數(shù)后的樹(shù)對(duì)應(yīng)的自然時(shí)序就是[7, 7, 3, 5, 6]。

3、代碼實(shí)現(xiàn)

import java.util.ArrayList;//本質(zhì)就是不去重版本的有序表/Size Balanced Tree
public class AddRemoveGetIndexGreat {//沒(méi)有key，因?yàn)閰⑴c排序的并不是key，而是隱含的自然時(shí)序public static class SBTNode<V> {public V value;public SBTNode<V> l;public SBTNode<V> r;public int size; //平衡因子，也參與業(yè)務(wù)public SBTNode(V v) {value = v;size = 1;}}public static class SbtList<V> {private SBTNode<V> root;private SBTNode<V> rightRotate(SBTNode<V> cur) {SBTNode<V> leftNode = cur.l;cur.l = leftNode.r;leftNode.r = cur;leftNode.size = cur.size;cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;return leftNode;}private SBTNode<V> leftRotate(SBTNode<V> cur) {SBTNode<V> rightNode = cur.r;cur.r = rightNode.l;rightNode.l = cur;rightNode.size = cur.size;cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;return rightNode;}private SBTNode<V> maintain(SBTNode<V> cur) {if (cur == null) {return null;}int leftSize = cur.l != null ? cur.l.size : 0;int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;int rightSize = cur.r != null ? cur.r.size : 0;int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;if (leftLeftSize > rightSize) {cur = rightRotate(cur);cur.r = maintain(cur.r);cur = maintain(cur);} else if (leftRightSize > rightSize) {cur.l = leftRotate(cur.l);cur = rightRotate(cur);cur.l = maintain(cur.l);cur.r = maintain(cur.r);cur = maintain(cur);} else if (rightRightSize > leftSize) {cur = leftRotate(cur);cur.l = maintain(cur.l);cur = maintain(cur);} else if (rightLeftSize > leftSize) {cur.r = rightRotate(cur.r);cur = leftRotate(cur);cur.l = maintain(cur.l);cur.r = maintain(cur.r);cur = maintain(cur);}return cur;}//root這棵樹(shù)上的index位置添加節(jié)點(diǎn)cur，這個(gè)cur一定不是重復(fù)的，因?yàn)榉庋b了一層，有不同的內(nèi)存地址private SBTNode<V> add(SBTNode<V> root, int index, SBTNode<V> cur) {if (root == null) {return cur;}//以root為根的樹(shù)上的節(jié)點(diǎn)個(gè)數(shù)加1，可以理解為與之前“區(qū)間和個(gè)數(shù)”問(wèn)題中的all數(shù)據(jù)項(xiàng)合并了root.size++; //左樹(shù)及根節(jié)點(diǎn)一共有多少個(gè)節(jié)點(diǎn)int leftAndHeadSize = (root.l != null ? root.l.size : 0) + 1; if (index < leftAndHeadSize) {root.l = add(root.l, index, cur);} else {root.r = add(root.r, index - leftAndHeadSize, cur); //在右樹(shù)上位于自然時(shí)序的第幾位}root = maintain(root);return root;}private SBTNode<V> remove(SBTNode<V> root, int index) {//找到要?jiǎng)h除的節(jié)點(diǎn)過(guò)程中的沿途節(jié)點(diǎn)的size都要減1root.size--;int rootIndex = root.l != null ? root.l.size : 0;if (index != rootIndex) {if (index < rootIndex) {root.l = remove(root.l, index);} else {root.r = remove(root.r, index - rootIndex - 1);}return root;}if (root.l == null && root.r == null) {return null;}if (root.l == null) {return root.r;}if (root.r == null) {return root.l;}SBTNode<V> pre = null;SBTNode<V> suc = root.r;suc.size--;while (suc.l != null) {pre = suc;suc = suc.l;suc.size--;}if (pre != null) {pre.l = suc.r;suc.r = root.r;}suc.l = root.l;suc.size = suc.l.size + (suc.r == null ? 0 : suc.r.size) + 1;return suc;}private SBTNode<V> get(SBTNode<V> root, int index) {int leftSize = root.l != null ? root.l.size : 0;if (index < leftSize) {return get(root.l, index);} else if (index == leftSize) {return root;} else {return get(root.r, index - leftSize - 1);}}//add方法：在index位置加入numpublic void add(int index, V num) {SBTNode<V> cur = new SBTNode<V>(num); //先封裝一層，以區(qū)分相同的numif (root == null) {root = cur;} else {if (index <= root.size) {root = add(root, index, cur);}}}public V get(int index) {SBTNode<V> ans = get(root, index);return ans.value;}public void remove(int index) {if (index >= 0 && size() > index) {root = remove(root, index);}}public int size() {return root == null ? 0 : root.size;}}// 通過(guò)以下這個(gè)測(cè)試，// 可以很明顯的看到LinkedList的插入、刪除、get效率不如SbtList// LinkedList需要找到index所在的位置之后才能插入或者讀取，時(shí)間復(fù)雜度O(N)// SbtList是平衡搜索二叉樹(shù)，所以插入或者讀取時(shí)間復(fù)雜度都是O(logN)public static void main(String[] args) {// 功能測(cè)試int test = 50000;int max = 1000000;boolean pass = true;ArrayList<Integer> list = new ArrayList<>();SbtList<Integer> sbtList = new SbtList<>();for (int i = 0; i < test; i++) {if (list.size() != sbtList.size()) {pass = false;break;}if (list.size() > 1 && Math.random() < 0.5) {int removeIndex = (int) (Math.random() * list.size());list.remove(removeIndex);sbtList.remove(removeIndex);} else {int randomIndex = (int) (Math.random() * (list.size() + 1));int randomValue = (int) (Math.random() * (max + 1));list.add(randomIndex, randomValue);sbtList.add(randomIndex, randomValue);}}for (int i = 0; i < list.size(); i++) {if (!list.get(i).equals(sbtList.get(i))) {pass = false;break;}}System.out.println("功能測(cè)試是否通過(guò) : " + pass);// 性能測(cè)試test = 500000;list = new ArrayList<>();sbtList = new SbtList<>();long start = 0;long end = 0;start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * (list.size() + 1));int randomValue = (int) (Math.random() * (max + 1));list.add(randomIndex, randomValue);}end = System.currentTimeMillis();System.out.println("ArrayList插入總時(shí)長(zhǎng)(毫秒) ： " + (end - start));start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * (i + 1));list.get(randomIndex);}end = System.currentTimeMillis();System.out.println("ArrayList讀取總時(shí)長(zhǎng)(毫秒) : " + (end - start));start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * list.size());list.remove(randomIndex);}end = System.currentTimeMillis();System.out.println("ArrayList刪除總時(shí)長(zhǎng)(毫秒) : " + (end - start));start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * (sbtList.size() + 1));int randomValue = (int) (Math.random() * (max + 1));sbtList.add(randomIndex, randomValue);}end = System.currentTimeMillis();System.out.println("SbtList插入總時(shí)長(zhǎng)(毫秒) : " + (end - start));start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * (i + 1));sbtList.get(randomIndex);}end = System.currentTimeMillis();System.out.println("SbtList讀取總時(shí)長(zhǎng)(毫秒) :  " + (end - start));start = System.currentTimeMillis();for (int i = 0; i < test; i++) {int randomIndex = (int) (Math.random() * sbtList.size());sbtList.remove(randomIndex);}end = System.currentTimeMillis();System.out.println("SbtList刪除總時(shí)長(zhǎng)(毫秒) :  " + (end - start));}
}