자료구조 : 트리(편향, 균형, 레드블랙, 다양한 이진트리..)

* 트리

비선형 계층적 자료 구조(데이터 순차저장x)  / 재귀적 자료구조(트리 내 다른 트리 ㅇ)

부모-자식 계층적 구조, 사이클이 없음.

노드 : N, 간선 : N-1

레벨 : 루트에서 노드까지 간선의 수

 

 

** 트리 순회 방식

- 전위 순회 : 루트 -> 왼 -> 오

- 중위 순회 : 왼 -> 루트 -> 오

- 후위 순회 : 왼 -> 오 -> 루트

 

 

 

1) 편향트리

모든 노드가 한 쪽으로만 자식을 가지는 이진 트리

 

 

 

2) 이진트리

각 자식노드 차수가 2이하

 

 

2-1) 정 이진트리

자식 노드 수 0 or 2개(1개 불가능)

 

 

2-2) 완전 이진트리

마지막 레벨을 제외하고는 다 채워져있고, 마지막 레벨은 왼쪽부터 채워져있음

 

 

2-3) 변질 이진트리

모든 노드가 오직 한 개의 자식만 가지는 이진 트리

 

 

2-4) 포화 이진트리

모든 노드 꽉찬 경우

 

 

2-5) 균형 이진트리

왼쪽 서브-오른쪽 서브 높이차 1

 

 

 

 

2-6) 이진 탐색 트리(BST : Binary Search Tree) 

순서화 된 이진트리, 탐색시에 유리

왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼

 

삽입하면, 크기에 영향을 받기 때문에 변질트리 가능

이진 탐색트리 O(log N)에서 변질트리 O(N)되어 효율 떨어질 수 있음

이런 경우에는 AVL, 레드블랙으로 해결하기

 

 

 

4) m원 탐색 트리(multi way search tree)

이진 탐색 트리 확장, 높이 줄이기 위해 사용

 

 

5) 균형트리(B Tree)

m원 탐색 트리에서 높이 균형 유지하는 트리

height balanced multi way tree

 

 

 

6) 레드블랙 트리

자가 균형 이진 탐색 트리

모든 노드는 red/black

루트노드 black

모든 리프노드 black

모든 리프노드~루트노드 depth중에 black개수는 같음

red노드 자식은 black(red 연속 불가)

 

 

** 새로운 노드 삽입시, double red 문제 발생시 해결

 

1) recoloring : 노드의 삼촌이 red일때

노드의 부모, 삼촌은 black, 조상을  red로 바꾸기

조상이 루트라면 black으로 바꾸기

 

2) restructuring : 노드의 삼촌이 black 일때

노드, 부모, 조상 오름차순 정렬하고 중간값을 부모로, 나머지는 자식으로 바꾸기

부모된 노드는 black, 자식은 red로 바꾸기