트리(Tree)_2

이진트리 ADT 구현과 메쏘드

배열에 기초한 이진트리

• 1D 배열을 이용한 이진트리 표현
• 순위 i의 노드의 대해 왼쪽 자식의 위치 순위 2i, 오른쪽 자식의 위치 순위 2i+1, 부모의 위치순위 i/2
• 0에 관한 연산 오류를 피하기 위해 순의 0셀은 사용하지않음, 사용하지 않는 셀도 표시 널마커('#')나 널포인터

  

 

 

 

 

 

 

 

 

• 만약 MAX를 노드 순위 중 최대값이라 하면 배열크기 N = MAX로 해야함 
• 배열크기 N = n 인 경우가 최선임
• 이 경우는 크기 N인 배열의 순위 0을 제외한 모든 셀이 이진트리의 노드를 표현하는 데 사용되어 기억장소의 낭비가 전혀 없는 상황
• 편향이진트리가 최악의 경우가 됨
  

  

 

 

 

 

 

 

 

 

 

 

연결리스트에 기초한 이진트리

• 연결리스트에 기초하여 이진트리 저장
• 각 노드는 원소, 부모노드, 왼쪽 자식노드, 오른쪽 자식노드를 저장함
• 부모를 향하는 포인터가 불필요한 응용에서는 부모노드를 저장하는 필드 생략가능

• 

 

 

 

 

 

 

 

 

 

 

 

트리 ADT  구현과 메쏘드

• 트리의 경우 자식노드의 수가 일정하지 않으므로 배열로 구현하는 것은 기억장소의 낭비 초래

연결리스트를 이용한 트리 구현1

• 각 노드는 원소, 부모노드, 자시노드들의 리스트를 저장함
• 각 노드의 세 가지 정보만 저장하는 대신 자식노드의 수가 많고 적음에 따라 리스트의 길이가 가변임

• 

 

 

 

 

 

 

 

 

 

 

 

연결리스트를 이용한 트리 구현2

• 각 노드는 원소 부모노드, 첫째 자식노드, 그리고 바로 아래 동생노드를 저장함
• 각 노드에 네 가지 정보를 저장함으로써 자식노드에 대한 가변길이 리스트를 사용하지 않음

• 

 

 

 

 

 

 

 

 

 

 

이진트리와 트리 성능 요약

작업	이진트리		트리
	배열	연결	연결
size, isEmpty	1	1	1
root, parent	1	1	1
children(v)	1	1	Cv
leftChild, rightChild, sibling	1	1	N/A
isInternal, isExternal, isRoot	1	1	1
setElement, swapElements	1	1	1

• 이진트리를 배열 또는 연결리스트로 구현할 경우 모든 기초 작업들은 O(1) 시간에 수행
• 트리의 경우 임의의 노드의 자식들을 반환하는 데 자식들의 수, Cv, 즉 l children(v) l에 비례하는 시간이 걸림 이를 제외한 기초 작업들은 O(1)시간에 수행
• 만약 트리가 비어있지 않도록 구현한다면 isEmpty는 항상 False를 반환할 것이므로 별 효용이 없는 메쏘드