트리 Flashcards
이진트리
[정의] 부모-자식 관계로 이루어진 계층적인 구조를 나타내는 자료구조
[구성] Root, Node, Depth, Height, Degree
[유형]
1. 이진트리 : 모든 노드가 2개의 서브트리를 보유. 모든 노드 차수 2이하
2. 포화 이진트리 : 트리의 각 레벨에 노드가 다 차있는 이진트리
3. 완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, leaf 노드들이 트리의 왼쪽부터 채워지는 트리
4. 경사 이진트리 : 트리의 노드가 왼쪽이나 오른쪽으로 한쪽으로만 노드가 있는 트리
5. AVL(높이 균형) 트리 : 왼쪽 하위 트리와 오른쪽 하위트리의 높이가 1이상 차이 나지 않는 이진트리
6. 완전 높이 균형 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진트리
이진트리순회
[정의] 그래프 및 트리 내 데이터에 효율적 접근위해 전위, 중위, 후위 순회기반 노드를 탐색하는 트리 순회 기법
[특징] 그래프 탐색 일종, 재귀 순환, 시간 복잡도 O(n), 공간 복잡도 O(n)
[종류]
1.전위 순회(Pre Order) : DLR, 부모(Root) 우선 (깊이우선순회)
2.중위 순회(In Order) : LDR, 좌측 최하위 노드 시작, 부모(Root)가 중간 (오름차순/내림차순에 사용)
3.후위 순회(Post Order) : LRD, 좌측 최하위에서 시작, 부모(Root)가 맨 마지막 (트리삭제)
4.레벨 오더 순회 : 위에서 아래, 왼쪽에서 오른쪽
이진탐색트리
[정의] 중복된 노드가 없고, 왼쪽 서브 트리에는 작은 값, 오른쪽 서브 트리에는 큰 값으로 구성되는 이진 트리
[특징] O(log N)의 평균 탐색 속도 보장, 삽입/삭제 시 트리 재구성 필요, 모든 키는 유일
[삽입연산]
1. 전체 트리에서 동일값 탐색
2. 탐색 성공시 종료
3. 탐색 실패시 부모 노드가 NULL이면 부모 노드에 삽입
5. 부모 노드보다 작으면 왼쪽, 크면 오른쪽 삽입
[삭제연산]
1. 노드가 leaf인경우 - leaf노드의 부모노드를 찾아서 연결 끊음
2. 삭제노드가 하나의 서브트리만 가지고 있는 경우 - 해당 노드를 삭제하고 서브트리는 부모노드에 붙여줌
3. 삭제노드가 두개의 서브트리를 모두 가지고 있는 경우 - 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 이동
AVL Tree
[정의] 밸런스 팩터를 1,0,-1로 유지하여 트리의 균형을 유지한 O(log N) 성능을 보장하는 이진탐색트리
[특징] 균형 상태 유지, 이진 트리, 회전 연산, O(log N)속도록 검색,삽입,삭제 가능
* Balance Factor = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
[동작]
1. 삽입 : Root Node부터 크기를 비교항 작으면 왼쪽, 크면 오른쪽에 삽입
2. 회전 : Balance Factor가 절대값 1이상이 될 경우 불균형 발생으로 LL,RR,LR,RL 회전
3. 삭제 : 왼쪽 트리 최댓값이나 오른쪽 트리 최솟값과 삭제대상 변경 및 최종 삭제
[회전] 단순 회전(LL,RR) 이중회전(LR, RL)
* AVL Tree는 Binary Search Tree에 Balance를 유지하여 탐색 하나 효율성 문제로 Red-Black Tree가 대두
2-3 Tree
[정의] leaf 노드가 아닌 노드가 2개 또는 3개의 child를 가지는 노드로 이루어진 이진 탐색 트리
[특징] AVL트리보다 단순하지만 완전균형트리를 지향
B Tree
[리드] 균등한 응답속도 보장을 위한 탐색트리
[정의] Leaf Block에 정렬된 데이터와 해당 데이터를 가진 행의 위치를 가리키는 레코드 식별자로 구성된 균형 트리
[특징]
- 탐색, 추가, 삭제는 root node로부터 시작함
- 동일레벨의 Leaf node (균형)
- 자식 노드의 개수가 2개 이상인 트리
[조건]
- Root node : 최소 2개의 자식수, 한 개의 값
- Leaf node : 동일 레벨에 존재 (Root에서 Leaf로 가능 경로 길이 동일)
- 데이터 : Root 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터(1/2이상 채워져야함)
[장/단점]
- (장) 균등한 탐색 속도 보장, 삽입, 삭제 후에도 균형 트리 유지, 저장 장치의 효율성
- (단) 트리의 균형을 유지하기 위해 복잡한 연산, 순차접근시 중위(inorder) 순회에 따라 성능저하 발생 -> B+트리로 해결
B+ Ttee
[정의] B Tree 순차탐색 문제 개선 위해 인덱스와 순차 트리를 구별하여 데이터를 순차 접근하기 용이하게 만든 자료구조
[특징] Leaf 노드에만 데이터 포함, 순차 검색에 효율
[구성]
- 인덱스(Index) Set: 실제 키 값 검색 경로 제공
- 순차(Sequence) Set: Leaf노드로만 구성, Linked list로 연결
[장/단점]
- (장) 순차 접근 용이 저장, 검색 빠름
- (단) 인덱스셋, 순차셋 의 중복성 존재
B* Tree
[정의] Split 을 줄이기 위해 Root 노드와 Leaf 를 제외한 Tree 의 모든 노드가 최소한 2/3 가 Key 값으로 채워지도록 제한한 다중 검색 트리
[특징] B-Tree의 삽입 시 Split 현상 최소화 , 공간활용도 66%
[장/단점] (장) 데이터 삽입/삭제가 잦은 경우 유리, (단) 대용량 데이터 처리 어려움
T Tree
[정의] AVL-Tree의 이진 탐색 특성 및 높이 균형과 B-Tree의 업데이트와 저장 효율(한 노드는 여러 개 데이터 가짐)을 물려 받은 메모리 기반 DBMS 최적화 트리형 자료구조
[구성요소] Parent Pointer, Left Child Pointer, Right Child Pointer, Data, Control
[노드종류]
- 내부 노드 : 오른쪽, 왼쪽 서브트리 소유. 데이터 개수는 T트리 생성시 결정
- 하프리프 노드 : 방향과 상관없이 한쪽 서브트리만 소유
- 리프 노드 : 자식포인터가 하나도 없음
R Tree
[정의] 최소 사각형(MBR: Minimum Bounding Rectangle)에 기반 한 인덱싱 기법으로 N차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 질의를 빠르게 수행할 수 있는 자료구조
[장점/단점]
- (장) 다차원 data쿼리 가능, 구현용이
- (단) 임의 삽입순서로 성능저하, 겹침현상
[활용]
- SAM(Spatial Access Method) 같은 선/면/다각형/다면체의 저장, 검색에 활용
R+ Tree
[정의] R트리의 노드간 MBR 중복 제거를 통해 검색 성능을 향상시킨 트리
R* Tree
[정의] R-트리의 삽입, 삭제 알고리즘 개선하여, 삽입, 삭제시 부모 노드의 MBR이 효율적으로 확장될 수
있도록 알고리즘을 개선한 R 트리의 변형
TRIE
[리드] 고속 문자열 탐색
[정의] Key값을 이루는 문자 개수를 레벨로 구성하는 트리 구조
[특징] 순서 데이터, 고속처리, Cache Friendly, 자동완성
[종류] Standard Tries, Compressed Tries , Radix trie(Patricia trie), Suffix Tries
MCTS
[정의] 전수 조사등의 시간 제약적 문제에 대해 Random 시뮬레이션을 통한 효율적 트리 경로 탐색이 가능한 알고리즘
[특징] Min-Max 알고리즘의 성능을 개선, 몬테카를로 확률기법 적용
* 바둑, 체스등 게임에 주로 활용
[주요 처리단계] (예시-바둑)
1. 선택 : Root node에서 시작 현재까지 펼쳐진 트리 선택 (수 읽기)
2. 확장 : 선택한 트리에서 하나 이상의 자식 node 를 생성하여 하나 선택 (수 읽기 확장)
3. 시뮬레이션 : 선택된 자식 node에서 게임의 시뮬레이션 수행 (임의 수 예측)
4. 역전파 : 시뮬레이션 결과 반영 (승상 가능성 예측)
* 병렬컴퓨팅 기반 1~4의 단계를 반복 수행하며 정확도를 개선
