Horowitz, Sahni and Anderson-Freed Computer Science Press 10장: 탐색 구조-1 C로 쓴 자료구조론 Horowitz, Sahni and Anderson-Freed Computer Science Press

최적 이진 탐색 트리 정의 탐색비용 예 탐색 비용을 최소로 하는 트리 for for do void do while if while void for(1), do(2), void(2), if(3), while(3) =11 if for(1), do(2), while(2), void(3), if(4)=12

확장 이진 트리 외부노드 이진트리에서 널 링크가 있는 부분에 사각형 노드를 추가함 탐색에 실패한 노드 for do void if while

경로 길이 외부 경로 길이(E) 내부 경로 길이(I) 루트로부터 각 외부노드까지의 경로 길이를 합한 것 루트로부터 각 내부노드까지의 경로 길이를 합한 것 I=0+1+1+2+3 =7 E=2+2+4+4+3+2=17 E=I+2n I의 최대값: 경사트리 =n(n-1)/2 I의 최소값: 완전이진트리 =O(n log n) do void for while if

이진 탐색 트리 총 비용 계산식 fi: failure node

이진 탐색 트리 예 (a1, a2, a3)=(do, if, while) pi=qj=1/7일 경우 cost(tree a)=cost(tree c)= cost(tree d)=15/7; cost(tree b)=13/7 p1,3=(.5, .1, .05) q0,3=(.15, .1, .05, .05) 일 경우 cost(tree a)=2.65;cost(tree b)=1.9;cost(tree c)=1.5; cost(tree d)=2.05 if do while do while if if while do do if while (b) (a) (c) (d)

최적 탐색 트리 결정의 계산식 가중치 비용 최소비용 ak L R cij=pk+cost(L)+cost(R)+ weight(L)+weight(R) cii=0 단, 최소값을 정하는 l이 루트

최적 탐색 트리의 계산 예(1) (a1, a2, a3 ,a4)=(do, for, void, while) p1,4=(3, 3, 1, 1) q0,4=(2, 3, 1, 1, 1) 일 경우 w01=p1+w00+w11=p1+q1+w00=3+3+2=8 c01=w01+min{c00+c11}=8+0=8 r01=1 w12=p2+w11+w22=p2+q2+w11=3+1+3=7 c12=w12+min{c11+c22}=7+0=7 r12=2 : w02=p2+w01+w22=p2+q2+w01=3+1+8=12 c02=w02+min{c00+c12 , c01+c22}=12+min{7,8}=19 r02=1

최적 탐색 트리의 계산 예(2) (do, for, void, while) W00=2 C00=0 R00=0 W11=3 C11=0

이진 탐색 트리의 균형 동적 테이블 관리를 위한 트리의 균형 균형트리 Jan부터 순서대로 삽입한 이진 트리 최악의 경우 Feb Jul May Apr Aug Dec Nov Oct Sep Jun Mar Jan Jan부터 순서대로 삽입한 이진 트리 Feb Jan Mar May Apr Aug Dec Jun Jul Sep Oct Nov Apr Aug Dec Feb 최악의 경우

AVL 트리 균형트리 정의 Adelson-Velskii, Landis가 1962년 제안 서브트리들의 높이가 균형을 이룸 동적검색 O(log n), 삽입삭제 O(log n) 정의 공백 트리는 높이 균형을 이룸 트리 T의 왼쪽과 오른쪽 서브트리 TL과 TR을 가진 이진 트리의 경우, 다음 조건을 만족하면 T는 높이 균형을 이루며, 그 역도 성립 TL과 TR은 높이 균형 |hL-hR| <= 1 (hL과 hR은 TL과 TR의 높이) 균형인수 BF(T) = hL-hR

AVL 트리 삽입 예(1) RR 회전 및 LL 회전 -2 RR회전 -1 -1 -2 +2 +1 LL회전 +2 +1 Mar May Mar Nov Nov +2 +1 May LL회전 May +2 Mar Nov Nov Aug +1 Aug Apr Mar Apr

AVL 트리 삽입 예(2) LR회전 및 RL회전 +2 -1 LR회전 -1 +1 +2 +1 -2 -1 RL회전 -1 +1 Mar May Nov -1 +2 Apr Aug +1 Jan Jan Mar May -1 Apr Aug Nov LR회전 Jan Mar May -2 +2 -1 Apr Aug +1 Nov Dec Feb Jul Jan Mar May +1 -1 Aug Dec Nov Feb Jul Apr RL회전

재균형 회전(1) LL 회전 및 RR 회전 LL RR AR BL BL BR BR AR BR AL AL BL BL BR +2 A B LL +1 B h+2 A h+2 AR h BL BL BR BR AR B -2 A A -1 B h+2 h+2 RR BR AL AL BL BL BR

재균형 회전(2) LR회전 종류 LR(a) LR(b) BL CL CR AR BL CL CR AR +2 A -1 B C C B C C B A LR(a) +2 A -1 B +1 C BL CL CR h h-1 AR h+2 C B -1 A BL CL CR AR h+2 LR(b)

재균형 회전(3) RL 회전도 LR회전과 대칭 LR(c) BL CL CR AR BL CL CR AR C +1 B A h+2 C +1 B A BL CL CR AR h+2 +2 A -1 B C BL CL CR h h-1 AR h+2 LR(c) RL 회전도 LR회전과 대칭

여러 구조들의 성능 비교 연산 순차리스트 연결리스트 AVL 트리 x 탐색 O(log n) O(n) k번째 항목 탐색 O(1) O(k) x 삭제 O(1) * k번째 항목 삭제 O(n-k) x 삽입 순차 출력 * 위치가 알려진 경우