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

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

반응형

Chap8 트리

트리

삽입삭제가 편함

이진검색의 장점을 이용해 빠른 검색 가능

루트의 레벨 = 1

차수 : 노드의 부속트리 개수. 리프노드는 차수가 0임

부모, 자식, 조상, 자손 관계 등..

트리 저장(구현)방법

n-링크표현법 모든 노드에 무조건 n개의 링크를 두고 각 자식노드의 링크를 저장함(남는 공간 있음) 왼쪽자식노드-오늘쪽형제노드 표현법 모든 노드에 링크 두개씩. - 효율적

왼쪽링크에는 첫번째 자식노드, 오른쪽 링크에는 자신의 형제노드를 연결함

차수가 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인노드는 있을 수 있음. 하나인 자식노드가 왼쪽이어야 하겠지)

이진트리의 저장 방법 배열 노드를 레벨순으로 저장함. 배열 0번째부터 시작한다고 하면, 현재 노드가 배열의 i번째에 저장되어있을 때 부모노드의 위치는 (i-1)/2 의 몫 - 암기!!!! 왼쪽 자식노드 : i*2+1 , 오른쪽 자식 노드 : i*2+2 m레벨의 k번째 노드 : (2^(m-1)-1) + (k-1) 완전이진트리 저장에는 효과적이나 skewed와 같이 빈공간이 많으면 비효율적 연결리스트 한 노드를 왼쪽 자식에 대한 포인터, 데이터, 오늘쪽 자식에 대한 포인터로 구성함. (부모노드 포인터도 추가하는 경우도 간혹 있음) 노드 수 만큼의 공간을 사용. 노드 수가 변해도 공간 조정가능. 배열보다는 관리가 복잡

Chap 9 트리 탐색

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

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

전위 탐색 V L R

재귀호출 방법으로 V를 탐색하고 -> L을 재귀호출하고 -> R을 재귀호출 하는 식으로 코드 구성함. 나머지도 순서만 바꾸면 됨 중위 탐색 L V R 후위 탐색 L R V 레벨 탐색 레벨순으로 탐색

루트를 방문하고 자식노드들을 왼->오 순으로 기억해둠(큐에 저장). 다음 레벨로 넘어가려면 가장 예전에 저장했던 노드부터 기억에서 꺼내 방문. 방문시마다 왼->오 순으로 기억해둠. 반복..

알고리즘 코드 . . . .

[2 스레드 이진트리]

탐색이 쉽도록 노드의 빈 링크에 다음 방문할 곳이나 직전에 방문한 곳의 주소값을 저장해둠(스레드)

링크에 저장된 값이 노드를 가리키는 포인터인지 쓰레드인지 구분하기위해 왼/오 링크의 값이 스레드인지 알려주는 새 필드를 2개 추가해서 true/false를 표시해야 함

head node : 트리의 가장 오른쪽 노드의 오른쪽 링크와 가장 왼쪽 노드의 왼쪽 노드가 가리키는 곳. 헤드노드의 왼쪽 링크는 루트노드를, 오른쪽 링크는 스스로를 가리킴. 데이터값은 비어있음. 트리가 비어있는 경우 헤드노드만 남아있게 됨

알고리즘 코드 . . .

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

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

반응형

from http://onedaythreecoding.tistory.com/90 by ccl(A) rewrite - 2021-12-13 00:00:39