RB트리 탐색 및 최솟값/최댓값 함수 구현하기RPG 게임에서 레벨이 오르면 새로운 콘텐츠가 해금되듯이, RB트리도 삽입 기능이 구현되면 여러 기능들을 추가로 구현하는 것이 가능해지는데요. 그중 대표적인 것이 바로 탐색 기능입니다. 특정 값을 가진 노드를 찾거나, 가장 작거나 큰 값을 가진 노드를 빠르게 찾을 수 있게 되는 것이죠. 이번 글에서는 이러한 핵심 탐색 기능을 담당하는 함수들을 직접 구현해 보겠습니다. RB트리 탐색 함수 (rbtree_find)rbtree_find 함수는 RB트리에서 특정 값을 가진 노드를 찾아 반환하는 함수입니다. RB트리라고 해서 탐색 방식이 특별하지는 않고, 기본적인 이진 탐색 트리(BST)와 완전히 동일한 방식으로 동작합니다. 찾고자 하는 값이 현재 노드의 값보다 작으..

RB트리 삽입 구현하기이제까지 RB트리의 개념과 규칙, 그리고 파생 개념들을 배우고, 삽입과 삭제 과정의 작동 원리를 충분히 이해해보는 시간을 가졌는데요. 또한 회전, 색상 교환 등 자주 사용되는 연산에 대한 유틸리티 함수 구현까지 마쳤다면, 본격적으로 C언어를 활용해 RB트리의 핵심 로직을 직접 구현할 준비가 끝났다고 볼 수 있습니다. 본격적인 구현 내용에 들어가기 전에, 만약 위의 이론들이 아직 완전히 숙지되지 않았다면 아래 포스트들을 먼저 참고하시기 바랍니다.[CS] RB트리의 개념과 규칙, 파생 개념[CS] RB트리의 삽입과 회전[CS] RB트리의 삭제[C언어] RB트리 유틸리티 함수 구현하기※ 주의: 해당 RB트리 구현은 set 자료구조를 기반으로 하고 있습니다. RB트리 삽입 후 재조정 함수 ..

RB트리 초기화 및 전체 삭제 구현하기라면을 끓일 때 "면부터 넣을까, 스프부터 넣을까?"라는 질문이 자주 나오는데요. 면일지 스프일지 고민이 되시겠지만 진짜 정답은 바로 냄비에 물부터 올리기입니다. RB트리(Red-Black Tree)도 마찬가지입니다. 삽입과 삭제라는 핵심 로직에 집중하기 전에, 트리 자체를 초기화하고 전체를 삭제할 수 있는 기본 기능부터 먼저 마련해야 합니다. 이처럼 올바르게 준비된 RB트리 위에서 특정 노드에 대한 삽입, 삭제, 탐색 등 다양한 연산들이 제대로 동작하게 되는 것이죠. 이번 글에서는 RB트리를 초기화하는 함수와 RB트리 전체를 삭제하는 함수를 구현해봅니다. RB트리 초기화 함수 (new_rbtree)new_rbtree 함수는 RB트리를 사용하기 위한 준비 단계로, ..

RB트리 유틸리티 함수 구현하기 (rotate, color flip, color swap)RB트리의 삽입과 삭제를 공부하면서 눈에 띄는 공통된 작동 방식들이 있었는데요. 바로 회전(Rotation), 색상 반전(Color Flip), 색상 교환(Color Exchange)과 같은 연산들이었습니다. 이러한 연산은 RB트리의 균형을 유지하는 핵심 요소로, 삽입과 삭제 과정에서 반복적으로 등장하는 친구들입니다. 그래서 본격적인 RB트리 구현에 앞서, 이들 연산을 별도의 유틸리티 함수로 분리해 구현해 보았습니다. 이렇게 미리 구성해두면, 이후 삽입과 삭제 알고리즘을 작성할 때 핵심 로직에 집중할 수 있고, 코드도 훨씬 더 깔끔하게 유지할 수 있습니다. 이번 포스팅에서는 제가 직접 구현한 회전, 색상 반전, 색상..

Binary Search Tree (5) - postOrderIterativeS2 함수 구현하기이진 탐색 트리의 후위 순회에 대해 스택 2개를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수주어진 요소 확인하기구조체BSTNode: (struct) 이진 탐색 트리 노드 구조체item: (int field) 노드의 값*left: (pointer field) 왼쪽 자식 노드 주소*right: (pointer field) 오른쪽 자식 노드 주소StackNode: (struct) 스택 노드 구조체*data: (pointer field) 이진 탐색 트리 노드 주소*next: (pointer field) 다음(스택 아래쪽) 노드 주소Stack: (struct) 스택 구조체*top: (pointer field..

Binary Search Tree (4) - postOrderIterativeS1 함수 구현하기이진 탐색 트리의 후위 순회에 대해 스택 1개를 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수주어진 요소 확인하기구조체BSTNode: (struct) 이진 탐색 트리 노드 구조체item: (int field) 노드의 값*left: (pointer field) 왼쪽 자식 노드 주소*right: (pointer field) 오른쪽 자식 노드 주소StackNode: (struct) 스택 노드 구조체*data: (pointer field) 이진 탐색 트리 노드 주소*next: (pointer field) 다음(스택 아래쪽) 노드 주소Stack: (struct) 스택 구조체*top: (pointer field..

Binary Search Tree (3) - preOrderIterative 함수 구현하기이진 탐색 트리의 전위 순회를 스택을 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수주어진 요소 확인하기구조체BSTNode: (struct) 이진 탐색 트리 노드 구조체item: (int field) 노드의 값*left: (pointer field) 왼쪽 자식 노드 주소*right: (pointer field) 오른쪽 자식 노드 주소StackNode: (struct) 스택 노드 구조체*data: (pointer field) 이진 탐색 트리 노드 주소*next: (pointer field) 다음(스택 아래쪽) 노드 주소Stack: (struct) 스택 구조체*top: (pointer field) 스택 최상단 ..

Binary Search Tree (2) - inOrderIterative 함수 구현하기이진 탐색 트리의 중위 순회를 스택을 사용하여 반복문으로 구현하고, 순회 결과를 출력하는 함수주어진 요소 확인하기구조체BSTNode: (struct) 이진 탐색 트리 노드 구조체item: (int field) 노드의 값*left: (pointer field) 왼쪽 자식 노드 주소*right: (pointer field) 오른쪽 자식 노드 주소StackNode: (struct) 스택 노드 구조체*data: (pointer field) 이진 탐색 트리 노드 주소*next: (pointer field) 다음(스택 아래쪽) 노드 주소Stack: (struct) 스택 구조체*top: (pointer field) 스택 최상단 노..