혼잣말처럼 넘기는 자료구조 (파트4)

[이미지 출처: Data Structures Explained]
목차
파트 1	기본 용어 및 개념 > 추상화, 성능 등등.  배열  스택  큐
파트 2	연결 리스트 > 기본 개념 > 단순 연결 리스트 > 단순 원형 연결 리스트 > 이중 연결 리스트  이진 트리 > 기본 개념 > 형태 > 연산
파트 3	그래프 > 기본 개념 > 기술하기 > 탐색 > 최소 신장 트리: 프림, 크루스컬, 솔린  힙 > 기본 개념 > 형태 > 연산
파트 4	선택 트리 > 승자 트리, 패자 트리  숲  BS 트리 > 탐색, 삽입, 삭제  BS변형 > Splay, AVL, BB  멀티웨이 탐색 트리 ① > m원, B, B*, B+  멀티웨이 탐색 트리 ② > 2-3 트리, 2-3-4 트리, 레드 블랙 트리  마치며.

 

* 일반적인 강의형 포스팅이라기보다는 개인적인 노트정리여서 보조 설명이나 자체적인 언어(?)로 해석/재구성한 부분은 밑줄을 포함한 이탤릭체 혹은 기울임꼴로 표기됩니다.

* 참조 서적중 초판이 1994년 이고 2020년 이후에도 개정판이 나온거 같은데 그걸로 봐도 되지 않을까 싶지만 제가 가지고 있던건 구판이다보니 이걸 기준으로

* 자체적으로 만들어둔 예제 코드는 C++(11)과 JAVA기준이며 C++의 경우 C++11과 C++14에서 구동 테스트 마친 코드입니다.

 

 

 

 

 

1. 선택 트리(Selection tree)

 

-> 정렬된 N개의 리스트를 하나로 '합병 정렬'하는데 쓰이는 완전 이진 트리 기반인 특수한 트리로 2가지 종류가 있다. (승자 트리, 패자 트리)

-> k개의 리스트(혹은 배열)로 선택트리를 만들어서 n개의 데이터 병합에 걸리는 계산 복잡도는 O(n logk)이다.

-> /* KOCW 2008~2023년 자료구조 강좌 목차상 선택 트리가 독립적으로 존재하는건 딱 2개군요. [#2015, 영남대학교 조행래 교수][#2010, 한림대학교 송찬근 교수]

 또한 플로리다 대학(공립대)나 다른 영문권 자료는 승자/패자 트리의 상위 분류를 토너먼트 트리(Tournament Tree)로 쓰고 있습니다. 이리 되면... 선택 트리가 아니라 토너먼트 트리 아닐지;;; */

 

1) 합병 in 승자 트리(Winner Tree)

-> 예시는 같은 레벨의 자식노드중 작은값이 상위 레벨로 올라간다.

-> /* 다른 참조 자료는 최상위 노드에 가는것이 큰값 우선이면 Max/Maximum Winner tree라 하고 작은값 우선이면 Min/Minimum Winner tree로 설명이 나오는데 서울대랑 플로리다대는 Max/Min Winner tree쪽으로 표기를 쓰네요. 일단 학교쪽 자료를 표준으로 보는걸로;;; */

[그림: 승자트리 구성전, 출처: geeksforgeeks]	[그림:승자트리 구성, 출처: geeksforgeeks]
-> 완전 이진 트리를 맞춰야. 2^(1) < 3개의 배열 <= 2^2 로 레벨이 2(혹은 깊이가 3)인 잎 노드에 준비.	-> arr[0]으로 토너먼트 시작. 배치된 배열이 없은 해당 잎 노드는 Integer.MAX등으로 막아버림. ->재구성: 예시의 2번 배열 {1, 3, 4}의 원소가 상위 노드로 올라가면서 잎 노드는 빈자리니 나머지 배열 원소가 새로 들어간다. -> (루트에 도착한 값은 정렬 결과에 차례대로)토너먼트와 배열에 준비된 값의 입력을 계속하다 값이 더이상 없으면 종료.

 

 

