트리와 이진트리

목차

1. 트리
- 개념
- 용어정리
- 트리의 표현
- 저장방법
- 구현
- 포인터에 의한 트리

2. 이진트리
- 개념
- 특성
- 표현
- 순회
- 저장
- 완전 이진 트리와 경사 트리

3. 이진 탐색트리

4. 쓰레드 이진트리

본문내용

어진 키 값이 같으면 검색은 성공
② 주어진 키 값 > 노드의 키 값 : 오른쪽 서브트리로 이동한 후, ①의 과정을 수행
③ 주어진 키 값 < 노드의 키 값 : 왼쪽 서브트리로 이동한 후, ①의 과정을 수행
④ 노드의 키 값 = NIL이면 검색은 실패
(EX1) 이진 검색트리에서 n = 7일 때 "키 값 17"을 가진 레코드를 찾는 과정에서
① 균형 트리로 구성했을 때의 검색순서와 평균 탐색 길이,
② 비균형트리로 구성했을 때의 검색순서와 평균 탐색 길이를 구하시오.
풀이)
(1) 입력 순서 : 13, 6, 18, 3, 8, 25, 17일 때
① 검색 순서 : (a)와 같은 균형 트리로 구성을 한 후 검색을 하면
(b)와 같은 순서(11→18→17)로 검색 됨
② 평균 검색 길이 : ((1 * 1) + (2 * 2) + (3 * 4)) / 7 = 2.4
(2) 입력 순서 : 3, 18, 8, 17, 6, 25, 13
① 검색 순서 : (c)와 같은 비균형 트리로 구성을 한 후 검색을 하면
(d)와 같은 순서 ( 3→18→8→17)로 검색됨
② 평균 검색 길이 : ((1 * 1) + (2 * 1) + (3 * 2) + (4 * 2) + (5 * 1)) / 7 = 3.7
※ 이진 검색트리에서 특정 노드를 찾을 때의 특성
① 찾으려는 레코드가 트리의 Root로부터 멀어질수록 그 레코드를 찾는 시간이 많이 걸린다.
② 검색시간을 단축하기 위해서는 이진 탐색 트리의 형태 →정이진트리(full binary tree) 또는 이와
유사한 이진 트리로 만들어야 한다.
그러므로 AVL트리, 또는 2-3-4트리 등의 균형있는 이진 탐색 트리가 사용된다.
4. 쓰레드 이진 트리(thread binary tree)
(1) 정의
☞ n개의 노드를 가진 이진 트리의 링크 표현에서 거의 절반이 널 링크를 가지게 되므로 이러한 널 링크들을
트리에서 처 높은 위치의 노드들을 지시하는 특별한 포인터로 대체하게 되는 트리를 말한다.
(2) n개 노드를 가진 이진 트리의 링크 표현
이진 트리에는 총 2n개 링크 종에 n+1개의 널 링크가 있다.
(3)스레드
+ 널 링크를 이용하는 방법이 Perlis, Thornton 에 의해 고안 되었다.
+ 널 링크를 다른 노드를 가리키는 포인터로 대체한다.
+ 스레드를 구성하기 위한 규칙 - 어떤 노드의 Right_Child가 널이면, 그 트리의
+ 중위 순회시 그 노드 다음에 방문할 노드를 가리키는 포인터로 사용한다.
- 어떤 노드의 Left_Child가 널이면, 중위 순회시 그노드 바로 전에 방문한 노드를 가리키는 포인
터로 사용한다.
- 장점으로는 스택의 도움 없이 트리를 순회할 수 있다.
- 단점으로는 실제 포인터와 스레드를 구별 할 수 없다.
(4) 스레드 이진 트리의 노드 구조 표현
메모리 표현에서 스레드와 정상 포인터는 구별되어야 한다.
※ 스레드의 데이터 구조는 아래의 그림과 같다.
L 비트 = 0 : LLINK가 스레드 포인터
L 비트 = 1 : LLINK가 정상적인 포인터
R 비트 = 0 : RLINK가 스레드 포인터
R 비트 = 1 : RLINK 가 정상적인 포인터
※ 스레드 이진 트리의 표현원칙은 다음과 같다.
+ 널 포인터가 좌측 포인터이면 그 노드 직전에 검사할 노드를 가리키도록 포인터 값을 조정한다.
+ 널 포인터가 우측 포인터이면 그 노드 다음에 검사될 노드를 가리키도록 포인터 값을 조정한다.
5. 힙
(1) 정의
☞ 최대 힙 - 최대 힙은 최대 트리이면서, 완전 이진 트리이다. 최대 트리는 각 노드의 키 값이
그 자식의 키 값 보다 작지 않은 트리를 말한다.
☞ 최소 힙 - 최소 힙은 최소 트리 이고 최소 각 노드의 키 값이 자식의 키 값보다 크지 않은 트리이다.
(2)기본연산 - 공백 힙의 생성, 힙에 새로운 원소의 삽입, 힙에서 가장 큰 원소의 삭제
(3)최대 힙에서의 삽입
+ 완전 이진 트리의 높이 = [log2(n+1)]
+ 삽입 함수의 연산 시간 = O(log2n)
(4)최대 힙에서의 삭제
+ 힙의 루트(최대 값) 삭제 후, 힙이 되도록 재구성 한다.
+ 힙의 높이는 [log2(n+1)]이고, 삭제의 복잡도는 O(log2n)이다.
6. 포리스트
(1) 정의
☞ 포리스트는 n(>=0)개의 분리 트리들의 집합을 말한다.
(2) 포리스트이 이진 트리 변환
포리스트 내의 각 트리를 이진 트리로 변환한다.
(3) 포리스트 순회
- 포리스트의 전위 순회
: F가 공백이면 Return 한다.
: F의 첫 트리의 루트를 반문한다.
: 첫 트리의 서브 트리들을 트리 전위로 순회한다.
: F의 남은 트리들을 트리 전위로 순회한다.
- 포리스트의 준위 순회
: F가 공백이면 Return 한다.
: F의 첫 트리의 서브 트리를 트리 주위 순회한다.
: 첫 트리의 루트를 방문한다.
: F의 남은 트리들을 트리 주위로 순회한다.
- 포리스트의 후위 순회
: F가 공백이면 return 한다.
: F의 첫 트리의 서브 트리를 트리 후위 순회한다.
: F의 남은 트리들을 트리 후위로 순회한다.
: F의 첫 트리의 루트를 방문한다.
7.높이 균형 이진 트리
(1) 정의
☞ AVL은 서브 트리들의 높이가 [ hL-hR] <= 1이 되도록 균형을 이루어 탐색 시간을 줄이는 이진
트리를 말한다.
※ 참고자료..
+ http://sanhak.yeojoo.ac.kr/online/hkh/onch13.html#6.3 --> 이진탐색트리
+ http://210.95.92.1/tc/%C0%FC%BB%EA%B0%FA/%C3%D6%C0%B1%C8%F1/%C0%DA%B7%E1/%C0
%DA%B7%E1%B1%B8%C1%B6.htm --> 트리의개념, 트리의 저장방법,,이진트리
+ http://www.kiscos.net/kiscom/study/datastructure/5_5.html --> 스레드 이진트리
+ http://pllab.kangwon.ac.kr/lecture/ds_website/chapt-41.htm --> 트리의정의......
+ http://my.netian.com/~inshall/study/database/db_9.htm --> 트리의정의

키워드

트리,   이진트리,   개념,   용어정리,   표현