- [ 크래프톤정글/C 언어 ][C] 이진 탐색 트리(Binary Search Tree, BST) 개념 및 구현2022-11-28 21:38:06이진 탐색 트리(Binary Search Tree, BST) 원소를 특정한 조건에 따라 정렬해 놓은 이진트리를 말한다. 이진 탐색 트리는 탐색을 위해 정렬을 해놓은 트리이다. 이진 탐색 트리는 검색 수행 연산은 O(logN) 이다. 이진 탐색 트리의 속성 모든 원소는 유일한 키 값을 갖는다. 즉, 중복된 내용을 가지는 항목은 없다. 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값을 갖는다. 오른쪽 서브트리의 모든 원소들은 루트의 키보다 큰 값을 갖는다. 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다. 즉, 일반 트리나 이진트리하고 똑같이 이진탐색트리도 재귀적인 정의를 한다.(서브트리에서 볼 때나 루트노드에서 볼 때나 위의 조건은 모두 성립되므로) 트리 안에서 어떤 노드를 루트로 잡던지 위 조건은..
- [ 크래프톤정글/C 언어 ][C | WEEK05] 연결리스트 구현 - 추가예정2022-11-27 20:32:49C 언어로 연결 리스트 구현 정글에서 5주차가 진행되고 RB-Tree를 구현하는 과제가 주어졌다. 그것도 C 언어를 이용해서 RB-Tree의 자료구조를 구현해야 하는데, C 언어에 대한 문법도 익숙치 않을 뿐더러 RB-Tree 자료구조 구현 자체가 쉽지 않다기에 비교적 쉬우면서도 선수지식으로 알아야 할 '연결 리스트'와 '이진 검색 트리'를 C 언어를 구현해 봄으로써 C 언어를 익히고, RB-Tree를 구현하고자 한다. Operator 1. 연결리스트 구조체 만들고 사용하기 연결 리스트에서 노드를 추가하는 규칙 노드에 메모리 할당 next 멤버에 다음 노드의 메모리 주소 저장 data 멤버에 데이터 저장 마지막 노드라면 next 멤버에 NULL 저장 아래 이미지는 사용자가 정의한 구조체를 이용해 연결리스..