2) 합병 in 패자 트리(Loser Tree)

-> 승자 트리랑 거의 비슷하나 부모가 없는 루트 노드에 부모 노드를 하나 연결한다.

[그림: 패자트리 구성전, 출처: tutorialspoint]	[그림:패자트리 구성, 출처: tutorialspoint]
->최하위 레벨에서 루트까지 경합을 거쳐 하나의 값(예시는 작은값)이 올라가는 단계까지는 동일.	-> (기존 이진 트리)루트 노드위에 최상위 0번 노드를 하나 올려서 루트에 있던 값을 옮기고, 후속으로 루트 노드에도 값 채움.//패자트리 구조! -> 루트와 최상위 0번을 결승전. 지는쪽이 루트에.//패자트리는 루트가 준우승자. -> 최상위 0번을 비우고, 루트의 값을 올리고 루트에 새로운 값을 넣고 경합//지난 경합의 준우승은 결승 시드권 부여?

 

 

 

 

 

2. 숲

-> "트리에 대한 이론을 수학적으로 쉽게 다루기 위해 공집합도 트리로 인정합니다. ...(중략)... 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있습니다. 반대로 숲을 연결하면 트리를 만들 수도 있습니다."   (p.225, 자료구조, 2023)

빈 숲	총 노드 개수가 0인 이진 트리
홀로 숲	총 노드 개수가 2~3개인 이진트리
숲	-> 숲을 이진 트리화 하려면? 루트(노드)가 왼쪽 서브트리만 가지고 있도록 하면 간단해짐.

 

* 이진 트리에 대한 경우의 수

-> n개의 노드를 가진 이진 트리는 (2n)! / (n! * (n+1)!) 종류로 계산된다.

(수학자 카탈랑의 증명 기반)

-> 예시. 3개의 노드를 가진 이진 트리들

[출처: 취미로 공부하기]

(2*3)! / (3! * (3+1)!)

= (6*5*4*3*...)! / ((3*2*1)*(4*3*...))

= (6*5*4*3*...)! / ((3*2*1)*(4*3*...))

= 5개의 이진트리가 존재

 

 

 

 

 

3. 이진 탐색 트리(Binary Search Tree, BS 트리)

1) 개념

-> "원리상 동적인 자료 집합에 대해서 매율 효율적인 검색 방법어서 이진 나무 검색을 위한 자료 집합에서 자료를 하나 삭제하거나 삽입할 경우 순차 검색이나 이분 검색처럼 평균적으로 N/2개의 자료를 밀고 당기는 작업이 필요없고 단순한 포인터의 조작으로 자료를 삽입·삭제 할 수 있다. ...(중략)... 구성에는 어떤 원칙이 있다. 그것은 부모보다 작은 값은 부모의 왼쪽 자식으로 부모보다 큰 값은 부모의 오른쪽 자식으로 둔다는 것이다." (p.475, C로 배우는 알고리즘, 1994)

-> /* 부모가 자식보다 크거나 작기 때문에 같은 값만 아니면, 새 노드는 항상 잎 노드가 될수밖에. 노드 추가시 중복값 불허 */

 

 

2) 연산

-> [#David Galles 교수의 시각자료, Binary Search Tree]

2-1) 탐색 [함수 doBST(노드)]

if(노드==null){ return 탐색불가; }   if(노드.data==찾는값){ 탐색성공; } else if(노드.data>찾는값){ doBST(현노드.left); } else if(노드.data<찾는값){ doBST(현노드.right); }

 

2-2) 삽입 [함수 insertBST(노드값)] -> 중복값 불허

2-3) 삭제 [함수 deleteBST(노드값)] -> 삭제 대상인 노드의 왼쪽 서브 트리중 가장 큰값이나 오른쪽 서브트리의 가장 작은값을 찾아서 공백을 메꿔야 -> 삭제되는 노드 레벨을 N이라 가정

