[자료구조] Chap8~9 트리, 트리 탐색

Chap8 트리

 

트리

• 삽입삭제가 편함
• 이진검색의 장점을 이용해 빠른 검색 가능
• 루트의 레벨 = 1
• 차수 : 노드의 부속트리 개수. 리프노드는 차수가 0임
• 부모, 자식, 조상, 자손 관계 등..

 

트리 저장(구현)방법

1. n-링크표현법
   • 모든 노드에 무조건 n개의 링크를 두고 각 자식노드의 링크를 저장함(남는 공간 있음)
2. 왼쪽자식노드-오늘쪽형제노드 표현법
   • 모든 노드에 링크 두개씩. - 효율적
   • 왼쪽링크에는 첫번째 자식노드, 오른쪽 링크에는 자신의 형제노드를 연결함
   • 차수가 n인 어떤 트리라도 이 방법을 이용하면 이진트리형태로 저장해 낭비되는 공간을 줄일 수 있음(간선을 다시 그리고 시계방향으로 45도 정도 돌림)

이진트리

• 자식노드의 수가 2개 이하(0~2개)인 트리
• 자식노드에 순서가 있음 - 똑같이 자식노드가 1개라도 왼쪽/오른쪽 방향이 다르면 다른 트리로 생각함.
• 최대 레벨이 i인 트리의 최대 노드 수는 2^i - 1
• 이진트리의 전체 노드 수, 리프노드 수, 차수가 1인 노드 수, 차수가 2인 노드 수 n, n0, n1, n2에 대해 다음 식이 성립한다.(n=n0+n1+n2)
  • n0 = n2+1 
• 이진트리 종류
  • skewed 이진트리 : 노드가 왼/오 한 방향으로만 있음
  • 포화 이진트리 : 노드가 꽉참
  • 완전 이진트리 : 자식노드가 위, 왼쪽부터 차있는 이진트리. 리프노드 직전 레벨까지는 노드가 꽉 차있음. 노드에 번호를 매기면 빠지는 번호가 없음. (차수가 1인노드는 있을 수 있음. 하나인 자식노드가 왼쪽이어야 하겠지)
• 이진트리의 저장 방법
  1. 배열 
     • 노드를 레벨순으로 저장함. 
     • 배열 0번째부터 시작한다고 하면, 현재 노드가 배열의 i번째에 저장되어있을 때 부모노드의 위치는 (i-1)/2 의 몫 - 암기!!!!
     • 왼쪽 자식노드 : i*2+1, 오른쪽 자식 노드 : i*2+2
     • m레벨의 k번째 노드 : (2^(m-1)-1) + (k-1)
     • 완전이진트리 저장에는 효과적이나 skewed와 같이 빈공간이 많으면 비효율적
  2. 연결리스트
     • 한 노드를 왼쪽 자식에 대한 포인터, 데이터, 오른쪽 자식에 대한 포인터로 구성함. (부모노드 포인터도 추가하는 경우도 간혹 있음) 
     • 노드 수 만큼의 공간을 사용. 노드 수가 변해도 공간 조정가능. 배열보다는 관리가 복잡

 

Chap 9 트리 탐색

 

[1 이진트리 탐색 알고리즘]

탐색 방법 : 왼쪽자식노드(서브트리)L, 오른쪽R, 루트노드V라 하면 항상 L->R 순이고 V를 언제 방문하냐에 따른 방법들

1. 전위 탐색
   • V L R
   • 재귀호출 방법으로 V를 탐색하고 -> L을 재귀호출하고 -> R을 재귀호출 하는 식으로 코드 구성함. 나머지도 순서만 바꾸면 됨
2. 중위 탐색
   • L V R
3. 후위 탐색
   • L R V
4. 레벨 탐색
   • 레벨순으로 탐색
   • 루트를 방문하고 자식노드들을 왼->오 순으로 기억해둠(큐에 저장). 다음 레벨로 넘어가려면 가장 예전에 저장했던 노드부터 기억에서 꺼내 방문. 방문시마다 왼->오 순으로 기억해둠. 반복..

알고리즘 코드 . . . .

 

 

[2 스레드 이진트리]

• 탐색이 쉽도록 노드의 빈 링크에 다음 방문할 곳이나 직전에 방문한 곳의 주소값을 저장해둠(스레드)
• 링크에 저장된 값이 노드를 가리키는 포인터인지 쓰레드인지 구분하기위해 왼/오 링크의 값이 스레드인지 알려주는 새 필드를 2개 추가해서 true/false를 표시해야 함
• head node : 트리의 가장 오른쪽 노드의 오른쪽 링크와 가장 왼쪽 노드의 왼쪽 노드가 가리키는 곳. 헤드노드의 왼쪽 링크는 루트노드를, 오른쪽 링크는 스스로를 가리킴. 데이터값은 비어있음. 트리가 비어있는 경우 헤드노드만 남아있게 됨
• 알고리즘 코드 . . .

 

[3 이진트리관련 알고리즘]

1. 이진트리 복사
   •  
2. 이진트리 동등비교
   • 이진트리의 모든 노드에 대해 데이터값(키값), 왼쪽/오른쪽 자식이 같으면 동등함