1. 선택트리
1.1. 합병 트리
•
차례로 정렬된 데이터 리스트 k개를 완전한 순서로 유지하는 하나의 리스트로 만드는 과정
•
일반적으로 데이터 리스트가 k개인 경우 k-1번 비교
•
선택 트리를 활용하여 비교 횟수 줄일 수 있음
1.2. 승자 트리
•
부모 노드가 두 자식 노드보다 작은 값을 갖는 포화 이진 트리
•
작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
•
트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
•
결과적으로 루트의 값이 트리에서 가장 작은 값이 됨
•
프로세스
24를 넣을때는 3번만 비교하면됨
•
첫번째 단계에서는 비교 횟수를 줄이지 못했지만, 두번쩨 비교단계부터는 비교 횟수가 감소됨
•
재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어줌
1.3. 패자 트리
•
부모 노드가 두 자식 노드보다 작은 값을 갖는 포화 이진 트리인 점은 승자 트리와 같지만, 패자 트리는 루트 노드 위에 최상이 0번 노드를 가짐
•
최상위 0번 노드에는 최종 승자를 저장
•
트리의 각 노드는 승자가 아닌 패자를 저장
•
즉, 패자를 부모노드에 저장하고, 승자는 부모의 부모 노드로 올라가서 다시 경쟁
•
루트에는 마지막 패자를 저장하고, 최종 승자는 0번 노드에 저장
•
예시
◦
0번 노드에 최소값이 있으므로 이 값을 제거하여 전체 리스트에 저장
▪
저게된 값을 갖고 있던 4번 리스트 head에 위치한 값 24를 패자 트리에 올려 보내고 경쟁을 시킴
▪
패자 트리를 재구성
2. 숲
2.1. 정의
•
기본 정의
◦
분리 된 트리 모임
◦
트리의 모임
◦
0개 이상의 분리된 트리 집합
•
기술적 정의
◦
n( n≥0)개 이상의 분리된 트리 집합
◦
트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음
▪
숲의 개수 = 루트 노드의 자식 노드 수
◦
반대로 숲을 연결하면 트리를 만들 수도 있음
2.2. 일반트리 → 이진 트리 변환
•
이진 트리 변환 방법
•
추가 예시
2.3. 숲의 이진트리 변환
일반트리 → 이진트리 변환 과정과 동일
•
먼저 각 트리를 이진 트리로 바꿈
•
이때 이진트리의 루트는 왼쪽 서브트리만 가짐
•
다음은 첫번째 이진트리 루트를 최상위 루트로 하고, 왼쪽 자식은 그 외쪽 서브 트리, 오른쪽 자식은 나머지들의 이진 트리가 되도록 함
3. 이진 트리 개수
3.1. 노드와 이진 트리의 관계
•
노드 개수에 따른 가능한 이진 트리 개수
•
노드 개수가 3개인 이진트리 개수
◦
노드가 3개인 이진트리에서 전위 순회 방문순서가 1 → 2→ 3 이고, 중위 순회 방문 순서가 1 → 3 → 2 라면 위 5개 트리중 어느 것일까?
1 | 2 (정답) | 3 | 4 | 5 | |
전위순회(PLR) | 1→2→3 | 1→2→3 | 1→2→3 | 1→2→3 | 1→2→3 |
중위순회(LPR) | 1→2→3 | 1→3→2 | 2→1→3 | 2→3→1 | 3→2→1 |
•
어떤 이진 트리에 대한 전위 순회와 중위 순회 방문 순서가 주어지면 트리 구조를 유일하게(한 개) 정할 수 있음
3.2. 스택을 이용한 이진 트리 순회
1부터 n까지의 수를 스택에 넣었다가 가능한 모든 방법을 삭제하여 생성할 수 있는 경우의 수와 n개의 노드를 가진 상이한 이진트리의 수가 같음
•
카탈링의 수식
•
push()
◦
트리 생성 과정으로 껍데기 노드와 왼쪽 서브트리를 나타냄
•
pop()
◦
껍데기 노드에 값을 넣고 오른쪽 서브트리로 이동하는 것
•
예시