신규노드.data = 노드값 ptr = root;   while(ptr!=null) 루프문 시작 if(ptr.data==노드값){ return; } if(ptr.data>노드값){   if(ptr.left==null){ ptr.left=신규노드; }    else { ptr=ptr.left; } } else{//CASE. ptr.data<노드값    if(ptr.right==null){ ptr.right=신규노드; }    else { ptr=ptr.right; } } while(ptr!=null) 루프문 종료

if(자식이 0개){    if(N-1레벨 부모 없음){ root=null; }    else {       (부모.left==target)?부모.left=null : 부모.right=null; }} else if(자식이 1개){    (target.left!=null)?child=target.left:target.right;    if(N-1레벨 부모 없음){ root = child; }    else{       (parent.left==target)?parent.left=child:parent.right=child; }} else if(자식이 2개){    prevLevelNode = target;    ptr = target.left;//시작 노드의 왼쪽 서브 트리    while(ptr.right!=null) 루프 시작       prevLevelNode = ptr;       ptr = ptr.right;    while(ptr.right!=null) 루프 종료    if(ptr==target.left) { prevLevelNode.left = ptr.left; }    else{ prevLevelNode.right = ptr.left; }    target.data = ptr.data;    //ptr = null; }

 

 

4. BS변형

 

ⓐ 자주 탐색하는 키를 루트 가까이에 [Splay트리]

ⓑ 각 노드의 왼쪽/오른쪽 서브트리가 가급적 같은 수, 균형(balance)이 유지된 트리가 되도록. [AVL트리, BB트리]

-> "휴리스틱(heuristic) 알고리즘을 사용하여 구축한 BS트리의 성능이 최적의 BS트리에 버금간다는 것이 많은 연구 결과로 밝혀졌습니다." (p.244, 자료구조, 2023)

 

 

1) Splay트리

1-1) 개념

-> Splay연산을 통해 자주 탐색하는 키를 아예 루트에 올때까지 반복.

-> /* 해당 최적화를 거치고 나면 노드의 배치가 거의 다 들어엎는편. */

 

1-2) 연산

-> [#David Galles 교수의 시각자료, Splay Tree]

 

 

2) AVL 트리

2-1) 개념

-> 완전하게 균형 잡힌 배치에 가깝지만,

(연산비용도 적지 않으니) 절충안으로 왼쪽/오른쪽 서브트리의 높이를 엇비슷하게 맞추되,

절대값(노드의 왼쪽 서브트리 높이-오른쪽 서브트리 높이)= 최대 1이다.

이리 처리되면 '높이 균형 트리'(height-balanced tree)라 표현한다.
-> 삽입&삭제후 트리의 균형을 잡으려면 O(N)개의 노드 이동 필요.

2-2) 연산

-> [#David Galles 교수의 시각자료, AVL Tree] 


3) BB트리(Bound-Balanced tree)

3-1) 개념

-> 완전하게 균형 잡힌 배치에 가깝지만,

(연산비용도 적지 않으니) 절충안으로 왼쪽/오른쪽 서브트리의 무게(잎 노드의 개수)를 엇비슷하게 맞추되, √2-1 < 무게(왼쪽 서브트리) / 무게(오른쪽 서브트리) < √2+1로 무게 비율이 0.5에 가까울수록 이상적이며 이리 처리되면 '무게 균형 트리'(weight-balanced tree)라 표현한다.

(참고. √2 ≈ 1.4142...)

-> 삽입&삭제후 트리의 균형을 잡으려면 O(log2(N))개의 노드 이동 필요.

 

 

 

 

 

5. 멀티웨이 탐색 트리 ①

 

* 참고 서적으로는 이해가 안 되는 예외상황들이 적지 않아 다른 파트에 비해 웹 공개강좌 자료 인용 비율이 높습니다.

 

1) m원 탐색 트리(MST. m-way Search Tree)

public class MwaySearchNode

{// mValue의 값은 m-way의 숫자값에 따라 유동적

    int currentDataCountInNode;

    int[] dataArr = new int[mValue-1];

