선형 데이터 구조와는 다르게 트리 구조는 데이터를 계층으로 정렬한다.
트리 구조의 중심점은 루트노드로, 트리의 나머지 요소들은 루트 노드를 기준으로 구성된다. 루트 노드에서 멀어지는 방향으로 다른 노드가 연결되면, 해당 노드를 하위 노드 또는 자식 child 노드라고 한다. 루트 노드를 향한 방향으로 연결된 노드는 상위 노드, 부모 parent 노드라고 한다. 부모 노드는 여러개의 자식노드를 가질 수 있지만 자식 노드는 하나의 부모 노드만을 갖는다. 자식 노드를 가지지 않는 트리구조의 말단을 리프 노드라고 한다.
노드 에는 데이터를 저장하며, 이때 저장된 데이터를 식별하는 데 사용되는 키와 저장된 데이터인 값을 포함할 수도 있다.
트리를 탐색하는 과정을 순회 traversal 라고 한다.
노드 하나와 그 자식 노드들로 구성된 트리를 서브트리 _subtree _라고 한다.
이진 트리 binary tree
가장 많이 사용되는 데이터 구조. 부모 노드가 항상 2개의 자식 노드와 연결되어 있다. 가장 일반적인 유형은 이진 탐색 트리 binary search tree 로 노드의 키를 기준으로 정렬한 상태. 이진 탐색 트리에서 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다. 트리에 노드를 추가, 삭제할 수 있고 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인 할 수 있다. 이진 탐색 트리는 트리 구조로 정렬된 데이터를 저장하는 데 효율적이어서 폭넓게 사용된다.
불균형 이진 트리
많은 노드가 단 하나의 자식 노드를 가짐으로서 트리 구조가 불균형한 상태로, 이를 해결하려면 트리의 균형을 조정하는 과정을 거쳐야 한다. 트리의 균형을 조정하는 과정은, 트리의 역할은 유지하되 가능한 한 최소 높이 (자식 노드의 계층이 최소)로 만드는 것이다.
트리의 불균형을 해결하는 것은 메모리 관리를 위해 중요하다. 즉, 균형 잡힌 구조는 메모리를 더 효율적으로 사용할 수 있다. 일부 이진 탐색 트리는 균형을 조정할 수 있다.
AVL 이진 트리 Adelson-Velsky and Landis
서브트리 2개 사이에서 높이 차이를 감지하면 트리 회전 tree rotation이라는 균형 조정 과정을 수행한다. 트리 회전에 의해 노드 하나는 위로 이동하고 다른 노드 하나는 아래로 이동한다. 시간 복잡도는 O(logn). 일부 데이터 베이스 검색 시스템에서 사용된다.
RB 이진 탐색 트리 Red-Black
노드마다 빨강 또는 검정으로 해석되는 비트를 포함한다. 일반적으로 루트 노드는 검정이고, 빨강 노드는 검정 노드를 자식 노드로 갖는다. 자체적으로 균형을 조정한다는 점에서 AVL 트리와 비슷하지만, 트리의 구조 때문에 균형을 조정하는 과정에서 회전수가 적어 더 효율적이다. 시간 복잡도 O(logn).
B 트리
컴퓨터 과학자들이 데이터베이스 시스템을 설계할 때 사용하는 데이터 구조로, 자체적인 균형 조정 기능을 갖춘 트리 유형. B 트리에는 자식 노드 3개 이상을 갖는 부모 노드가 있다. 많은 파일 시스템에서 데이터 계층 구조로 사용된다.
힙 heap
이진 트리 데이터 구조의 한 종류이며, 값이 최대 혹은 최소인 노드에 빠르게 접근해야 하는 응용 프로그램에 적합하다. 힙을 사용해서 큐를 구현할 수 있다. 루트 노드가 힙에서 가장 큰 값이고 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성된 힙을 최대 힙 max heap 이라고 한다. 반대로 최소 힙 min heap을 구성할 수도 있다.
힙 데이터 구조는 힙 메모리 heap memory 와 전혀 다른 개념이다. 실제로 힙 메모리는 프로그래머가 직접 관리해야 하는 메모리의 영역을 뜻한다. 프로그래머가 작성한 코드에 따라 메모리 공간을 동적으로 할당하거나 해체하는 부분이기도 하다. 힙 데이터 구조와 다른 방식으로 구현된다는 것을 확실히 구분해 둘 필요가 있다.
