前端面試之道30常見數(shù)據(jù)結(jié)構(gòu)

1、對于個算法來說，可能會計算出操作次數(shù)為 aN + 1，N 代表數(shù)據(jù)量。那么該算法的時間復(fù)雜度就是 O(N)。因為我們在計算時間復(fù)雜度的時候，數(shù)據(jù)量通常是常的，這時候低階項和常數(shù)項可以忽略不計。當(dāng)然可能會出現(xiàn)兩個算法都是 O(N) 的時間復(fù)雜度，那么對兩個算法的好壞就要通過對低階項和常數(shù)項了。棧概念棧是個線性結(jié)構(gòu)，在計算機中是個相當(dāng)常的數(shù)據(jù)結(jié)構(gòu)。棧的特點是只能在某端添加或刪除數(shù)據(jù)，遵循先進后出的原則實現(xiàn)每種數(shù)據(jù)結(jié)構(gòu)都可以很多種式來實現(xiàn)，其實可以把?？闯墒菙?shù)組的個集，所以這使數(shù)組來實現(xiàn)應(yīng)選取了 LeetCode 上序號為 20 的題(parentheses/submissions/1)題意是匹配括

2、號，可以通過棧的特性來完成這道題class Stack constructor() this.stack = push(item) this.stack.push(item)pop() this.stack.pop()peek() return this.stackthis.getCount() - 1getCount() return this.stack.lengthisEmpty() return this.getCount() = 0其實在 Vue 中關(guān)于模板容。的代碼，就有應(yīng)到匹配尖括號的內(nèi)隊列概念隊列是個線性結(jié)構(gòu)，特點是在某端添加數(shù)據(jù)，在另端刪除數(shù)據(jù)，遵循先進先出的原則。var i

3、sValid = function (s) let map = '(': -1,')': 1,'': -2,'': 2,'': -3,'': 3let stack = for (let i = 0; i < s.length; i+) if (mapsi < 0) stack.push(si) else let last = stack.pop()if (maplast + mapsi != 0) returnfalseif (stack.length > 0) return fa