    MwaySearchNode[] child = new MwaySearchNode[mValue];

}

-> "트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리를 m원 탐색 트리라고 합니다. (BS 트리가 2-way 탐색 트리구나라고 생각했다면 훌륭합니다.) ...(중략)...

 이진 탐색 트리를 확장한 것입니다. 즉, 탐색 트리의 제한을 따르되 두 개 이상(m개 이하) 자식을 가질 수 있는 것입니다."  (p.255, 자료구조, 2023)

-> "Multi-way search trees are a generalized version of binary trees that allow for efficient data searching and sorting. In contrast to binary search trees, which can only have two children per node, multi-way search trees can have multiple children per node."  (Rahmat Ullah Orakzai, 2023)

-> /* 일반적으로(?) 2/3/4원 트리를 많이 쓴다고 하며 m-way에서 최대 m개의 자식노드(=최대 차수가 5)에 최대 m-1개의 자료값(키값, elements 등)이 구성. 서브트리의 균형에 제한X

예. 5-way에서 노드마다 자식[5]까지 가능하고 자료값[4]까지 가능하다. */

-> /* 전체 노드 N개인 m원 탐색 트리의 높이(0-base)를 계산하면

log m(N) 로 형태상 2-way같은 이진 트리에도 적용은 가능한 공식 */

 

 

2) B 트리(혹은 차수 m인 B-tree)

2-1) 개념

ⓐ 루트는 최소 2개의 서브트리(혹은 자식 노드)

ⓑ 모든 잎 노드는 같은 레벨에

ⓒ (트리내 나머지 노드)내부 노드는 최소 m/2개, 최대m개 서브트리

-> "Invented by Bayer and McCreight in 1972A B-tree is a Balanced M-way search tree"  (Sugih Jamin, 2011)

-> "One of the main reason of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small."  (javatpoint, "B Tree")

-> m원 탐색 트리가 균형이 유지되면, 트리의 높이가 불필요하게 늘어나지 않아 경로 길이 최적화가 가능하다.

-> /* javatpoint.com 자료상,

B-트리와 이진트리의 차이점으로 전자는 디스크에 데이터 저장시 쓰이고, 후자는 데이터가 RAM에 저장될때 쓰인다를 두고 있네요. 참고로 이진트리쪽이 데이터 입력등이 수월하고 허프만 코딩에도 활용됩니다. */

 

2-2)연산

-> [#David Galles 교수의 시각자료, B-Trees]

-> 해당 시작자료는 3/4/5/6/7-way로 시뮬레이션이 가능합니다.

2-2-1) 삽입

ⓐ 루트에서 삽입가능한 잎노드까지 대소관계 비교하며 탐색

ⓑ (노드의 키 값 개수 < m-1개)? 삽입 및 연산종료 : ⓒ로 이동

ⓒ (키 값이 m-1개인 잎노드)노드에 새 키값을 정렬해서 넣음.

ⓓ 키 값이 m개가 된 노드내 중간값을 확인해둔다.

ⓔ 확인된 중간값 기준으로 노드 조각1(왼쪽)과 노드 조각2(오른쪽)으로 분할한다. (당연히 부모는 동일하게 유지.)

ⓕ 중간값을 부모노드에 보내고, (부모노드 키 값 m개==true)? 해당 노드에서 ⓓ부터 : 연산 종료

-> /* 참조 자료들을 비교해보니

ⓒ단계에서 분할후 키값 추가: 참고서적(방송대), geeksforgeeks

ⓒ단계에서 키값 추가후 분할: javatpoint, programiz

로 갈라지는데 몇가지 추가 처리에 대한 설명때문에 javatpoint 기준으로 진행합니다. */

2-2-2) 삭제

ⓐ (삭제할 키 값이 잎노드에 존재==true)? ⓑ : ⓒ

ⓑ 해당 잎노드에서 키값을 삭제후, 필요시 부모나 형제 노드를 재배열.(B 트리 조건에 맞게)

