6: 자료구조-5(연결 리스트: 트리)

6: 자료구조-5(연결 리스트: 트리)

트리 : 연결 리스트를 기반으로 한 새로운 데이터 구조

이진 탐색 트리

- 연결 리스트에서의 요소들의 연결은 1차원적으로 구성되어 있고, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있음

- 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됨

- 가장 높은 층에서 트리가 시작되는 노드 ‘루트’

- 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 함

- 트리의 노드들은 최대 두 개의 자식 노드를 가짐. 이진법의 이진을 따와서 최대 2라는 것을 표현

- 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 자신의 값보다 큼 이런 트리 구조는 이진 검색을 수행하는 데 유리함

- 트리를 탐색하려면 트리의 가장 위에 있는 루트라는 노드만 알려주면 트리의 모든 곳으로 갈 수 있음

- 트리에서 7개의 요소가 있다면 어떤 값을 찾는 데에는 3단계밖에 걸리지 않음 -> 필요한 단계의 수는 O(log n)

- 이진 검색 트리를 활용했을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)

이진 검색 트리의 노드 구조체

typedef struct node { // 노드의 값 int number; // 왼쪽 자식 노드 struct node *left; // 오른쪽 자식 노드 struct node *right; } node;

50을 재귀적으로 검색하는 이진 검색 함수를 구현함(50이 트리에 있으면 true 아니면 false를 받는 코드 작성)

// 트리의 루트의 주소를 입력 받음 // 이진 검색 함수(*tree는 이진 검색 트리를 가리키는 포인터) bool search(node *tree) { // 트리가 비어있는 경우 “false”를 반환하고 함수 종료 if (tree == NULLL) { return false; } // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색 else if (50 < tree->number) { return search(tree->left); } // 현재 노드의 값이 50보다 작다면 오른쪽 노드 검색 else if (50 > tree->number) { return search(tree->right); } // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환 else // (50 == tree->number) { return true; } }

트리는 2차원적이고 재귀적으로 정의되어 있는데 이 의미는 어떤 노드에서도 왼쪽이 더 작고 오른쪽이 더 크다는 것

https://www.boostcourse.org/cs112/joinLectures/41307

from http://everysmallstep.tistory.com/51 by ccl(A) rewrite - 2021-12-11 21:01:22