- 계층적 구조를 나타내는 자료구조
- 트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다.
- 트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양이다.
- 노드 : 트리의 구성 요소
- 부모, 자식, 형제(sibling) 노드
- 루트(root) : 가장 상위의 노드, 최상위 부모 노드
- 서브트리 : 하나의 노드와 하위 노드로 이루어진 트리
- 단말(leaf, terminal) 노드 : 자식을 갖지 않는 노드
- 레벨 : 트리의 각 층 번호
- 높이(height), 차수(degree) : 트리의 최대 레벨, 한 노드의 자식의 수
이진 트리 (Binary Tree)
- 노드 하나가 최대 2개의 자식 노드를 갖는다.
- 모든 노드의 차수가 2 이하인 트리
- 차수가 2로 제한되어 구현이 용이
- 모든 값은 크다, 작다의 2개 기준으로 구분
functions
– BTree Create( )
– Boolean isEmpty(bt)
– BTree MakeBT(bt1, item, bt2)
– BTree Lchild(bt)
– BTree Rchild(bt)
– element Data(bt)
- 이진 트리의 노드 개수가 n이면 엣지의 개수는 n-1
- 높이가 h인 이진 트리는 푀소 h개, 최대 2^h -1개의 노드로 구성
- n개의 노드를 가지는 이진 트리의 높이
- 최대 : n
- 최소 : log2(n+1)
이진 트리 순회
- 순회란 어떤 데이터가 있을 때 그 데이터를 빠짐없이 방문하는 것을 의미한다.
- 전위 순회(Preorder)
-
VLR
-
현재 노드를 부모 노드로 생각했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문한다.
-
자손보다 루트 노드를 먼저 방문
-
- 중위 순회(Inorder)
- LVR
- 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문한다.
- 왼쪽 자손, 루트, 오른쪽 자손의 순으로 방문.
- 후위 순회(Postorder)
- LRV
- 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문한다.
- 자손을 먼저 방문한 후 루트 노드 방문
- 트리 삭제에 자주 사용
이진 탐색 트리 (Binary Search Tree)
- 이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있다.
레드-블랙 트리(Red-Black Tree)
레드-블랙 트리는 자가 균형 이진 탐색 트리이다
- 모든 노드는 빨간색 or 검은색
- 루트 노드는 검은색
- 모든 리프 노드(NIL)들은 검은색 (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색 즉, No Double Red(빨간색 노드가 연속으로 나올 수 없다)
- 모든 리프 노드에서 Black Depth는 같다. 즉, 리프노드에서 루트 노드까지 가는 경로에서 만나는검은색 노드의 개수가 같다.
