.Net 4.0 中的二叉搜尋樹
Abdullahi Salawudeen
2023年10月12日
本文將介紹二叉搜尋樹或 BST 在 .Net 4.0 中的實現。
使用 SortedSet<T> 類在 .Net 4.0 中實現二叉搜尋樹
二叉搜尋樹 (BST)，通常稱為有序或排序二叉樹，是一種有根二叉樹資料結構。每個內部節點都儲存一個大於左子樹中的鍵且小於其右子樹中的鍵的鍵。
二叉搜尋樹上操作的時間複雜度與樹的高度成正比。對於 n 個節點，搜尋、插入和刪除操作的平均複雜度分析需要 O(log N)，而最壞情況的操作需要 O(n)。
可通過此二叉搜尋樹介紹進行進一步討論。
SortedSet 類在 .net 框架、.netcore、UWP 和 Xamarin 中實現二叉搜尋樹。它包含在 System.Collections.Generic 名稱空間中。
可通過本參考文獻獲得有關實施的進一步討論。
自平衡紅黑樹 用於保持元素排序並獲取特定範圍內元素的元素子集或獲取集合的 Min 或 Max 元素。
SortedSet 類的完整程式碼實現可以通過 this reference 找到。
下面是 SortedSet 類的派生類的程式碼片段。
public class SortedSet<T> : System.Collections.Generic.ICollection<T>,
System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IReadOnlyCollection<T>,
System.Collections.Generic.IReadOnlySet<T>, System.Collections.Generic.ISet<T>,
System.Collections.ICollection, System.Runtime.Serialization.IDeserializationCallback,
System.Runtime.Serialization.ISerializable
使用 SortedSet 類建立一組有序集合
我們使用 new 關鍵字來建立排序陣列的例項。無論元素如何新增到陣列中，結果集總是返回一組有序陣列而不重複任何元素。
下面是一個程式碼示例。
// C# program to illustrate the
// use of SortedSet class to create
// a sorted set of elements
using System;
using System.Collections.Generic;
public class Example {
public static void Main() {
var elements = new SortedSet<int>() { 5, 9, 2, 11, 2, 1, 4, 1, 2 };
foreach (int element in elements) {
Console.Write(string.Format(" {0}", element));
}
}
}
// The example displays the following output:
// 1 2 4 5 9 11
輸出：
1 2 4 5 9 11
請注意，所有元素都按排序順序排列，沒有重複 1 和 2。
將元素新增到排序集合
可以將元素新增到排序陣列中，並且返回的元素集始終是排序的。
下面是一個程式碼示例。
using System;
using System.Collections.Generic;
public
class Example {
public
static void Main() {
var elements = new SortedSet<int>(){5, 9, 2, 11, 2, 1, 4, 1, 2};
Console.WriteLine("Sorted Set of Elements before Adding new Elements");
foreach (int element in elements) {
Console.Write(string.Format(" {0}", element));
}
Console.WriteLine();
elements.Add(3);
elements.Add(100);
elements.Add(10);
elements.Add(67);
Console.WriteLine("Sorted Set of Elements after Adding new Elements");
foreach (int element in elements)
Console.Write(string.Format(" {0}", element));
}
}
// Sorted Set of Elements before Adding new Elements
// 1 2 4 5 9 11
// Sorted Set of Elements after Adding new Elements
// 1 2 3 4 5 9 10 11 67 100
輸出：
Sorted Set of Elements before Adding new Elements
1 2 4 5 9 11
Sorted Set of Elements after Adding new Elements
1 2 3 4 5 9 10 11 67 100
請注意，將不同的數字新增到排序集中後，最終結果仍然是排序順序。
使用 GetViewBetween 獲取有序集合中的一系列元素
GetViewBetween 返回 SortedSet 中子集的檢視。它需要兩 (2) 個引數。
然後，下限值和上限值返回僅包含指定範圍值的子集檢視。這在從更多元素中獲取一系列值時很有用。
例如，給定一組從 1 到 1000 的偶數，我們只對前十個偶數感興趣。GetViewBetween 類可用於檢索此類元素。
進一步的討論可通過本參考文獻獲得。
下面是一個程式碼示例。
using System;
using System.Collections.Generic;
public
class Example {
public
static void Main() {
var elements = new SortedSet<int>(){};
int counter = 0;
while (counter <= 1000) {
if (counter % 2 == 0) {
elements.Add(counter);
}
counter++;
}
Console.WriteLine("Even numbers between 1 and 1000");
foreach (int element in elements) {
Console.Write(string.Format(" {0}", element));
}
Console.WriteLine();
// foreach (int element in elements) {
// Console.Write(string.Format(" {0}", element)); }
var subSet = elements.GetViewBetween(1, 100);
Console.WriteLine();
Console.WriteLine("Even numbers between 1 and 100");
foreach (int element in subSet)
Console.Write(string.Format(" {0}", element));
Console.WriteLine();
var newSubSet = elements.GetViewBetween(1, 10);
Console.WriteLine();
Console.WriteLine("Even numbers between 1 and 10");
foreach (int element in newSubSet)
Console.Write(string.Format(" {0}", element));
}
}
輸出：
Even numbers between 1 and 1000
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 202 204 206 208 210 212 214 216 218 220 222 224 226 228 230 232 234 236 238 240 242 244 246 248 250 252 254 256 258 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 320 322 324 326 328 330 332 334 336 338 340 342 344 346 348 350 352 354 356 358 360 362 364 366 368 370 372 374 376 378 380 382 384 386 388 390 392 394 396 398 400 402 404 406 408 410 412 414 416 418 420 422 424 426 428 430 432 434 436 438 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 500 502 504 506 508 510 512 514 516 518 520 522 524 526 528 530 532 534 536 538 540 542 544 546 548 550 552 554 556 558 560 562 564 566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610 612 614 616 618 620 622 624 626 628 630 632 634 636 638 640 642 644 646 648 650 652 654 656 658 660 662 664 666 668 670 672 674 676 678 680 682 684 686 688 690 692 694 696 698 700 702 704 706 708 710 712 714 716 718 720 722 724 726 728 730 732 734 736 738 740 742 744 746 748 750 752 754 756 758 760 762 764 766 768 770 772 774 776 778 780 782 784 786 788 790 792 794 796 798 800 802 804 806 808 810 812 814 816 818 820 822 824 826 828 830 832 834 836 838 840 842 844 846 848 850 852 854 856 858 860 862 864 866 868 870 872 874 876 878 880 882 884 886 888 890 892 894 896 898 900 902 904 906 908 910 912 914 916 918 920 922 924 926 928 930 932 934 936 938 940 942 944 946 948 950 952 954 956 958 960 962 964 966 968 970 972 974 976 978 980 982 984 986 988 990 992 994 996 998 1000
Even numbers between 1 and 100
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100
Even numbers between 1 and 10
2 4 6 8 10
請注意，無論返回的元素大小如何，最終結果仍然是排序的。
GetViewBetween 的子集結果不允許新增超出指定範圍的元素。
例子：
newSubSet.Add(11);
// this would throw ArgumentOutOfRangeException exception.
newSubSet.Add(1);
// this would add 1 to the set of elements since 1 is between the range of 1 and 10.
使用 RemoveWhere 類從排序集合中刪除元素
如前所述，SortedSet 類表示按排序順序的物件集合。此類屬於 System.Collections.Generic 名稱空間。
謂詞 (P => P % 2 == 0) 甚至從給定整數 SortedSet<T> 中刪除元素。RemoveWhere 方法返回從給定 SortedSet<T> 中刪除的元素總數。
下面是一個程式碼示例。
using System;
using System.Collections.Generic;
public class Example {
public static void Main() {
var elements = new SortedSet<int>() {};
int counter = 1;
while (counter <= 100) {
elements.Add(counter);
counter++;
}
Console.WriteLine("Numbers between 1 and 100");
foreach (int element in elements) {
Console.Write(string.Format(" {0}", element));
}
Console.WriteLine();
Console.WriteLine();
Console.WriteLine("After removing Even numbers between 1 and 100");
elements.RemoveWhere(P => P % 2 == 0);
foreach (int element in elements) {
Console.Write(string.Format(" {0}", element));
}
}
}
輸出：
Numbers between 1 and 100
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
After removing Even numbers between 1 and 100
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
SortedSet 類下的其他類可通過此參考獲得。