ⓒ 보통은 왼쪽 서브트리에서 가장 큰값이나 오른쪽 서브 트리에서 가장 작은값을 삭제하는 키값이 있던 자리로 옮긴다. 이때 잎 노드에 키값의 개수가 맞지 않으면 재배열.(B 트리 조건에 맞게)

-> 삭제시의 예시코드 [#geeksforgeeks]

 

 

3) B* 트리(B star Tree)

3-1) 개념

ⓐ 전체 노드가 0개이거나 높이가 1이상인 m-원 탐색 트리

ⓑ 루트의 자식은 2개이상, 2⌊ (2m-2)/3⌋+1이하 //2 * (int)((2m-2)/3) + 1

ⓒ 내부 노드는 최소 ⌈(2m-1)/3⌉개                  //올림함수. 소수점 올림

ⓓ 모든 잎 노드는 동일한 레벨 //B 트리 기반이라

ⓔ 포인터가 k개인 잎노드가 아니면 k-1개의 키

-> /* geeksforgeeks에서는 B* 트리에 대해서 ⓑ, ⓒ, ⓓ만 정의해둔걸 봐서는 적어도 3가지 항목이 가장 중요한것으로 봐야? */

-> "These techniques help to reduce the number of disk accesses required to search for and insert data into the tree, making B*-trees faster and more efficient than B-trees."

(tutorialspoint, "B*-Trees: An Optimized Data Structure for Fast Data Retrieval in C++")

-> "The advantage of using B* trees over B-trees is a unique feature called the ‘two-to-three’ split. By this, the minimum number of keys in each node is not half the maximum number, but two-thirds of it, making data far more compact. However, the disadvantage of this is a complex deletion operation. The difficulties in practically implementing a B-star algorithm contribute to why it’s not as regularly used as its B and B+ counterparts"

(geeksforgeeks, "B*-Trees implementation in C++")

-> /* B 트리 성능 개선했지만, 삭제 작업이 더 복잡해져 그리 많이 채택되지는 않는다로? */

 

 

4) B+ 트리(B Plus Tree)

4-1) 개념

-> "잎 노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다릅니다. 잎 노드는 자식이 없으므로 포인터가 NULL이지요. B+ 트리는 잎 노드의 마지막 포인터를 다음 키값을 갖는 노드를 카리킵니다."  (p.269, 자료구조, 2023)

-> 인덱스된 (디스크상의)순차 파일 구성에 사용. 잎의 마지막 포인터가 (같은 레벨에 있는)다음 노드를 가리키고 있어서 잎노드만 순서대로 연결된 리스트가 형성됨. DB등등 데이터 베이스 시스템에 많이 적용된다고.

 

 

4-2)연산

-> [#David Galles 교수의 시각자료, B+Trees]

-> 해당 시작자료는 3/4/5/6/7-way로 시뮬레이션이 가능합니다.

4-2-1) 삽입

[그림: 5-may에서 B+ 트리 삽입 예시 / 출처: javatpoint]

4-2-2) 삭제

[그림: B+ 트리 삭제 예시 / 출처: javatpoint]

 

 

 

 

6. 멀티웨이 탐색 트리 ②

 

1) 2-3 트리(2-3 Trees)

public class TwoThreeTreeNode
{//사실 자식 노드는 배열로 해도 되겠지만, 변수명을 통한 개념도를 위해.
   int lKey; //노드에 저장된 키값1
   int rKey; //노드에 저장된 키값2
   TwoThreeTreeNode lChild;
   TwoThreeTreeNode mChild;
   TwoThreeTreeNode rChild; //2-노드에서는 미사용.
}

-> B 트리 기반

-> 높이가 h이면 키 개수: log2(N)와 log3(N) 사이

-> 탐색/삽입/삭제시 시간복잡도: O(log N)

1-1) 개념

[그림. 2-3트리 / 출처: algorithmtutor.com]

ⓐ 내부 노드의 차수가 2 혹은 3이다.(2-노드의 키값=1개, 3-노드의 키값=2개)

