티스토리 뷰
트리
- 트리는 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적인 구조를 갖는 비선형 자료구조입니다.
- 마치 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있기에 트리라고 불립니다.
- 트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다.
- 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺습니다.
- 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있으며, 같은 레벨의 노드를 형제 노드(Sibling Node)라고 합니다.
- 각 노드는 자식 노드를 가질 수 있으며, 자식 노드 역시 다시 자식 노드를 가질 수 있는 재귀적인 특성을 가지고 있습니다.
- 가장 대표적인 예제로는 컴퓨터의 디렉토리 구조가 있습니다.
이진트리(Binary tree)
- 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 특별한 형태의 트리입니다.
- 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있습니다.
- 이때, 왼쪽 자식 노드는 현재 노드보다 작은 값을 갖고, 오른쪽 자식 노드는 현재 노드보다 큰 값을 갖는 것이 일반적입니다.
- 이진 트리는 포화 이진트리와 완전 이진트리 등이 존재합니다.
- 포화 이진트리는 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
- 완전 이진트리는 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
이진 탐색 트리(Binary Search Tree)
- 이진 탐색 트리는 이진 탐색의 알고리즘이 이진트리에 적용된 트리 구조입니다.
- 이진 탐색이란 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나입니다.
- 이진 탐색은 오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘입니다.
- 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지고 있습니다.
만약 이진 탐색 트리를 사용해 특정값을 탐색한다면.
- 루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료합니다.
- 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
- 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.
- 1~3을 반복해 진행합니다.
- 탐색 연산의 시간 복잡도는 트리의 높이에 비례하며, 일반적으로 O(log n)입니다.
트리 순회
- 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다.
- 트리를 순회할 수 있는 방법은 전위 순회, 중위 순회, 후위 순회의 세가지입니다.
- 전위 순회는 루트,왼쪽,오른쪽 순으로, 중위는 왼쪽,루트,오른쪽 , 후위는 왼쪽,오른쪽,루트 순으로 진행됩니다.
- 전위 순회는 주로 트리를 복사할 때,중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때,후위 순회는 트리를 삭제할 때 주로 사용합니다.
- 번외로, 트리의 레벨를 기준으로 순회하는 레벨순회가 존재합니다.
댓글