-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-10-5.html
1270 lines (1245 loc) · 47.9 KB
/
1-10-5.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="icon" href="./public/favicon.ico" />
<meta http-equiv="cache-control" content="no-cache" />
<title></title>
<link rel="stylesheet" href=" https://necolas.github.io/normalize.css/8.0.1/normalize.css" />
<link rel="stylesheet" href="./hightlight/default.min.css" />
<link rel="stylesheet" href="./css/main.css" />
<link rel="stylesheet" href="./css/copybutton.css" />
<link rel="stylesheet" href="./css/hightlight.css" />
<script src="./hightlight/hightlight.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.11/clipboard.min.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-BEVZJDBC7Z"></script>
<script src="./js/gtag.js"></script>
</head>
<body>
<header>
<nav>
<h1>
<span id="toggle-menu"></span>
<a href="index.html"></a>
</h1>
</nav>
</header>
<main>
<aside>
<nav></nav>
</aside>
<article>
<h2 id="1-10-5">1-10-5 資料結構</h2>
<p>
資料結構是電腦中組織和儲存資料的特定方式,目的是方便且高效率地對資料進行存取和修改。一方面,資料結構表述了資料之間的關係,以及操作資料的一系列方法,資料又是程式的基本單元,因此無論是哪種語言、哪個領域,都離不開資料結構:另一方面,資料結構是演算法的基礎,其本身包含了演算法的部分內容。也就是說,想要掌握演算法,先有一個牢固的資料結構基礎是必要條件。
</p>
<p>
前端領域也到處表現資料結構的應用,尤其是隨需求的複雜度上升,前端工程師越來越離不開資料結構。React、Vue
些設計的架構,上線文件編輯系統、大型管理系統,甚至一個簡單的檢索需求,都離不開資料結構的支援。是否掌握了這個困難是進階的重要考量。
</p>
<p>資料結構分為以下8大類。</p>
<ul>
<li>陣列:Array</li>
<li>堆疊:Stack</li>
<li>佇列:Queue</li>
<li>結串列:LinkedList</li>
<li>樹:Tree</li>
<li>圖:Graph</li>
<li>字典樹:Trie</li>
<li>雜湊表(雜湊表):Hash Table</li>
</ul>
<h3>堆疊和佇列</h3>
<p>
堆疊和佇列是一種操作受限的線性結構,它們非常簡單,雖然 JavaScript
並沒有原生內建這樣的資料結構,但是可以輕鬆地將它們模擬出來。
</p>
<p>堆疊的實現遵循後進先出(Last,First Out LIFO) 原則,範例程式如下：</p>
<pre><code class="language-js">
class Stack {
constructor(...args) {
this.stack = {...args}
}
// Modifiers
push(...items) {
return this.stack.push(... items)
}
pop() {
return this.stack.pop()
}
peek() {
// Element access
return this.isEmpty()
? undefined
: this.stack[this. size () - 1]
}
// Capacity
isEmpty() {
return this.size() == 0
}
size() {
return this.stack.length
}
}
</code></pre>
<p>佇列的實現遵循先進先出(First in, First out FIFO )原則,範例程式如下：</p>
<pre><code class="language-js">
class Queue {
constructor(. ..args) {
this.queue = [...args]
}
// Modifiers
enqueue(...items) {
return this.queue.push(... items)
}
dequeue () {
return this.queue.shift()
}
// Element access
front() {
return this.isEmpty()
? undefined
: this.queue[0]
}
back () {
return this.isEmpty()
? undefined
: this.queue[this.size() - 1]
}
// Capacity
isEmpty() {
return this.size() == 0
}
size() {
return this.queue.length
}
}
</code></pre>
<p>堆疊和佇列的實際應用場景比比皆是,例如下面這些。</p>
<ul>
<li>瀏覽器的歷史記錄,因為回復總是回復到上一個最近的頁面,所以它需要遵循堆疊的原則。</li>
<li>與瀏覽器的歷史記錄類似,任何 undo/redo 都是以堆疊為基礎的實現。</li>
<li>在程式中,廣泛應用遞迴產生的呼叫堆疊同樣也是堆疊思想的表現。</li>
<li>同上,瀏覽器在拋出例外時,通常都會拋出呼叫堆疊資訊。</li>
<li>在電腦科學領域中的應用也比較廣泛,如進位轉換、括號比對、堆疊混洗、運算式求值等。</li>
<li>
佇列的應用更為直觀,所謂的巨任務/微任務都是佇列, 不管是什麼類型的任務,都是先進先執行。
</li>
<li>
在後端中的應用也比較廣泛,如訊息佇列(RabbitMQ、ActiveMQ
等)，這種佇列能造成延遲緩衝的功效。
</li>
</ul>
<p>
總結以上，不管是堆疊還是佇列,都是用陣列來模擬的。陣列是最基本的資料結構,但是它的價值是驚人的。這裡稍微提一下,React
中 hook 從本質上看可以簡單地被看作陣列。
</p>
<h3>鏈結串列</h3>
<p>
堆疊和佇列都可以用陣列實現,鏈結串列同樣和陣列一樣,都是按照一定的順序儲存元素的,不同的地方在於鏈結串列不能像陣列一樣透過索引對元素進行存取,而是透過每個元素指向其下一個元素的方式進行存取。
</p>
<p>
直觀上可得出這樣一個結論:鏈結串列不需要一段連續的儲存空間,「指向下一個元素」的方式能夠更大限度地利用記憶體。
</p>
<p>根據以上結論可以繼續歸納出鏈結串列的優點,如下。</p>
<ul>
<li>鏈結串列的插入和刪除操作的時間複雜度是常數級的,只需要改變相關節點的指標指向即可。</li>
<li>鏈結串列可以像陣列一樣循序存取元素，尋找元素的時間複雜度是線性的。</li>
</ul>
<p>下面來看一看鏈結串列的應用場景。</p>
<p>
React 的核心演算法 Fiber 就是透過串列實現的。 React 最早使用堆疊協調(stack
reconciler)排程演算法。堆疊協調排程演算法最大的問題在於它是像函數呼叫堆疊一樣,遞迴地自頂向下地進行
diff 和 render
相關操作的,在堆疊協調排程演算法執行的過程中,該排程演算法始終佔據瀏覽器主執行緒。也就是說在此期間,使用者的互動所觸發的版面配置行為、動畫執行任務都不會被立即回應,進一步影響使用者體驗。
</p>
<p>
因此,React Fiber 將繪製更新過程進行了拆解,簡單說,就是每次檢查虛擬 DOM
的一小部分,在檢查間隙會檢查是否還有時間繼續執行下一個虛擬 DOM
樹上的某個分支任務,同時觀察是否有更優先的任務需要回應,如果沒有時間執行下一個虛擬 DOM
上的某個分支任務,有更高優先順序的任務,React
就會讓出主執行緒,直到主執行緒不忙的時候繼續執行那個分支任務。
</p>
<p>
所以,React
Fiber其實很簡單,將堆疊協調過程分成區塊,一次執行一區塊,執行完一區塊之後需要將結果儲存起來,根據是否還有空閒的回應時間
(requestIdleCallback)來決定下一步策略。當所有的區塊都已經執行完畢後,就進入提交階段,這個階段需要更新
DOM,整個過程是一口氣同步完成的。
</p>
<p>
React Fiber 是專門用於 React
元件堆疊呼叫的重新實現,可以隨意中斷呼叫堆疊並手動操作呼叫堆疊,也就是說一個 Fiber
就是一個虛擬堆疊幀,其結構如下所示。
</p>
<pre><code class="language-js">
function FiberNode(
tag: WorkTag,
pendingProps: mixed,
key: null | string,
mode: TypeOfMode,
){
// Instance
// ...
this.tag = tag;
// Fiber
this.return = null;
this.child = null;
this.sibling = null;
this.index = 0;
this.ref = null;
this pendingProps = pendingProps;
this.memoizedProps = null;
this.updateQueue = null;
this.memoizedState = null;
this.dependencies = null;
// Effects
// ...
this.alternate = null;
}
</code></pre>
<p>
這麼看,Fiber 就是一個物件,透過 parent、children、sibling, 同時,parent、children、sibling
又都是 Fiber 結構,FiberNode.alternate 這個屬性用來儲存上一次繪製的結果,事實上整個 Fiber
模式就是一個鏈結串列。React
也借此從依賴於內建堆疊同步遞迴模型,變為具有鏈結串列和指標的非同步模型了。
</p>
<p>實際的繪製過程如下。</p>
<pre><code class="language-js">
function renderNode(node) {
// 判斷是否需要繪製該節點,如果 props 發生變化,則呼叫 render
if (node.memoizedProps !== node.pendingProps) {
render(node)
}
// 是否有子節點,如果有則進行子節點繪
if (node.child !== null) {
return node.child
// 是否有兄弟節點,如果有則進行兄弟節點繪製
} else if (node.sibling !== null){
return node.sibling
// 沒有子節點和兄弟節點
}else if (node.return !== null){
return node. return
} else {
return null
}
}
function workloop(root) {
nextNode = root
while (nextNode !== null && (no other high priority task)) {
nextNode = renderNode (nextNode)
}
}
</code></pre>
<p>
注意,在 workloop 中, while 的條件是 nextNode!==null &&(no other high priority
task)，這是描述 Fiber
工作原理的關鍵虛擬程式碼。以上只是簡略的虛體程式碼用於說明鏈接串列的資料結構，並沒有介紹
requestAnimationFame(callback)和 requestIdleCallback(callback)
的實現，這裏重點是體會鏈結串列資料結構的思想。
</p>
<h3>鏈結串列實現</h3>
<p>實現鏈結串列首先串進行分類,常見的有單向鏈接串列和雙向鏈結串列。</p>
<p>有了節點類別,下面來初步實現雙向鏈結串列類別</p>
<ul>
<li>
單向鏈結串列:單向鏈結串列是維護一系列節點的資料結構,其特點是每個節點都包含資料,同時包含指向鏈結串列中下一個節點的指標。
</li>
<li>
雙向鏈結串列:與單向鏈結串列不同,雙向鏈結串列的特點是每個節點除了包含其資料,還包含分別指向其前驅節點和後繼節點的指標。
</li>
</ul>
<p>(單向案例要另外找)</p>
<p>根據雙向鏈結串列的特點,實現一個節點建構函數(節點類別)的程式如下。</p>
<pre><code class="language-js">
class DoublyLinkedList {
constructor() {
// 雙向鏈結串列的開頭
this.head = null
// 雙向鏈結串列的結尾
this.tail = null
}
// ...
}
</code></pre>
<p>接下來,需要實現雙向鏈結串列原型中的一些方法,這些方法包含以下幾種。</p>
<ul>
<li>add:在鏈結串列尾部增加一個新的節點。</li>
<li>addAt:在鏈結串列指定位置增加一個新的節點。</li>
<li>remove:刪除鏈結串列指定資料項目節點。</li>
<li>removeAt:刪除鏈結串列指定位置節點。</li>
<li>reverse:翻轉鏈結串列。</li>
<li>swap:交換兩個節點資料。</li>
<li>isEmpty:查詢鏈結串列是否為空。</li>
<li>length:查詢鏈結串列長度。</li>
<li>traverse:檢查鏈結串列。</li>
<li>find:尋找某個節點的索引。</li>
</ul>
<p>來逐一實現鏈結串列的各種方法，add方法的程式如下。</p>
<pre><code class="language-js">
add(item) {
// 產生實體一個節點
let node = new Node(item)
// 如果目前鏈結串列還沒有頭
if(!this.head) {
this.head = node
this.tail = node
}
//如果目前鏈結串列已經有了頭,則只需要在尾部加上該節點
else {
node.prev = this.tail
this.tail.next = node
this.tail = node
}
}
</code></pre>
<p>addAt 方法的程式如下。</p>
<pre><code class="language-js">
addAt(index, item) {
let current = this.head
let counter = 1
let node = new Node(item)
//如果在頭部插入
if (index === 0) {
this.head.prev = node
node.next = this.head
this.head = node
}
//如果在非頭部插入,則需要從頭開始找尋插入位置
else {
while(current) {
current = current.next
if( counter === index) {
node.prev = current.prev
current.prev.next = node
node.next = current
current.prev = node
}
counter++
}
}
}
</code></pre>
<p>remove 方法的程式如下。</p>
<pre><code class="language-js">
remove(item) {
let current = this.head
while (current) {
//找到了目標節點
if (current.data === item ) {
//目標鏈結串列只有目前目標項,即目標節點既是鏈結串列頭又是鏈結串列尾
if (current == this.head && current == this.tail) {
this.head = null
this.tail = null
}
//目標節點為鏈結串列頭
else if (current == this.head ) {
this.head = this.head.next
this.head.prev = null
}
//目標節點為鏈結串列尾
else if (current == this.tail ) {
this.tail = this.tail.prev;
this.tail.next = null;
}
//目標節點在鏈結串列首尾之間,即中部
else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
current = current.next
}
}
</code></pre>
<p>removeAt方法的程式如下。</p>
<pre><code class="language-js">
removeAt (index) {
// 都是從頭開始檢查
let current = this.head
let counter = 1
//删除鏈結串列頭部
if (index === 0 ) {
this.head = this.head.next
this.head.prev = null
}
else {
while(current) {
current = current.next
//如果目標節點在鏈結串列尾部
if (current == this.tail) {
this.tail = this.tail.prev
this.tail.next = null
}
else if (counter === index) {
current.prev.next = current.next
current.next.prev = current.prev
break
}
counter++
}
}
}
</code></pre>
<p>reverse 方法的程式如下。</p>
<pre><code class="language-js">
reverse() {
let current = this.head
let prev = null
while (current) {
let next = current.next
//前後倒置
current.next = prev
current.prev = next
prev = current
current = next
}
this.tail = this.head
this.head = prev
}
</code></pre>
<p>swap方法(用於交換兩個節點的資料值)的程式如下。</p>
<pre><code class="language-js">
swap(index1, index2) {
// 使 index1 始終小於 index2 ,方便後面尋找交換
if (index1 > index2) {
return this.swap(index2, index1)
}
let current = this.head
let counter = 0
let firstNode
while(current !== null) {
// 找到第一個節點,並儲存起來
if (counter === index1 ){
firstNode = current
}
//找到第二個節點,並進行資料交換
else if (counter === index2) {
// ES 提供了更簡潔的交換資料的方法,這裡用傳統方式實現更為直觀
let temp = current.data
current.data = firstNode.data
firstNode.data = temp
}
current = current.next
counter++
}
return true
}
</code></pre>
<p>isEmpty 方法的程式如下。</p>
<pre><code class="language-js">
isEmpty () {
return this.length() < 1
}
</code></pre>
<p>isEmpty 方法使用了 length 方法實現，length 方法的程式如下。</p>
<pre><code class="language-js">
length() {
let current = this.head
let counter = 0
while(current !== null) {
counter++
current = current.next
}
return current
}
</code></pre>
<p>length 方法透過檢查結串列傳回鏈結串列長度。</p>
<p>traverse 方法的程式如下。</p>
<pre><code class="language-js">
traverse (fn) {
let current = this.head
while(current !== null) {
fn(current)
current = current.next
}
return true
}
</code></pre>
<p>
有了上面 length 方法的檢查實現， traverse 方法也就不難了解了，它接收一個檢查執行函數,在
while 循環中進行呼叫。
</p>
<p>最後，search方法的程式如下。</p>
<pre><code class="language-js">
search(item) {
let current = this.head
let counter = 0
while( current ) {
if( current.data == item ) {
return counter
}
current = current.next
counter++
}
return false
}
</code></pre>
<p>
至此就實現了所有 DoublyLinkedList
類別向鏈結串列的方法。仔細分析一下整個實現過程可以發現,雙向鏈結串列的實現並不複雜,在手寫過程中需要開發者做到「心中有表」,考慮到目前節點的
next 和 prev 設定值,其在邏輯實現上還是很簡單的。
</p>
<p>
掌握了這些內容,再回想一下鏈結串列的應用,以及 React Fiber
的設計和實現,也許一切就都變得不再神秘。
</p>
<h3>樹</h3>
<p>
不同於之前介紹，樹是非線性的。因為樹決定了其儲存的資料有明確的層級關係，因此對於維護具有層級特性的資料,樹是一個天然良好的選擇。
</p>
<p>前面提到,樹有很多種分類,但是它們都具有以下特性。</p>
<ul>
<li>除了根節點,所有的節點都有一個父節點。</li>
<li>每一個節點都可以有許多個子節點,如果沒有子節點,那麼就稱此節點為葉子節點。</li>
<li>一個節點所擁有的葉子節點的個數被稱為該節的度,因此葉子節點的度為0。</li>
<li>在所有節點中,最大的度為整棵樹的度。</li>
<li>樹的最大層次被稱為樹的深度。</li>
</ul>
<p>
從應用上來看,前端開中的DOM 就是樹狀結構;同理,不管 是React 還是 Vue 的虛擬 DOM 也都是樹。
</p>
<h4>二元搜尋樹的實現和檢查</h4>
<p>
二元樹是最基本的樹,因為它的結構最簡單,每個節點最多包含兩個子節點。二元樹又非常有用,因為根據二元樹可以延伸出二元搜尋樹(BST)、平衡二元搜尋樹(AVL)、紅黑樹(R/BTree)等。
</p>
<p>二元搜尋樹有以下特性。</p>
<ul>
<li>左子樹上所有節點的值均小於或等於它的根節點的值。</li>
<li>右子樹上所有節點的值均大於或等於它的根節點的值。</li>
<li>左、右子樹也分別為二元搜尋樹。</li>
</ul>
<p>根據其特性實現二元搜尋樹時，應該先建置一個節點類別,如下所示。</p>
<pre><code class="language-js">
class Node{
constructor(data) {
this.left = null
this.right = null
this.value = data
}
}
</code></pre>
<p>接著,按照慣例實現二元搜尋樹的以下方法。</p>
<ul>
<li>insertNode:根據一個父節點插入一個子節點。</li>
<li>insert:插入一個新節點。</li>
<li>removeNode:根據一個父節移除一個子節點。</li>
<li>remove:移除一個節點。</li>
<li>findMinNode:取得子節點的最小值。</li>
<li>searchNode:根據一個節點找子節點。</li>
<li>search:尋找節點。</li>
<li>preOrder:前序検查。</li>
<li>InOrder:中序檢查。</li>
<li>PostOrder:後續檢查。</li>
</ul>
<p>下面來實現樹結構的各種方法，insertNode 和 insert 方法的程式如下。</p>
<pre><code class="language-js">
insertNode (root, newNode) {
if (newNode.value < root.value) {
(root.left) ? root.left= newNode : this.insertNode(root.left,newNode)
} else {
(!root.right) ? root.right =newNode : this.insertNode(root.right,newNode)
}
}
insert (value) {
let newNode = new Node(value)
if (!this.root) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
</code></pre>
<p>
insertNode方法先判斷目標父的值,如果插入節點的值更小,則放到父節點的左邊,接著遞迴呼this.insertNode(root.left,newNode);
如果插入節點的值更大,則放到父節點的右邊。
</p>
<p>insert 方法中多了建置 Node 節點實例這一步,而 removeNode 和 remove 方法 的程式如下。</p>
<pre><code class="language-js">
removeNode(root, value) {
if(!root) {
return null
}
if (value < root.value) {
root.left = this.removeNode(root.left, value)
return root
} else if (value > root.value) {
root.right = tis.removeNode(root.right, value)
return root
} else {
//找到需要刪除的節點
//如果目前 root 節點無左右子節點
if (!root.left && !root.right) {
root = null
return root
}
// 只有左節點
if (root.left && !root.right) {
root = root.left
return root
}
// 只有右節點
else if (root,right) {
root = root.right
return root
}
// 有左右兩個子節點
let minRight = this.findMinNode(root.right)
root.value = minRight.value
root.right = this.removeNode(root.right, minRight.value)
return root
}
}
remove (value) {
if (this.root) {
this.removeNode(this.root, value)
}
}
</code></pre>
<p>上述程式可能最需要思考的就是要刪除的節點含有左右兩個子節點的情況。</p>
<p>
當需要刪除的節點(目標節點)含有左右兩個子節點時,因為要把目前節點刪除,所以就需要找到合適的補位節點,這個補位節點一定在該目標節點的右側樹中,因為這樣才能確保補位節點的值一定大於該目標節點的左側樹所有節點的值,而該目標節點的左側樹不需要調整;同時,為了確保補位節點的值一定要小於該目標節點的右側樹節點的值,要找到的補位節點應該是該目標節點的右側樹中值最小的那個節點。下面借助
this.fndMinNode 方法實現這個過程。
</p>
<pre><code class="language-js">
findMinNode (root) {
if (!root.left) {
return root
} else {
return this.findMinNode(root.left)
}
}
</code></pre>
<p>該方法會不斷進行遞迴,直到找到最左側的葉子節點。</p>
<p>尋找節點的方法(searchNode 和 search) 的實現程式如下。</p>
<pre><code class="language-js">
searchNode(root, value) {
if (!root) {
return null
}
if (value < root.value) {
return this.searchNode(root.left, value)
}else if (value > root.value) {
return this.searchNode(root.right, value)
}
return root
}
search(value) {
if (!this.root) {
return false
}
return Boolean(this.searchNode(this.root, value))
}
</code></pre>
<p>前序檢查程式如下。</p>
<pre><code class="language-js">
preOrder(root) {
if (root) {
console.log(root.value)
this.preOrder(root.left)
this.preOrder(root.right)
}
}
</code></pre>
<p>中序檢查的範例程式如下。</p>
<pre><code class="language-js">
inOrder(root) {
if (root) {
this.inOrder(root.left)
console,log(root.value)
this.inOrder(root.right)
}
}
</code></pre>
<p>後序檢查的範例程式如下。</p>
<pre><code class="language-js">
postOrder(root) {
if (root) {
this.postOrder(root.left)
this.postOrder(root.right)
console.log(root.value)
}
}
</code></pre>
<p>前序檢查、中序查、後序查的區別其實就在於,執行console.log(root.value)方法的位置不同。</p>
<h4>字典樹</h4>
<p>
樹(Trie)是針對特定類型的搜尋而最佳化的樹資料結構,典型的實例是
autoComplete,也就是說,它適合實現透過部分值得到完整值的場景。字典樹因此也是一種搜尋樹,有時候也被叫作字首樹,因為任意一個節點的後代都
存在共同的字首。下面歸納一下它的特點。
</p>
<ul>
<li>
字典樹能做到高效查詢和插入,時間複雜度為O(k),
k為字串長度。但是如果大量字串沒有共同字首,那就會很耗記憶體,
</li>
<li>最極端的情況,所有字都沒有共同字首時,這棵字典樹的圖形可以幫助理解這一點。</li>
<li>
字典樹的核心就是減少不必要的字元比較,獲得較高的查詢效率,也就是說用空間換時間,再利用共同字首來加強查詢效率。
</li>
</ul>
<p>
除了剛剛提到的 autoComplete
自動填充的情況,字典樹還有很多其他應用場景,例如搜尋、輸入法選項、分類、IP位址檢索、電話號碼檢索等。
</p>
<h4>字典樹的實現和檢查</h4>
<p>實現一個字典樹上 程式如下。</p>
<pre><code class="language-js">
class PrefixTreeNode{
constructor(value){
//儲存子節點
this.children = {}
this.isEnd = null
this.value = value
}
}
</code></pre>
<p>字典樹 PrefixTree 承繼 PrefixTreeNode 類別,程式如下。</p>
<pre><code class="language-js">
class prefixTree extends PrefixTreeNode {
constructor() {
super(null)
}
}
</code></pre>
<p>接著在 PrefixTree 繼承 PrefixTreeNode 類別的基礎上實現以下方法。</p>
<ul>
<li>addWord:建立一個字典樹節點。</li>
<li>predictWord:指定一個字串,傳回字典樹中以該字串開頭的所有單字。</li>
</ul>
<p>addWord 方法的實現程式如下。</p>
<pre><code class="language-js">
addWord(str) {
const addWordHelper = (node, str) => {
//目前node不含目前 str 開頭的目標
if (!node.children[str[0]]) {
// 以目前 str 開頭的第一個字母建立一個 PrefixTreeNode實例
node.children[str[0]] = new PrefixTreeNode(str[0])
if (str.length === 1) {
node.children[str[0]].isEnd = true
} else if (str.length > 1) {
addWordHelper(node.children[str[0]], str.slice(1))
}
}
}
addWordHelper(this, str)
}
</code></pre>
<p>predictWord 方法的實現程式如下。</p>
<pre><code class="language-js">
predictWord(str) {
let getRemainingTree = function(str, tree){
let node = tree
while (str) {
node = node.children[str[0]]
str = str.substr(1)
}
return node
}
// 該陣列維護所有以 str 開頭的單字
let allWords = []
let allWordsHelper = function(stringSoFar, tree){
for (let k in tree.children) {
const child = tree.children[k]
let newString = stringSoFar + child.value
if (child.endWord) {
allWords.push(newString)
}
allWordsHelper(newString, child)
}
}
let remainingTree = getRemainingTree(str, this)
if (remainingTree) {
allWordsHelper(str, remainingTree)
}
return allWords
}
</code></pre>
<h3>圖</h3>
<p>
圖是由具有邊的節點集合組成的資料結構,圖可以是定向的,也可以是不定向的。因此,圖可以分為好多種類,主要是根據場景來進行分類,如下所示。
</p>
<ul>
<li>LBS ( Location Based Services),以位置為基礎的服務及GPS 系統。</li>
<li>社交媒體網站的使用者關係圖。</li>
<li>前端專案化中的開發依賴圖。</li>
<li>搜尋演算法使用圖,用於確保搜尋結果的相關性。</li>
</ul>
<p>
圖也是應用最廣泛的資料結構之一,真實場景中處處都有圖的應用。需要了解圖的幾種基本元素，如下。
</p>
<ul>
<li>Node: 節點</li>
<li>Edge: 邊</li>
<li>[V]: 圖中頂點(節點)的總數</li>
<li>[E]: 圖中的連接總數(邊)</li>
</ul>
<h4>圖的實現和檢查</h4>
<p>這裡主要實現一個有方向圖 Graph 類別,程式如下。</p>
<pre><code class="language-js">
class Graph {
constructor() {
this.AdjList = new Map()
}
}
</code></pre>
<p>
圖的建構方法還需要表明圖中各個頂點之間的關係,使用 Map 資料結構來實現對這種關係的維護。
</p>
<p>接下來,需要實現以下方法。</p>
<ul>
<li>增加頂點: addVertex</li>
<li>增加邊: addEdge</li>
<li>列印圖: print</li>
<li>廣度優先演算法(BFS)</li>
<li>深度優先演算法(DFS)</li>
</ul>
<p>addVertex 方法的程式如下。</p>
<pre><code class="language-js">
addVertex(vertex) {
if (!this.AdjList.has(vertex)){
this.AdjList.set(vertex, [])
} else {
throw 'vertex already exist!'
}
}
</code></pre>
<p>建立頂點的程式如下</p>
<pre><code class="language-js">
let graph = new Graph();
graph.addVertex('A')
graph.addVertex('B')
graph.addVertex('C')
graph.addVertex('D')
</code></pre>
<p>其中,A、B、C、D 頂點都對應一個陣列,如下。</p>
<pre><code class="language-js">
'A' => [],
'B' => [],
'C' => [],
'D' => [],
</code></pre>
<p>該陣列將用來儲存邊。舉例來說,透過以下描述,就可以把一個圖表現出來。</p>
<pre><code class="language-js">
Map {
'A' => ['B', 'C', 'D'],
'B' => [],
'C' => ['B'],
'D' => ['C']
}
</code></pre>
<p>
如何獲得上述程式表述的關係呢?首先要實現 addEdge方法,該方法需要兩個參數:一個是頂點
vertex,另一個是連線物件 node,實際程式如下。
</p>
<pre><code class="language-js">
addEdge (vertex, node) {
if (this.AdjList.has(vertex)) {
if (this.AdjList.has(node)){
let arr = this.AdjList.get(vertex)
if(!arr.includes (node) ) {
arr.push (node)
}
} else {
throw `Can't add non-existing vertex ->'${node}'`
}
} else {
throw 'You should add '${vertex}' first`
}
}
</code></pre>
<p>釐清資料關係,就可以 Print 圖了,這裡只用到一個很簡單的 for...of 迴圈。</p>
<pre><code class="language-js">
print() {
for (let [key, value] of this.AdjList) {
console.log(key, value)
}
}
</code></pre>
<p>剩下要做的就是檢查圖。</p>
<p>
廣度優先演算法(BFS)是一種利用佇列實現的搜尋演算法。對圖來說,其搜尋過程和「向湖丟進一塊石頭激起層層漣漪」類似。換成演算語言,就是從起點出發,對於每次出佇列的點都要檢查其四周的點。因此,BFS
實現步驟如下。
</p>
<ul>
<li>以起始節點作為開頭初始化一個空白物件: visited</li>
<li>初始化一個空陣列,該陣列將模擬一個佇列。</li>
<li>將起始節點標記為已存取。</li>
<li>將起始節點放入佇列中。</li>
<li>循環檢查直到佇列為空。</li>
</ul>
<p>遵循以上步驟實現 BFS 的程式如下。</p>
<pre><code class="language-js">
createVisitedObject(){
let map = []
for(let key of this.AdjList.keys()){
arr[key] = false
}
return map
}
bfs(initialNode) {
// 建立一個已存取節點的 map
let visited = this.createVisitedObject()
// 模擬一個佇列
let queue = []
// 第一個節點已存取
visited[initialNode] = true
// 第一個節點入佇列
queue.push(initialNode)
while(queue.length) {
let current = queue.shift()
console.log(current)
// 獲得該節點的其他節點關係
let arr = this.AdjList.get(current)
for (let elem of arr) {
// 如果目前節點沒有存取過
if (!visited[elem]) {
visited[elem] = true
queue.push(elem)
}
}
}
}
</code></pre>
<p>
對於深度優先搜尋演算法(DFS),可以將它的特點歸納為「不撞南牆不回頭」，從起點出發,先把一個方向的點都檢查完才會改變方向。換成演算語言就是,DFS是利用遞迴實現的搜尋演算法。
</p>
<p>在實現 DFS 時要作為起建立存取物件,同時呼叫輔助函數從起始節點開始遞迴,實現程式如下。</p>
<pre><code class="language-js">
createVisitedObject() {
let map = {}
for (let key of this.AdjList.keys()) {
arr[key] = false
}
return map
}
dfs(initialNode) {
let visited = this.createVisitedObject()
this.dfsHelper(initialNode, visited)
}
dfsHelper(node, visited) {
visited[node] = true
console.log(node)
let arr = this.AdjList.get(node)
for (let elem of arr) {
if (!visited[elem]) {
this.dfsHelper(elem, visited)
}
}
}
</code></pre>
<p>BFS 的重點在於檢查佇列,而 DFS 的重點在於遞迴,這是它們之間的本質別。</p>
<h4>圖在前端中的應用</h4>
<p>
圖其實在前端中的應用不算特別多,但絕對是不容忽視的一部分。這裡舉一個在現實中應用的實例：循環圖表。
</p>
<p>
專案化發展的今天,釐清專案中的依賴關係有助開發者在巨觀上把控專案化專案。在專案中,借助
mermaidj 畫圖工具實現了專案依賴視覺化,並借助 npm script 來產生圖片結果，相關 script
指令稿執行方程式如下。
</p>
<pre><code class="language-bash">
yarn graph
</code></pre>
<p>graph 指令稿的實現如下。</p>
<pre><code class="language-js">
import glob from 'glob'
import readJSON from 'xxx/utils/readJSON'
const pkgs = glob.sync('packages/\*/package.json').map(readJSON)
const deps = {}
for (const pkg of pkgs) {
deps[pkg.name] =Object.keys(pkg.dependencies || []).filter(
dep=> //...
)
}
const graph = { code: '', mermaid: { theme: 'default'}}
graph.code += 'graph TD;'
for (const name in deps) {
for (const dep of deps[name]) {
graph.code += `${name}-->${dep};`
}
}
const base64 = Buffer.from(JSON.stringify(graph)).toString('base64')
/* eslint-disable-next-line */
console.log(
`Open in browser: https://mermaidjs.github.io/mermaid-live-editor/#/
edit/${base64}`
)
</code></pre>
<p>
上述程式首先取得到packages/*/package.json中宣告的所有依賴,對依賴進行必要過濾之後,將其儲存到deps物件中,按照mermaid
需求將 monorepo 專案中的每一個子專案名稱和依賴為間隔儲存到 graph.code中最後將 graph
變數產生為 base64 類類型資料,並交給 mermaid
進行繪圖,繪圖過程中會根據約定(-->的標記)產生視覺化的依賴圖。
</p>
<p>
在專案中,這個依賴圖對專案的部署建置有非常重要的作 ,在對 monorepo
專案進行建置時,因為子專案過多會導致建置時間過長。為此,方案定為增量建置,如果這次改動只設計專案
A、專案 B、公共依賴 C,那麼專案 C、專案
D等其他專案在建置時只需要讀取快取建置結果即可。建置的想法很簡單,但是有一個直接的問題是,如作檢測出真正需要建置的專案呢?
</p>
<p>
舉個實例,專案 A 依賴公共依賴 C,那麼及時透過 git hook 拿到的 diff 表明專案 A
中沒有程式變動,但是可能因 C 變了而需要重新建置專A (因A依賴C)