ⓑ 2-노드={lchild, mchild}.

좌측/중간중 lchild(좌측 자식)가 이 노드의 키값이라 하면,

루트가 lchild인 모든 2-3 서브트리의 키값 < lkey

루트가 mchild인 모든 2-3 서브트리의 키값 > lkey

ⓒ 3-노드={lchild, mchild, rchild}.

좌측/중간/우측중 lkey, rkey를 이 노드의 키 값이라 하면,

lkey < rkey

루트가 lchild인 모든 2-3 서브 트리의 키값 < lkey

lkey < 루트가 mchild인 모든 2-3 서브트리 키값 < rkey

루트가 rchild인 모든 2-3 서브 트리의 키값 > rkey

ⓓ 모든 잎 노드는 같은 레벨에 

 

1-2) 연산

1-2-1) 탐색

-> 루트에서부터 타고 들어가되, 최대 2개 존재하는 노드의 키 값과 비교해가며 재귀함수의 주요 기능은 아래와 같다.

ⓐ 탐색값 < 노드.lKey이면, 노드.lChild로 이동

ⓑ 노드.lKey < 탐색값 < 노드.rKey이면, 노드.mChild로 이동

ⓒ 탐색값 > 노드.rKey이면, 노드.rChild로 이동

ⓓ 탐색값==노드.lKey or 탐색값==노드.rKey이면, 탐색 종료.

1-2-2) 삽입

-> 삽입후 노드 용량 확인 및 정렬은 B-트리 기반에 맞게 처리됨.

 

1-2-3) 삭제

-> "2-3 트리의 삭제는 삽입보다 매우 복잡합니다. 잎이 아닌 노드의 키를 삭제 하면 그곳을 적당한 다른 키로 대체해야 하기 때문입니다. 일반적으로 삭제한 키의 왼쪽 서브트리 안에서 가장 큰 값을 갖는 키나 오른쪽 서브트리 안에서 가장 작은 값을 갖는 키를 선택합니다."

(p.279, 자료구조, 2023)

 

2) 2-3-4 트리

2-1) 개념

[그림. 2-3-4트리 / 출처: algorithmtutor.com]

 

-> 2-3트리를 기반으로 4개의 자식을 가지는 4-노드를 허용하는 트리

/* 상속구조로 따지면 B-트리 클래스를 상속받은 자식의 자식 클래스 */

 

2-2) 연산

-> "2-3-4 트리는 2-3트리보다 삽입과 삭제가 용이합니다. ...(중략)... 2-3-4 트리에서는 2-노드와 3-노드에 대한 트리 재구성의 확률이 2-3 트리에서보다 작기 때문에 삽입 및 삭제 연산을 수행하는데 더 효율적인 것이다."   (p.282, 자료구조, 2023)

2-2-1) 삽입

-> 'C로 배우는 알고리즘' 기준

ⓐ 현재 노드가 잎 노드(혹은 외부 노드)가 아닐때,

if(현재 노드 is 4-노드) 분할

if(삽입 키<노드.key[0]) 노드.child[0]로 이동

else if(삽입 키<노드.key[1]) 노드.child[1]로 이동

else if(삽입 키<노드.key[2]) 노드.child[2]로 이동

else if(삽입 키>노드.key[2]) 노드.child[3]로 이동

ⓑ 잎 노드가 4-노드이면 분할.

ⓒ 잎 노드에 삽입 키.

2-2-2) 삭제

-> 'C로 배우는 알고리즘' 기준

ⓐ 현재 노드가 잎 노드가 아닐때,

if(현재 노드 != 4-노드 && 현재 노드 != 루트)

{ 4-노드로 변환, 형제에게 빌리거나 결합 }

if(현재 노드에 값이 존재==true) 잎 노드에서 삭제 키를 대체

else if(삽입 키<노드.key[0]) 노드.child[0]로 이동

else if(삽입 키<노드.key[1]) 노드.child[1]로 이동

else if(삽입 키<노드.key[2]) 노드.child[2]로 이동

