[자료구조] 10. 선택트리, 숲, 이진 트리 개수

01. 선택 트리

 

✅ 합병 정렬

• 차례로 정렬된 k개의 데이터 리스트를 완전한 순서를 유지하는 하나의 데이터 리스트로 만드는 과정
• 일반적으로 데이터 리스트가 k개인 경우 k-1번 비교를 통해 데이터 리스트에서 가장 큰/작은 값을 결정함
  • 데이터가 많을 수록 엄청난 비교 횟수(오버헤드) => 선택 트리를 이용하여 비교 횟수를 줄일 수 있음

 

 

 

 

✅ 승자 트리

• 비교 횟수가 많은 합병 정렬 대신 선택 트리를 이용하여 구현
• 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨

승자 트리 구성 전 단계

 

최초 승자 트리 구성

 

11 삭제 후, 24 추가

 

승자트리 재구성

=> 11 삭제 후, 24 추가하여 삭제되어 빈 부분을 비교하여 승자 트리 재구성

 

• 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교 단계부터는 비교 횟수가 감소됨
• 재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어즘

 

 

 

 

✅ 패자 트리

• 승자 트리보다 구현하기 쉬운 자료구조를 구상하다가 탄생(효율은 비슷)
• 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만! 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장(즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)
• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장

 

 

 

 

최초 패자 트리 구성

• 2레벨의 14는 4레벨의 14와 11을 비교해서 패자인 14를 넣은 것(2레벨 17은 4레벨의 12와 17을 비교)
• 1레벨의 12의 경우 2레벨의 내부 노드 값(패자)이 아닌 승자 값을 비교해서 패자인 12를 넣어줌(승자인 11은 0번 노드로)

 

11 삭제 후, 24를 넣고 재구성

• 재구성할 때는 자식과 자식간의 비교가 아니라 부모와 자식간의 비교!!

 

 

 

 

 

 

 

 

02. 숲

 

✅ 숲

• n(n>=0)개 이상의 분리된 트리 집합
• 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음 ↔ 숲을 연결하면 트리를 만들 수 있음

 

 

 

🔸숲의 이진트리 변환

 

 

 

🔸일반트리 → 이진트리(참고)

 

 

 

🔸숲 → 이진트리

각 트리를 루트의 왼쪽만 자식으로 가지는 이진트리로 변환

오른쪽 자식으로만 이진트리를 지정

• 숲을 하나의 통합된 자료구조에 넣어서 관리할 수 있음

 

 

 

 

 

 

03. 이진 트리 개수

 

🔸노드 개수에 따른 가능한 이진 트리

 

노드가 3개인 이진 트리의 개수

 

노드가 3개인 이진트리에서 전위 순회 방문 순거가 1,2,3인 이진 트리

=> 순회 방법이 정해진 상태에서 출력되는 값들의 순서가 정해지면 이진트리는 제한된 개수만큼만 만들어짐

 

Q. 노드가 3개인 이진 트리에서 전위 순회 방문 순서가 1,2,3 이고 중위 순회 방문 순서가 1,3,2라면 위의 5개의 트리 중 어느 것일까?

A. 두번째 트리

▪️ 첫번째 트리 중위 순회 방문

1, 2, 3

 

 

▪️ 두번째 트리 중위 순회 방문

 

1, 3, 2

 

=> 어떤 이진 트리에 대한 [전위 순회와 중위 순회 방문 순서]가 주어지면 트리 구조는 유일하게(1개) 특정할 수 있음