20. 커널 자료 구조(kernel data structure) 2

트리(tree)는 자료 간의 부모-자식 관계(상하 관계)를 표현하는 자료 구조이다. 모든 원소의 자식 원소가 2개 이하로 이루어진 트리를 이진 트리(binary tree)라 하고, 또 이 중 부모보다 큰 원소를 왼쪽 자식 원소로, 부모보다 작은 원소를 오른쪽 자식원소로 배열하는 트리를 이진 탐색 트리(binary search tree)라 한다. 이진 탐색 트리는 일반적인 이진 트리보다 검색이 더 용이하다. 트리의 층(level)은 맨 위의 부모 노드와 맨 아래의 자식 노드 사이의 최대의 거리를 의미하는데, 자료를 탐색하는 데에는 트리의 층 개수의 원소를 탐색하는 시간 만큼 걸린다. 이 때문에 최대한 층이 적은 트리인 균형 이진 탐색 트리(balanced binary search)로 만들어야 탐색 시간이 제일 적다.

해쉬 함수(hash function)는 자료를 입력 받아 결과를 출력하는 함수로, 자료 구조로 이용할 수 있다. 함수의 형태이기 때문에 어떤 자료든 빠르게 탐색할 수 있다는 장점이 있지만 다른 입력에 같은 값이 출력되는 해쉬 충돌(hash collision)이라는 것이 존재한다. 이러한 문제는 출력이 같은 각 입력을 연결 리스트로 연결하면 해결할 수 있다.

비트맵(bitmap)은 이진수 형태의 자료 구조이다. n 자리 이진수로 이루어진 비트맵은 주로 자료 n개의 사용 가능성을 표시할 때 사용된다. 예를 들어 0은 사용 가능한 자료, 1은 사용 불가능한 자료임을 나타낼 때 쓰인다.