else if(삽입 키>노드.key[2]) 노드.child[3]로 이동

ⓑ 잎 노드가 루트가 아니고 4-노드가 아니면 4-노드로 변환.

ⓒ 잎 노드에서 키 값 삭제.

 

 

3) 레드 블랙 트리(Red Black Tree)

-> 2-3-4 트리를 이진 탐색 트리화 시킨것을 레드 블랙 트리라 한다.//이진 탐색? 중복값X

-> 탐색/삽입/삭제시 시간복잡도: O(log N)

3-1) 개념

[그림. 레드 블랙 트리 / 출처: algorithmtutor.com]

ⓐ (레드 블랙)트리내 노드는 레드나 블랙이다.

ⓑ 하지만 루트 노드는 블랙.

ⓒ 노드가 키 값없이 null이면 블랙이며, 잎 노드도 키값이 없음.

ⓓ 레드의 부모와 자식은 모드 블랙. 2대 연속 레드는 불가능하고 블랙은 가능.

ⓔ 루트에서 잎 노드까지의 모든 경로들에는 블랙 갯수가 동일.

 

3-2) 연산

-> [#David Galles 교수의 시각자료, Red/Black Tree]

 

마치며.

 

 보통은 파트3 이하로 끝내던 포스팅이 이번에는 유례없이 파트4까지 진행됐습니다. 기왕 분량 늘어난거 좀 더 알차게 해본다고 해외권 자료랑 책자는 2개 참조하니깐 속도도 더 느려졌네요. 아무튼 해냈습니다.

 파트3에서도 변리사 선택과목 기출 문제로 '데이터구조'가 나오더니, 이번에는 선택 트리가 5급 공무원 시험 문제로도 나오네요. CS나 컴공 기초가 SW개발자 혹은 SW엔지니어의 전유물이라는 생각에 빠지지 않게 재환기 시켜줍니다.

 애초에 웹서핑만 해도 기초 이론이랑 공부할 오픈소스가 널린 환경이고 그런 세상이라 진입 장벽이 낮은 분야중 하나인데, 괜한 아집에 빠지게 되는건 글쎄올시다...

 약간의 부작용으로 기초중의 기초를 시작하면서 으스대는 사람을 보면 가자미눈 안 되게 표정관리에 최대한 용쓰게 되고

Q. 공개 포스팅을 하는 이유?

A. 국내/영문 자료를 교차 검증을 거쳐 문서화로 마무리하는 숙련도 유지겸 전공 기초를 공개 자료로 만들었습니다. 하지만 제 정리 자료가 AI학습에 사용되는건 동의하지 않습니다.

Q. 참고자료에 왜 하필 1994년 출판물을?

A. 예전에 구해둔 중고 서적이 이거여서 그냥 쓰고 있습니다. 당근 마켓이 나오기전이다보니

Q. 전문대 학위신가요?

A. 아니요. 방송대로 다시 공부한다고 하니 종종 들어오는 질문같네요.

 믿거나 말거나 컴퓨터 계열 학사 학위(4년제)도 있고 SW개발 재직 경력도 짧지는 않지만, 하는김에 그냥 방송대 컴퓨터과학 병행하고 있습니다.

 

Q. 이미 아는걸 왜 굳이?

A. 일종의 복습입니다. 최근까지 경력이 서버 파트다 보니 안 쓰면 기억에서 흐려지지더군요. 부수적으로 신뢰할 만한 자료를 얻을수 있는곳 목록 개정겸.

 참고로 '혼잣말처럼 넘기는-'라 제목이 붙은건 기존에 CS배경지식이 있는 사람이 빠르게 훑어보게 하는것에 목표를 두고 구성했습니다. 입문자 눈높이에 맞추는건 '입문 및 기초'처럼 입문 혹은 기초.

Q. 예제 코드를 굳이 2가지 언어로 한 이유?
A. JAVA 언어가 메인 업무이나, 서브 웨폰 혹은 보조 기술 숙련도를 위해 C++과 파이썬중 약간의 변덕을 부려 C++로 했습니다. 학부 때 C++이 가장 취약했던것도 작용했고.

 지금은 수도 코드 언급 위주로 예제를 작성했어도 시간이 되는선에서 수도 코드가 없던 부분도 추가 예정이나 장담은 못 합니다. 특히나 C++은 [#ciokorea, 백악관, 'C'와 'C++' 사용 중단 촉구··· 전문가들 "시의적절한 권고"]로 무려 백악관의 발표에 따라 언리얼을 위해 공부 시작한것이 장기적으로 필요성이 낮아졌습니다.

 그런고로 이후 예제 코드 갱신은 JAVA/파이썬/C# 위주가 되지 않을까 싶습니다.

기타. 참조자료

1) 서적

강태원, 정광식 저. 자료구조, 한국방송통신대학교출판문화원, 2023년.

이재규 저. C로 배우는 알고리즘, 세화, 1994년.

2) 웹페이지, 대학교 공개자료

