트리
단방향 그래프의 한구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리구조 라고 부른다.
사이클이 없는 하나의 연결 그래프
- 부모노드 : A는 B와 C의 부모노드
- 자식노드 : B와 C는 A의 자식노드
- 리프노트 : 자식이 없는 노드
깊이(depth)
루트로부터 하위 계층의 특정 노드까지의 깊이.
예) A의 depth: 0 / B,C의 depth: 1 / D,E,F,G의 depth : 2
레벨(level)
같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현한다.
높이(Height)
리프 노드를 기준으로 루트까지의 높이
부모노드 : 자식 노드의 가장 높은 height값에 +1 한 값
위 그림에서 H, I, E, F, J의 높이 : 0
D, G 의 높이 : 1
B, C 의 높이 : 2
A 의 높이 : 3
서브트리(Sub tree)
root에서 뻗어나오는 큰 트리의 내부에, 트리구조를 갖춘 작은 트리
서브트리: (D, H, I), (B, D, E), (C, F, G, J)
실사용 예제
컴퓨터의 디렉토리 구조, 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등
이진트리
자식 노드가 최대 두 개인 노드들로 구성된 트리.
정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리
완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.
▶이진탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다.
이진탐색트리(Binary Search Tree)
이진 탐색과 연결 리스트를 결합한 이진트리
이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료입력과 삭제를 가능하게끔 고안됨.
- 각 노드에 중복되지 않는 키가 있다.
- 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
- 좌우 서브트리도 모두 이진 탐색 트리여야 한다.
- 기존 이진 트리보다 탐색이 빠르다
- 트리의 높이가 h라면 복잡도는 o(h)
=> 이진탐색트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.
탐색 과정
1.루트 노드의 키와 찾고자 하는 값을 비교한다. 만약 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.
=>찾을때까지 반복해 진행한다. 만약 값을 찾지 못하면 그대로 연산을 종료한다.
트리순회
왼쪽 -> 오른쪽 으로 진행한다.
전위 순회
가장 먼저 방문하는 노드 : 루트
왼쪽의 노드들을 순차적으로 둘러본 뛰, 오른쪽 노드 탐색을 시작한다.
중위 순회
루트를 가운데 두고 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하며, 루트를 기준으로 왼쪽에 잇는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다. 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식.
오름차순으로 값을 가져올 때 쓰인다.
후위 순회
루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
트리를 삭제할 때 사용된다. 자식노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문이다.