[자료구조#7, 8] 트리 & 스레드의 트리

트리

분류

- 검색의 편리함

- 논리적 계층

- 계급적 특성

 

용어와 논리적 표현 방법

노드 : 트리의 항목/트리에 저장되는 데이터묶음

부모노드 - 자식노드 : 상하 계층 구조가 있고 직접적으로 연결된 노드로 상위계층의 부모 노드와 하위 계층의 자식 노드

루트노드 : 트리의 최상위 노드 (부모가 없는 노드)

서브트리 : 부모 노드를 삭제하면 생기는 트리들

리프 노드 : 트리의 맨 끝에 있으면서 자신의 서브트리를 갖지 않는 노드

 

진입/진출 차수

루트 노드 : 진입차수 = 0

루트를 제외한 모든 노드의 진입 차수 : 1

리프 노드 : 진출 차수 = 0

 

노드의 레벨 : 루트로부터 그 노드까지 이어진 선의 길이

트리의 높이 : 루트로부터 가장 멀리있는 노드까지 이어진 선의 길이에 1을 더한 값

 

 

 

이진 트리

모든 노드의 차수가 2 이하인 트리

컴퓨터 내부에서 구현하기도 효율적

개념적 접근으로 오른쪽/왼쪽으로 부르기도 함

 

포화 이진 트리 : 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

완전 이진 트리 : 0레벨부터 k-2 레벨까지 채우고 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트

 

배열을 이용한 이진 트리의 구현

트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적

트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐

 

이진 트리 연산

이진 트리의 순회 : 이진 트리의 각 노드를 빠짐없이 중복 없이 한번 씩 방문

전위 순회 : 루트 노드 - 왼쪽 자식노드 - 오른쪽 자식 노드

후위 순회 : 왼쪽 자식 노드 - 오른쪽 자식 노드 - 루트 노드

 

연결 리스트 연산을 사용함

 

일반 트리를 이진 트리로 변환

메모리 낭비를 줄이기 위해 이진 트리로 변환

---

스레드 트리의 정의

스레드 트리

- 주소값을 저장

 

"스레드" 라는 포인터를 추가하여 순회를 더 효율적으로

 

이진 트리의 노드 순회 : 전위 순회, 중위 순회, 후위 순회

이진 트리의 노드를 순회할 때 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야하는 번거로움이 발생

 

스레드 : 순회 방법에 따른 방문순서를 유지하는 포인터

 

스레드 트리의 구현

포인터 필드의 추가 : 스레드를 저장하는 포인터를 추가하는 것

오른쪽 스레드 : 정해진 순회 순서에 따른 그 노드의 후속 노드를 가르킴

왼쪽 스레드 : 그 노드의 선행 노드를 가르킴

 

노드의 빈 포인트 필드를 사용 : 노드에 사용하지 않는 포인터를 활용하는 방법, 추가 기억 장소를 사용 X

이진 트리의 포인터 갯수 2n

루트 노드를 제외한 각 노드 개수는 모두 진입차수가 1이 됨

루트 노드를 제외한 전체 노드 : n-1

태그 필드 : 서브 트리에 대한 포인터인지 구분하기 위해 필요

스택을 운영하지 않지만 추가 기억장소를 사용한다는 부담이 생김

오른쪽 스레드를 따라가면 중위 순회를 할 수 있음

 

스레드 트리 순회 삽입 삭제