Data Structures and Algorithms, 미국 미시간 대학교, 2011 가을학기 (by. Sugih Jamin) [#링크]

>Syllabus and Lecture Notes, Week 5 Multi-way trees (접속: 2024-03-05)

Data Structures and Algorithms, 미국 플로리다 대학교 (by. Sartaj Sahni) [#링크]

> Powerpoint Handouts, Lecture25, pdf2 (접속: 2024-02-28)

Data Structures, 한국 서울대학교, 2006 가을학기 [#링크]

> Tournament Trees (접속: 2024-02-28)

Data Structure Visualizations, 미국 샌프란시스코 대학교 (by. David Galles) [#링크]

> Algorithms (접속: 2024-03-08)

 

 

3) 웹페이지

algorithmtutor.com	> 2-3 Trees (접속: 2024-03-14) > 2-3-4 Trees (접속: 2024-03-14) > Red Black Trees (with implementation in C++, Java, and Python) (접속: 2024-03-14)
Baeldung on CS [#링크]	> What Are Multi-way Search Trees? (by. Rahmat Ullah Orakzai) (접속: 2024-03-05)(갱신: 2023-05-16)
geeksforgeeks.org	> 2-3 Trees | (Search, Insert and Deletion) (접속: 2024-03-14) > B*-Trees implementation in C++ (접속: 2024-03-07)(갱신: 2019-07-30) > Delete Operation in B-Tree (접속: 2024-03-07) > Insert Operation in B-Tree (접속: 2024-03-07) > Introduction to Red-Black Tree (접속: 2024-03-14) > m-WAY Search Trees | Set-1 ( Searching ) (접속: 2024-03-05) > Tournament Tree (Winner Tree) and Binary Heap (접속: 2024-02-28)
javatpoint	> Tournament Tree (Winner Tree) (접속: 2024-02-28) > B Tree (접속: 2024-03-07) > B tree vs B+ tree (접속: 2024-03-07) > B+ Tree (접속: 2024-03-07) > Binary Tree vs B Tree (접속: 2024-03-07)
tutorialspoint.com	> B*-Trees implementation in C++ (접속: 2024-03-07)(갱신: 2023-01-16) > Tournament Trees, Winner Trees and Loser Trees in Data Structure (접속: 2024-02-28)
programiz	> Insertion into a B-tree (접속: 2024-03-07)

 

4) 블로그

장고리즘
> [2019 5급 공무원 2차] 자료구조론 제 5문 (접속: 2024-02-28)

취미로 공부하기

> 10-3. 이진트리 개수 (접속: 2024-02-29)

walbatrossw/java-data-structures: 자바 자료구조 구현 및 요약정리

> ch07-red-black-trees (접속: 2024-02-28)

 

 

5) 기타

위키백과

> k-way merge algorithm (접속: 2024-02-28)

기타. 변경이력

일자	변경이력
2024-02-21	초안 작업 시작.
2024-03-15	일반 공개. [#blogger] [#티스토리]