.Net 4.0의 이진 검색 트리
Abdullahi Salawudeen
2024년2월16일
이 기사에서는 .Net 4.0에서 이진 검색 트리 또는 BST의 구현을 소개합니다.
SortedSet<T> 클래스를 사용하여 .Net 4.0에서 이진 검색 트리 구현
일반적으로 정렬 또는 정렬된 이진 트리라고 하는 이진 검색 트리(BST)는 루트 이진 트리 데이터 구조입니다. 각 내부 노드는 왼쪽 하위 트리의 키보다 크고 오른쪽 하위 트리의 키보다 작은 키를 저장합니다.
이진 검색 트리 작업의 시간 복잡도는 트리 높이에 정비례합니다. 검색, 삽입 및 삭제 작업에 대한 평균 복잡도 분석은 n 노드에 대해 O(log N)을 사용하는 반면 최악의 경우 작업은 O(n)을 사용합니다.
이 이진 검색 트리 참조를 통해 추가 논의가 가능합니다.
SortedSet 클래스는 .net 프레임워크, .netcore, UWP 및 Xamarin에서 이진 검색 트리를 구현합니다. System.Collections.Generic 네임스페이스에 포함되어 있습니다.
구현에 대한 추가 논의는 이 참조를 통해 확인할 수 있습니다.
자체 균형 레드-블랙 트리는 요소를 정렬된 순서로 유지하고 특정 범위에 있는 요소의 하위 집합을 가져오거나 집합의 Min 또는 Max 요소를 가져오는 데 사용됩니다.
SortedSet 클래스에 대한 완전한 코드 구현은 이 참조를 통해 찾을 수 있습니다.
아래는 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까지의 짝수 집합이 주어지면 처음 10개의 짝수에만 관심이 있습니다. 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 클래스 아래의 다른 클래스는 이 참조를 통해 사용할 수 있습니다.