4、lse return true;實現(xiàn)這會講解兩種實現(xiàn)隊列的式，分別是單鏈隊列和循環(huán)隊列。單鏈隊列因為單鏈隊列在出隊操作的時候需要 O(n) 的時間復(fù)雜度，所以引了循環(huán)隊列。循環(huán)隊列的出隊操作平均是 O(1) 的時間復(fù)雜度。循環(huán)隊列class SqQueue constructor(length) this.queue = new Array(length + 1)/ 隊頭this.first = 0/ 隊尾this.last = 0class Queue constructor() this.queue = enQueue(item) this.queue.push(item)deQueue(

5、) return this.queue.shift()getHeader() return this.queue0getLength() return this.queue.lengthisEmpty() return this.getLength() = 0/ 當(dāng)前隊列this.size = 0enQueue(item) / if隊尾 + 1 是否為隊頭如果是就代表需要擴容數(shù)組% this.queue.length 是為了防數(shù)組越界(this.first = (this.last + 1) %this.queue.length) this.resize(this.getLength() *

6、2 + 1)this.queuethis.last = item this.size+this.last = (this.last + 1) % this.queue.lengthdeQueue() if (this.isEmpty() throw Error('Queue is empty')let r = this.queuethis.first this.queuethis.first = null this.first = (this.first + 1) %this.queue.lengththis.size-/ if當(dāng)前隊列是否過為了保證不浪費空間，在隊列空間等于總

7、度四分之時且不為 2 時縮總度為當(dāng)前的半(this.size = this.getLength() / 4 &&this.getLength() / 2 != 0) this.resize(this.getLength() / 2)return r鏈表概念鏈表是個線性結(jié)構(gòu)，同時也是個天然的遞歸結(jié)構(gòu)。鏈表結(jié)構(gòu)可以充分利計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開getHeader() if (this.isEmpty() throw Error('Queue is empty')return this

8、.queuethis.firstgetLength() return this.queue.length - 1isEmpty() return this.first = this.lastresize(length) let q = new Array(length)for (let i = 0; i < length; i+) qi = this.queue(i + this.first) %this.queue.lengththis.queue = q this.first = 0 this.last = this.size銷較。實現(xiàn)單向鏈表class Node construct

9、or(v, next) this.value = v this.next = nextclass LinkList constructor() / 鏈表度this.size = 0/ 虛擬頭部this.dummyNode = new Node(null, null)find(header, index, currentIndex) if (index = currentIndex) return header return this.find(header.next, index,currentIndex + 1)addNode(v, index) this.checkIndex(index)

10、/ 當(dāng)往鏈表末尾插時，prev.next 為空/ 其他情況時，因為要插節(jié)點，所以插的節(jié)點/ 的 next 應(yīng)該是 prev.next/ 然后設(shè)置 prev.next 為插的節(jié)點let prev = this.find(this.dummyNode,index,0)prev.next = new Node(v, prev.next) this.size+return prev.nextinsertNode(v, index) return this.addNode(v,addToFirst(v) return this.addNode(v,addToLast(v) return this.add

11、Node(v,index)0)this.size)removeNode(index, isLast) this.checkIndex(index)index = isLast ? index - 1 : index let prev = this.find(this.dummyNode,0)let node = prev.next prev.next = node.next node.next = null this.size-return noderemoveFirstNode() return this.removeNode(0)removeLastNode() index,return

12、this.removeNode(this.size, true)樹樹擁有很多種結(jié)構(gòu)，的遞歸結(jié)構(gòu)。是最常的結(jié)構(gòu)，同時也是個天然擁有個根節(jié)點，每個節(jié)點多擁有兩個節(jié)點，分別為：左節(jié)點和右節(jié)點。樹的最底部節(jié)點稱之為葉節(jié)點，當(dāng)顆樹的葉數(shù)量數(shù)量為滿時，該樹可以稱之為滿。checkIndex(index) if (index < 0 | index > this.size) throw Error('Index error')getNode(index) this.checkIndex(index)if (this.isEmpty() returnreturn this.find

13、(this.dummyNode, index, 0).nextisEmpty() return this.size = 0getSize() return this.size分搜索樹分搜索是，擁有的特性。但是區(qū)別在于分搜索樹每個節(jié)點的值都他的的值，右樹的值。式很適合于數(shù)據(jù)搜索。如下圖所示，當(dāng)需要查找 6 的時這種候，因為需要查找的值根節(jié)點的值，所以只需要在根節(jié)點的右樹上尋找，提了搜索效率。實現(xiàn)class Node constructor(value) this.value = value this.left = null this.right = nullclass BST construct

14、or() this.root = null this.size = 0以上是最基本的分搜索樹實現(xiàn)，接下來實現(xiàn)樹的遍歷。對于樹的遍歷來說，有三種遍歷法，分別是先序遍歷、中序遍歷、后序遍歷。三種遍歷的區(qū)別在于何時節(jié)點。在遍歷樹的過程中，每個節(jié)點都會遍歷三次，分別是遍歷到，遍歷和遍歷右樹。如果需要實現(xiàn)先序遍歷，那么只需要第次遍歷到節(jié)點時進操作即可。getSize() return this.sizeisEmpty() return this.size = 0addNode(v) this.root = this._addChild(this.root, v)/ 添加節(jié)點時，需要較添加的節(jié)點值和當(dāng)前/

15、 節(jié)點值的_addChild(node, v) if (!node) this.size+return new Node(v)if (node.value > v) neft = this._addChild(neft, v) else if (node.value < v) node.right = this._addChild(node.right, v)return node/ 先序遍歷可于打印樹的結(jié)構(gòu)/ 先序遍歷先根節(jié)點，然后左節(jié)點，最后右節(jié)點。preTraversal() this._pre(this.root)_pre(node) if (node) console.l

16、og(node.value)this._pre(neft)this._pre(node.right)/中序遍歷可于排序?qū)τ?BST 來說，中序遍歷可以實現(xiàn)次遍歷就得到有序的值中序遍歷表示先左節(jié)點，然后根節(jié)點，最后右節(jié)點。midTraversal() this._mid(this.root)_mid(node) if (node) this._mid(neft)console.log(node.value)this._mid(node.right)/后序遍歷可于先操作節(jié)點再操作節(jié)點的場景后序遍歷表示先左節(jié)點，然后右節(jié)點，最后根節(jié)點。backTraversal() this._back(this.

17、root)以上的這種遍歷都可以稱之為深度遍歷，對應(yīng)的還有種遍歷叫做度遍歷，也就是層層地遍歷樹。對于度遍歷來說，我們需要利 之前講過的隊列結(jié)構(gòu)來完成。接下來先如何在尋找最值或最數(shù)。因為分搜索樹的特性，所以最值定在根節(jié)點的最左邊，最值相反breadthTraversal() if (!this.root) return null let q = new Queue()/ 將根節(jié)點隊q.enQueue(this.root)/ 循環(huán)隊列是否為空，為空/ 代表樹遍歷完畢while (!q.isEmpty() / 將隊出隊，是否有左右樹/ 有的話，就先左后右隊let n = q.deQueue() con

18、sole.log(n.value)if (n.left) q.enQueue(n.left) if (n.right) q.enQueue(n.right)_back(node) if (node) this._back(neft) this._back(node.right) console.log(node.value)向上取整和向下取整，這兩個操作是相反的，所以代碼也是類似的，這只如何向下取整。既然是向下取整，那么根據(jù)分搜索樹的特性，值定在根節(jié)點的左側(cè)。只需要直遍歷直到當(dāng)前節(jié)點的值不再于等于需要的值，然后節(jié)點是否還擁有右樹。如果有的話，繼續(xù)上的遞歸。getMin() return thi

19、s._getMin(this.root).value_getMin(node) if (!neft) return node return this._getMin(negetMax() return this._getMax(this.root).value_getMax(node) if (!node.right) return node return this._getMin(node.right)排名，這是于獲取給定值的排名或者排名第的節(jié)點的值，這兩個操作也是相反的，所以這個只如何獲取排名第的節(jié)點的值。對于這個操作，我們需要略微的改造點代碼，讓每個節(jié)點擁有個size 屬性。該屬性表示該

20、節(jié)點下有多少節(jié)點（包含身）。class Node constructor(value) this.value = value this.left = null this.right = null/ 修改代碼this.size = 1/ 新增代碼_getSize(node) floor(v) let node = this._floor(this.root, v) return node ? node.value : null_floor(node, v) if (!node) return nullif (node.value = v) return v/ 如果當(dāng)前節(jié)點值還需要的值，就繼續(xù)遞歸

21、if (node.value > v) return this._floor(neft, v)/當(dāng)前節(jié)點是否擁有右樹let right = this._floor(node.right, v) if (right) return rightreturn nodereturn node ? node.size : 0_addChild(node, v) if (!node) return new Node(v)if (node.value > v) / 修改代碼node.size+neft = this._addChild(neft, v) else if (node.value &

22、lt; v) / 修改代碼node.size+node.right = this._addChild(node.right,return nodev)select(k) let node = this._select(this.root, k)return node ? node.value : null_select(node, k) if (!node)/ 先獲取return null下有個節(jié)點let/size =neft ? neft.size : 0size 是否于 k/ if/k，代表所需要的節(jié)點在左節(jié)點k) return this._select(nk，代表所需要的節(jié)點在右節(jié)點如果

23、于(size >如果于eft, k)注意這需要重新計算 k，減去根節(jié)點除了右樹的節(jié)點數(shù)量if(size < k) return this._select(node.right, k-size - 1)接下來講解的是分搜索最難實現(xiàn)的部分：刪除節(jié)點。因為對于刪除節(jié)點來說，會以下種情況需要刪除的節(jié)點沒有樹需要刪除的節(jié)點只有條樹需要刪除的節(jié)點有左右兩條樹對于前兩種情況很好解決，但是第三種情況就有難度了，所以先來實現(xiàn)相對簡單的操作：刪除最節(jié)點，對于刪除最節(jié)點來說，是不存在第三種情況的，刪除最節(jié)點操作是和刪除最節(jié)點相反的，所以這也就不再贅述。delectMin() this.root = th

24、is._delectMin(this.root) console.log(this.root)_delectMin(node) / 直遞歸/ 如果為空，就節(jié)點是否擁有右樹/ 有右樹的話就把需要刪除的節(jié)點替換為右樹if (node != null) & !neft) return node.rightneft = this._delectMin(neft)/ 最后需要重新維護下節(jié)點的 sizenode.size = this._getSize(neft) + this._getSize(node.right) + 1return nodereturn node最后講解的就是如何刪除任意節(jié)

25、點了。對于這個操作，T.Hibbard 在 1962 年提出了解決這個難題的辦法，也就是如何解決第三種情況。當(dāng)遇到這種情況時，需要取出當(dāng)前節(jié)點的后繼節(jié)點（也就是當(dāng)前節(jié)點右樹的最節(jié)點）來替換需要刪除的節(jié)點。然后將需要刪除節(jié)點的賦值給后繼結(jié)點，右樹刪除后繼結(jié)點后賦值給他。你如果對于這個解決辦法有疑問的話，可以這樣考慮。因為分搜索樹的特性，節(jié)點定所有左節(jié)點，所有右節(jié)點。那么當(dāng)需要刪除節(jié)點時，勢必需要拿出個節(jié)點的節(jié)點來替換節(jié)點。這個節(jié)點肯定不樹，必然樹。然后需要保持節(jié)點都是右節(jié)點的，那么就可以取出右那個節(jié)點來替換節(jié)點。最的delect(v) this.root = this._delect(this.

26、root, v)_delect(node, v) if (!node) return null/ 尋找的節(jié)點當(dāng)前節(jié)點，去找if (node.value < v) node.right = this._delect(node.right, v) else if (node.value > v) / 尋找的節(jié)點當(dāng)前節(jié)點，去右樹找neft = this._delect(neft, v) else / 進這個條件說明已經(jīng)找到節(jié)點/ 先節(jié)點是否擁有擁有左右的個/ 是的話，將樹返回出去，這和 _delectMin 的操作樣if (!neft) return node.right if (!no

27、de.right) return neftAVL 樹概念分搜索樹實際在業(yè)務(wù)中是受到限制的，因為并不是嚴(yán)格的O(logN)，在情況下會成鏈表，如加組升序的數(shù)字就會造成這種情況。AVL 樹改進了分搜索樹，在 AVL任意節(jié)點的左右樹的度差都不于 1，這樣保證了時間復(fù)雜度是嚴(yán)格的 O(logN)。基于此， 對 AVL 樹增加或刪除節(jié)點時可能需要旋轉(zhuǎn)樹來達到度的平衡。實現(xiàn)因為 AVL 樹是改進了分搜索樹，所以部分代碼是于分搜索復(fù)的，對于重復(fù)內(nèi)容不作再次。/ 進這，代表節(jié)點擁有左右樹/ 先取出當(dāng)前節(jié)點的后繼結(jié)點，也就是取當(dāng)前節(jié)點右樹的最值let min = this._getMin(node.right)

28、/ 取出最值后，刪除最值/ 然后把刪除節(jié)點后的樹賦值給最值節(jié)點min.right = this._delectMin(node.right)/不動min.left = neft node = min/ 維護 sizenode.size = this._getSize(neft) + this._getSize(node.right) + 1return node對于 AVL 樹來說，添加節(jié)點會有四種情況情況來說，新增加的節(jié)點位于節(jié)點 2 的左側(cè)，這時樹已經(jīng)對不平衡，需要旋轉(zhuǎn)。因為搜索樹的特性，節(jié)點左節(jié)點，右節(jié)點，所以旋轉(zhuǎn)以后也要實現(xiàn)這個特性。旋轉(zhuǎn)之前：new < 2 < C <

29、; 3 < B < 5 < A，右旋之后節(jié)點 3 為根節(jié)點，這時候需要將節(jié)點 3 的右節(jié)點加到節(jié)點 5 的左邊，最后還需要更新節(jié)點的度。對右情況來說，相反情況，所以不再贅述。右情況來說，新增加的節(jié)點位于節(jié)點 4 的右側(cè)。對于這種情對況，需要通過兩次旋轉(zhuǎn)來達到的。先對節(jié)點的左節(jié)點左旋，這時次右旋就可以達到的。的情況，再對節(jié)點進class Node constructor(value) this.value = value this.left = null this.right = null this.height = 1class AVL constructor() this.

30、root = nulladdNode(v) this.root = this._addChild(this.root, v)_addChild(node, v) if (!node) return new Node(v)if (node.value > v) neft = this._addChild(neft, v) else if (node.value < v) node.right = this._addChild(node.right, v) else node.value = vnode.height =1 + Math.max(this._getHeight(neft

31、),this._getHeight(node.right)let factor = this._getBalanceFactor(node)/ 當(dāng)需要右旋時，根節(jié)點的定右樹度if (factor > 1 &&this._getBalanceFactor(neft) >= 0) return this._rightRotate(node)/ 當(dāng)需要左旋時，根節(jié)點的if (factor < -1 &&定右樹度矮this._getBalanceFactor(node.right) <= 0) return this._leftRotate(no

32、de)/ 左右情況/ 節(jié)點的的if (factor > 1 && this._getBalanceFactor(n右樹，且節(jié)點的的右樹節(jié)點的eft) < 0) neft = this._leftRotate(neft)return this._rightRotate(node)/ 右左情況/ 節(jié)點的右樹矮，且節(jié)點的右樹的右樹節(jié)點的右樹的矮if (factor < -1 && this._getBalanceFactor(node.right) > 0) node.right = this._rightRotate(node.right)

33、return this._leftRotate(node)return node_getHeight(node) if (!node) return 0 return node.height_getBalanceFactor(node) return this._getHeight(neft) -this._getHeight(node.right)/ 節(jié)點右旋/52/26=>15/ / 3 61/ new3new_rightRotate(node)/ 旋轉(zhuǎn)后新根節(jié)點let newRoot = n/ 需要移動的節(jié)點eftlet moveNode = newRoot.right/ 節(jié)點 2

34、 的右節(jié)點改為節(jié)點 5newRoot.right = node/ 節(jié)點 5 左節(jié)點改為節(jié)點 3neft = moveNode/ 更新樹的度node.height =1 + Math.max(this._getHeight(neft),this._getHeight(node.right) newRoot.height =1 +Math.max(this._getHeight(newRoot.left),this._getHeight(newRoot.right)return newRoot/ 節(jié)點左旋/46/Trie概念/26=>47/ /5725new/new_leftRotate(n

35、ode) / 旋轉(zhuǎn)后新根節(jié)點let newRoot = node.right/ 需要移動的節(jié)點let moveNode = newRoot.left/ 節(jié)點 6 的左節(jié)點改為節(jié)點 4newRoot.left = node/ 節(jié)點 4 右節(jié)點改為節(jié)點 5node.right = moveNode/ 更新樹的度node.height =1 + Math.max(this._getHeight(neft), this._getHeight(node.right)newRoot.height = 1 +Math.max(this._getHeight(newRoot.left), this._getH

36、eight(newRoot.right)return newRoot在計算機科學(xué)，trie，稱前綴樹或字典樹，是種有序樹，于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。簡單點來說，這個結(jié)構(gòu)的作多是為了便搜索字符串，該下個特點以根節(jié)點代表空字符串，每個節(jié)點都有 N（假如搜字符，就有 26 條） 條，每條代表個字符，這點和其他的樹結(jié)構(gòu)不同節(jié)點不字符，只有路徑才從根節(jié)點開始到任意個節(jié)點，將沿途經(jīng)過的字符連接起來就是該節(jié)點對應(yīng)的字符串、實現(xiàn)總得來說 Trie 的實現(xiàn)相別的樹結(jié)構(gòu)來說簡單的很多，實現(xiàn)就以搜字符為例。class TrieNode constructor() / 代表每個字符經(jīng)過節(jié)點的次數(shù)this.

37、path = 0/ 代表到該節(jié)點的字符串有個this.end = 0/this.next = new Array(26).fill(null)class Trie constructor() / 根節(jié)點，代表空字符this.root = new TrieNode()/ 插字符串insert(str) if (!str) returnlet node = this.rootfor (let i = 0; i < str.length; i+) / 獲得字符先對應(yīng)的索引let index = stri.charCodeAt() - 'a'.charCodeAt()/ 如果索引

38、對應(yīng)沒有值，就創(chuàng)建if (!node.nextindex) node.nextindex = new TrieNode()node.path += 1node = node.nextindexnode.end += 1/ 搜索字符串出現(xiàn)的次數(shù)search(str) if (!str) returnlet node = this.rootfor (let i = 0; i < str.length; i+) let index = stri.charCodeAt() -'a'.charCodeAt()/ 如果索引對應(yīng)沒有值，代表沒有需要搜素的字符串if (!node.nex

39、tindex) return 0node = node.nextindexreturn node.end/ 刪除字符串delete(str) if (!this.search(str) return let node = this.rootfor (let i = 0; i < str.length; i+) let index = stri.charCodeAt() -'a'.charCodeAt()/的字符串/if如果索引對應(yīng)的節(jié)點的 Path 為 0，代表經(jīng)過該節(jié)點已經(jīng)個，直接刪除即可(-node.nextindex.path = 0) node.nextindex

40、 = nullreturn并概念并是種特殊的樹結(jié)構(gòu)，于處理些不交集的合并及問題。該結(jié)構(gòu)中每個節(jié)點都有個節(jié)點，如果只有當(dāng)前個節(jié)點，那么該節(jié)點的節(jié)點指向。這個結(jié)構(gòu)中有兩個重要的操作，分別是：Find：確定元素屬于哪個集。它可以被來確定兩個元素是否屬于同集。Union：將兩個集合并成同個集合。實現(xiàn)class DisjointSet node = node.nextindexnode.end -= 1/ 初始化樣本constructor(count) / 初始化時，每個節(jié)點的節(jié)點都是this.parent = new Array(count)/ 于樹的深度，優(yōu)化搜索復(fù)雜度this.rank = new

41、 Array(count)for (let i = 0; i < count; i+) this.parenti = i this.ranki = 1find(p) /尋找當(dāng)前節(jié)點的節(jié)點是否為，不是的話表示還沒找到/開始進路徑壓縮優(yōu)化假設(shè)當(dāng)前節(jié)點節(jié)點為 A將當(dāng)前節(jié)點掛載到 A 節(jié)點的節(jié)點上，達到壓縮深度的的while (p != this.parentp) this.parentp =this.parentthis.parentpp = this.parentpreturn pisConnected(p, q) return this.find(p) = this.find(q)/ 合并union(p, q) / 找到兩個數(shù)字的節(jié)點let i = this.find(p)let j = this.find(q)堆概念堆通常是個可以被看做棵樹的數(shù)組對象。堆的實現(xiàn)通過構(gòu)造下性質(zhì)。，實為的種。這種數(shù)據(jù)結(jié)構(gòu)具有以任意節(jié)點于（或于）它的所有節(jié)點堆總是棵完全樹。即除了最底層，其他層的節(jié)點都被元素填滿，且最底層從左到右填。將根節(jié)點最的堆叫做最堆或根堆，根節(jié)點最的堆叫做最堆或根堆。優(yōu)先隊列也完全可以堆來