제 1 장 최적이원탐색트리 Copyright 27 DBLAB, Seoul National University
최적이원탐색트리 (1/11) 개요 정적원소들의집합에대한이원탐색트리구조 삽입이나삭제는하지않고탐색만수행 정렬된리스트 함수 Get( 프로그램 5.19 참고 ) 이용 비용측정방법 함수 Get 이용 for 루프를 l 번반복 1 5 15 리스트 (5,1,15) 에서의이원탐색에해당되는이원탐색트리 Copyright 27 DBLAB, Seoul National University 2
최적이원탐색트리 (2/11) 예제 1.1 1 1 5 25 5 2 2 15 25 15 (a) 두이원탐색트리 (b) 최악의경우탐색시간 : (a) 4 번, (b) 3 번 성공적인탐색에필요한평균 : (a) 2.4 번, (b) 2.2 번 5,1,15,2,25 가각각.3,.3,.5,.5,.3 의확률로탐색 : (a) 1.85, (b) 2.5 Copyright 27 DBLAB, Seoul National University 3
최적이원탐색트리 (3/11) 이원탐색트리의평가 특별한사각형노드 (square node) 추가시유용 1 1 5 25 5 2 2 15 25 15 (a) 확장이진트리 외부노드 ( 실패노드 ) : n+1 개의사각노드 내부노드 : 원래노드 (b) Copyright 27 DBLAB, Seoul National University 4
최적이원탐색트리 (4/11) 외부경로길이 (external path length) 루트로부터각외부노드경로길이의합 내부경로길이 (internal path length) 루트로부터각내부노드경로길이의합 1 5 25 내부경로길이 (I)=+1+1+2+3=7 외부경로길이 (E)=2+2+4+4+3+2=17 2 15 I 와 E 의관례 (n 개의내부노드를가질경우 ) E=I+2n E 가최고일때 I 도최고 Copyright 27 DBLAB, Seoul National University 5
최적이원탐색트리 (5/11) I 의최소값 최악의경우 : 트리가편향될때 I n j 일반적인경우 i n( n 완전이진트리일경우 1 1) / 2 + 2 1 + 4 2 + 8 3 + + i [log i O( nlog2 1 i n 2 n ) Copyright 27 DBLAB, Seoul National University 6
최적이원탐색트리 (6/11) 정적원소집합을이원탐색트리로표현 탐색이성공적일때비용 pi level( a 1 i n 탐색이실패적일때비용 q i ( level( 실패노드i) 1) 1 i n 이원탐색트리의총비용 p level( a ) q (level( 실패노드i) 1) 1 i n i 최적이원탐색트리의성립 p i qi 1 1 i n 1 i n i i ) (a i 를탐색할확률이 p i 일경우 ) ( 탐색중인원소가 Ei 에있을확률이 qi 일경우 ) 1 i n i Copyright 27 DBLAB, Seoul National University 7
최적이원탐색트리 (7/11) 예제 1.2 15 1 5 15 5 1 5 15 1 5 15 5 15 1 1 (a) (b) (c) (d) (e) 3 개의원소를가진이원탐색트리 똑같은확률 p i =q i =1/7 일경우 cost(tree a) = 15/7 ; cost(tree b) = 13/7 cost(tree c) = 15/7 ; cost(tree d) = 15/7 ; cost(tree e) = 15/7 p 1 =.5, p 2 =.1, p 3 =.5, q =.15, q 1 =.1, q 2 =.5, q 3 =.5 cost(tree a) = 2.65 ; cost(tree b) = 1.9 cost(tree c) = 1.5 ; cost(tree d) = 2.5 ; cost(tree e) = 1.6 Copyright 27 DBLAB, Seoul National University 8
최적이원탐색트리 (8/11) 최적이원탐색트리의성질 a 1 <a 2 <.<a n, n 개의키 T ij 가 a i+1,.,a j, i<j 가중치 : W ij = q i + 만약 T ij 가 a i+1,.,a j 와 r ij =k 에대한최적이원탐색트리라면 k 는 i<k j 를만족 비용 : c ij = p k + cost(l) + cost(r) + weight(l) + weight(r) = p k + c i,k-1 + c kj + w i,k-1 + w kj = w ij + c i,k-1 + c kj T ij 최적 r ij =k일때 w ij + c i,k-1 + c kj = {w ij + c i,l-1 + c lj } min min i 1 j c i,k-1 + c kj = {c i,l-1 + c lj } i 1 j j ( qk p k i 1 k ) L Weight(T i,k-1 ) = w i,k-1 ak R 최적이원탐색트리 T ij Weight(T kj ) = w kj Copyright 27 DBLAB, Seoul National University 9
최적이원탐색트리 (9/11) 예제 1.3 n=4, (a 1, a 2, a 3, a 4 ) = (1,15,2,25) (p 1, p 2, p 3, p 4 ) = (3, 3, 1, 1), (q, q 1, q 2, q 3, q 4 ) = (2, 3, 1, 1, 1) W 1 = p 1 + w + w 11 = p 1 + q 1 + w = 8 c 1 = w 1 + min {c + c 11 }= 8 r 1 = 1 W 12 = p 2 + w 11 + w 22 = p 2 + q 2 + w 11 = 7 c 12 = w 12 + min {c 11 + c 22 }= 7 r 12 = 2 W 23 = p 3 + w 22 + w 33 = p 3 + q 3 + w 22 = 3 c 23 = w 23 + min {c 22 + c 33 }= 3 r 23 = 3 W 34 = p 4 + w 33 + w 44 = p 4 + q 4 + w 33 = 3 c 34 = w 34 + min {c 33 + c 44 }= 3 r 34 = 4 Copyright 27 DBLAB, Seoul National University 1
최적이원탐색트리 (1/11) 1 2 3 4 1 2 3 4 W = 2 C = R = W 1 = 8 C 1 = 8 R 1 = 1 W 2 =12 C 2 =19 R 2 = 1 W 3 =14 C 3 =25 R 3 = 2 W 4 =16 C 4 =32 R 4 = 2 W 11 = 3 C 11 = R 11 = W 12 = 7 C 12 = 7 R 12 = 2 W 13 = 9 C 13 =12 R 13 = 2 W 14 =11 C 14 =19 R 14 = 2 W 22 = 1 C 22 = R 22 = W 23 = 3 C 23 = 3 R 23 = 3 W 24 = 5 C 24 = 8 R 24 = 3 W 33 = 1 C 33 = R 33 = W 34 = 3 C 34 = 3 R 34 = 4 C 4 와 r 4 의계산 W 44 = 1 C 44 = R 44 = 계산은 행부터 4 행까지순서로수행됨 Copyright 27 DBLAB, Seoul National University 11
최적이원탐색트리 (11/11) 15 1 2 25 예제 1.3 에대한최적이원탐색트리 c 와 r 값을구하는함수의복잡도 C ij 는 (j-i)= 1, 2,., n 순서로계산 j-i=m일때 n-m+1개의 C ij 계산 j-i=m인모든 c ij 의총연산시간 : O(nm-m 2 ) 총연산시간 : n m 1 ( nm m 2 ) O( n 3 ) Copyright 27 DBLAB, Seoul National University 12
AVL 트리 (1/3) 어떤원소를찾기위한최대비교횟수 JAN JUL FEB MAR FEB MAY APR JUN MAY AUG JUL DEC 3.5 (a) 1 년 12 달에대한이원탐색트리 APR AUG DEC SEP AUG JAN MAR OCT OCT APR DEC JUN NOV SEP NOV (b) 1 년 12 달에대한균형트리 3.1 FEB JAN JUL 6.5 (c) 성능이저하된이원탐색트리 JUN MAR MAY NOV OCT Copyright 27 DBLAB, Seoul National University 13
AVL 트리 (2/3) 정의 공백트리는높이균형을이룬다 T L 과 T R 을가진공백이아닌이진트리라할때 T L 과 T R 이높이균형을이룬다 h L h R 1(h L 과 h R ) 은각각 T L T R 의높이 T 는높이균형을이루며그역도성립함 앞장에서 (a), (c) 는높이균형을이루지못하는반면 (b) 는높이균형을이룸 Copyright 27 DBLAB, Seoul National University 14
AVL 트리 (3/3) 균형인수 (balance factor) 왼쪽, 오른쪽서브트리사이의높이차 BF(T) = hl hr AVL 트리의어떠한노드 T 에대해서도 BF(T)= -1,, 1 삽입된노드 Y 에가장가까우면서균형인수가 ±2 인조상노드 A 에대한회전성질 LL: 새노드 Y 는 A 의왼쪽서브트리의왼쪽서브트리에삽입 LR: Y 는 A 의왼쪽서브트리의오른쪽서브트리에삽입 RR: Y 는 A 의오른쪽서브트리의오른쪽서브트리에삽입 RL: Y 는 A 의오른쪽서브트리의왼쪽서비트리에삽입 단일회전 (Single rotation) : LL 과 RR 불균형을바로잡는변환 이중회전 (Double rotation) : LR 과 RL 불균형을바로잡는변환 Copyright 27 DBLAB, Seoul National University 15
LL 회전 삽입전 B L 에삽입한뒤 LL 회전뒤 균형인수는노드안에있음 서브트리높이는서브트리이름밑에있음 Copyright 27 DBLAB, Seoul National University 16
LR 회전 삽입전 B R 에삽입한뒤 LR 회전뒤 b = bf(b) = bf(a) = 회전뒤 b = 1 bf(b) = and bf(a) = -1 회전뒤 b = -1 bf(b) = 1 and bf(a) = 회전뒤 Copyright 27 DBLAB, Seoul National University 17
트리확장및균형유지과정 (1/5) 삽입순서 MAR, MAY, NOV, AUG, APR, JAN, DEC, JUL, FEB, JUN OCT, SEP 순 -1 MAR MAR MAY (a) 삽입 MARCH (b) 삽입 MAY -2 MAR -1 MAY NOV RR MAR MAY NOV (c) 삽입 NOV Copyright 27 DBLAB, Seoul National University 18
트리확장및균형유지과정 (2/5) AUG +1 MAR +1 MAY NOV (d) 삽입 AUGUST APR +1 AUG +2 MAR +2 MAY NOV LL APR AUG +1 MAY MAR NOV (e) 삽입 APRIL Copyright 27 DBLAB, Seoul National University 19
트리확장및균형유지과정 (3/5) APR -1 AUG JAN +2 MAY +1 MAR NOV LR APR AUG MAR JAN -1 MAY NOV (e) 삽입 JANUARY APR -1 AUG DEC +1 MAR +1 JAN -1 MAY NOV APR -1 AUG DEC +1 MAR JAN -1 MAY JUL NOV (g) 삽입 DECEMBER (h) 삽입 JULY Copyright 27 DBLAB, Seoul National University 2
트리확장및균형유지과정 (4/5) ARP APR +1 AUG -2 AUG +2 MAR +1 JAN -1 DEC FEB -1 DEC FEB +2 MAR -1 JAN -1 MAY JUL -1 MAY -1 JUL JUN NOV RL ARP (i) 삽입 FEBRUARY NOV LR (j) 삽입 JUNE +1 AUG DEC FEB +2 MAR JAN +1 JAN DEC +1-1 AUG FEB ARP -1 MAY NOV Copyright 27 DBLAB, Seoul National University 21 JUL MAR -1 JUL -1 MAY JUN NOV
트리확장및균형유지과정 (5/5) -1 +1 JAN -1 DEC +1-1 MAR -1-2 AUG FEB JUL MAY -1 ARP JUN NOV OCT RR (k) 삽입 OCTOBER +1 JAN DEC MAR +1-1 AUG FEB JUL NOV ARP JUN MAY OCT +1 DEC +1 AUG FEB ARP -1 JAN -1 JUL JUN -1 MAR (l) 삽입 SEPTEMBER -1 NOV -1 MAY OCT SEP Copyright 27 DBLAB, Seoul National University 22
AVL 트리에서의삽입 여러구조들의비교 연산순차리스트연결리스트 AVL 트리 키가 k 인원소탐색 O(log n) O(n) O(log n) j 번째원소탐색 O(1) O(j) O(log n) 키가 k 인원소삭제 O(n) O(l) 1 O(log n) j 번째원소삭제 O(n - j) O(j) O(log n) 삽입 O(n) O(l) 2 O(log n) 순서대로출력 O(n) O(n) O(n) 1. K 의위치가알려진이중연결리스트 2. 삽입할위치가알려진경우 Copyright 27 DBLAB, Seoul National University 23
레드 - 블랙트리 (1/14) 정의 RB1. 루트와모든외부노드들은컬러가블랙이다. RB2. 루트에서외부노드로의경로는두개의연속적인레드노드를가질수없다. RB3. 루트에서외부노드로의모든경로들에있는블랙노드의수는동일하다. RB1'. 내부노드로부터외부노드로의포인터는블랙이다. RB2'. 루트에서외부노드로의경로는두개의연속적인레드포인터를가질수없다. RB3'. 루트에서외부노드로의모든경들에있는블랙포인터의수는동일하다. Copyright 27 DBLAB, Seoul National University 24
레드 - 블랙트리 (2/14) 65 5 8 1 6 7 5 62 레드 - 블랙트리 블랙포인터 레드포인터 Copyright 27 DBLAB, Seoul National University 25
레드 - 블랙트리 (3/14) 보조정리 1.1 루트로부터외부노드로의 2 개의경로 P, Q 가있을때 length(p) 2length(Q) 증명 임의레드 - 블랙트리에서루트의경로를 r 로둠. RB1' 로부터루트에서외부노드로의경로상에있는마지막포인터는블랙 RB2' 로부터 2 개의연속적인레드포인터를갖는경로미존재 각레드포인터뒤에는항상블랙포인터가와야함. 결과적으로루트에서외부노드로의각경로는 r, 2r 사이에서포인터를갖게됨. 따라서 length(p) 2length(Q) 임. Copyright 27 DBLAB, Seoul National University 26
레드 - 블랙트리 (4/14) 보조정리 1.2 레드 - 블랙트리높이 h, 트리내부노드수 n, 랭크 r 이면 (a) h 2r (b) n 2 r 1 (c) h 2log 2 (n+1) 증명 보조정리 1.1 에서 length > 2r 은존재하지않음. 따라서 h 2r 레벨 1 에서 r 까지외부노드가없고, 이러한레벨은 2 r -1 개의내부노드가있음. 따라서 2 r -1 은내부노드의최소한의수가됨. (b) 로부터 h 2log 2 (n+1) Copyright 27 DBLAB, Seoul National University 27
레드 - 블랙트리 (5/14) 레드 - 블랙트리의표현 구현에있어외부노드를표현하기위해물리적노드보다널포인터이용 노드의컬러를저장하기위해노드당 1bit 필요 포인터의컬러를저장하기위해노드당 2bit 필요 레드 - 블랙트리에서의탐색 일반적으로이원탐색트리의탐색에서사용하는 알고리즘을이용하여탐색 Copyright 27 DBLAB, Seoul National University 28
레드 - 블랙트리 (6/14) 레드 - 블랙트리로의삽입 불균형타입 LLb : pu 가 gu 의왼쪽자식이고 u 는 pu 의왼쪽자식이며, gu 의다른자식이블랙인경우 LLr : pu 가 gu 의왼쪽자식이고 u 는 pu 의왼쪽자식이며, gu 의다른자식이레드인경우 LRb : pu 가 gu 의왼쪽자식이고 u 는 pu 의오른쪽자식이며, gu 의다른자식이블랙인경우 LRr : pu 가 gu 의왼쪽자식이고 u 는 pu 의오른쪽자식이며, gu 의다른자식이레드인경우 위와마찬가지로 RRb, RRr, RLb, RLr 이있다. 불균형타입 XYr 는컬러에의해변경되지만, XYb 은회전이필요함. Copyright 27 DBLAB, Seoul National University 29
레드 - 블랙트리 (7/14) gu gu pu gur pu gur u pur u pur ul ur ul ur (a) LLr 불균형 (b) LLr 컬러변화뒤 gu gu pu gur pu gur pul u pul u ul ur (c) LRr 불균형 ul ur (d) LRr 컬러변화뒤 Copyright 27 DBLAB, Seoul National University 3
레드 - 블랙트리 (8/14) gu pu pu gur pul gu pul pur pur gur (a) LLb 불균형 (b) LLb 회전뒤 gu u pu gur pu gu pul u pul ul ur gur ul ur (c) LRb 불균형 (d) LRb 회전뒤 Copyright 27 DBLAB, Seoul National University 31
레드 - 블랙트리 (9/14) 예제 1.4 5 1 8 5 1 8 9 7 9 (a) 초기 (b) 7 을삽입 5 pu 5 gu 1 8 1 8 u pu 7 9 7 9 u 6 6 (c) 6 을삽입 (d) LLr 컬러변환 Copyright 27 DBLAB, Seoul National University 32
레드 - 블랙트리 (1/14) 5 5 1 8 1 8 gu 7 9 65 9 pu 6 6 7 65 u (e) 65 삽입 (f) LRb 회전 1 5 8 1 gu 5 8 pu gu 65 9 u 65 9 pu 6 7 6 7 u 62 62 (g) 62 삽입 (g) LRr 컬러변경 Copyright 27 DBLAB, Seoul National University 33
레드 - 블랙트리 (11/14) 65 5 8 1 6 7 9 62 (i) RLb 회전 Copyright 27 DBLAB, Seoul National University 34
레드 - 블랙트리 (12/14) 레드 - 블랙트리에조인 경우 1 A 와 B 가같은랭크를갖는다면 X, leftchild, rightchild B 의쌍을갖는새로운 root 를생성함으로써 C 가만들어진다고하자 C 의랭크는 A 와 B 의랭크보다하나높다 경우 2 rank(a) > rank(b) 를갖는다면 A 에서부터 B 와같은랭크를갖는 첫번째노드 Y 까지 rightchild 포인터를따라간다. p(y) 가 Y 의부모이면 rank(p(y)) = rank(y) + 1 P(Y) 에서 Y 로의포인터는블랙포인터 x, leftchild, Y, rightchild, B 의쌍을갖는새로운노드 Z 생성 경우 3 rank(a) < rank(b), 경우 2 와비슷 Copyright 27 DBLAB, Seoul National University 35
레드 - 블랙트리 (13/14) 3 원조인연산의분석 기술된함수가정확한지에대해서쉽게알수있다. 경우 1 은 O(1) 의시간이걸리고 경우 2, 3 은 O( rank(a) rank(b) ) 이걸린다 따라서 3 원조인은 O(log n) 의시간에수행될수있으며이때 n 은조인되고있는두트리의노드수를의미 레드 - 블랙트리의분할 단계 1 키값이 i 인원소를포함하고있는노드 P 를찾기위해 A 를탐색 그원소를참조인자 (parameter) x 에복사 B 와 C 를 P 의왼쪽과오른쪽서브트리가되도록초기화 단계 2 for (Q = parameter(p); Q; P = Q, Q = parent(q)) { if(p == Q leftchild) C.ThreeWayJoin(C,Q data, Q rightchild) else B.ThreeWayjoin(Q leftchild, Q data, B); } Copyright 27 DBLAB, Seoul National University 36
레드 - 블랙트리 (14/14) 분할연산의분석 분할되지않은트리에서노드 X 의랭크를 r(x) 라하면 R(Q) max{r(b), r(c)} 정의로부터 r(q )=r(q)+1 이고 R(B ) r(b)+1 이고 r(c ) r(c)+1 이므로 Q 가블랙자식 P 를가진노드를가리킬때 R(q )=r(q)+1 max{r(b), r(c)}+1 max{r(b ),r(c )} 성립 Q 가블랙자식을가진한노드를가리킬때시작부터 Q 가이노드에도달할때까지분할알고리즘 2 단계에서수행되는모든작업이 O(r(B)+r(C)+r(Q)) 를알수있음 R(Q) max{r(b), r(c)} 이기때문에단계 2 에서이루어진모든작업은 O(r(Q)) 이다. 요구되는시간은 O(log n) 임을알수있음 Copyright 27 DBLAB, Seoul National University 37
상향식스플레이트리 (1/8) 상향식스플레이트리 (bottom-up splay tree) 이원탐색트리와같은방식으로탐색, 삽입, 삭제, 조인연산이이루어지며, 다른것은연산이수행된후스플레이 (splay) 가실행됨 시작노드는다음과같이결정 탐색 : 스플레이를찾고자하는원소를포함하는노드로부터시작 삽입 : 스플레이에대한시작노드는새로삽입된노드 삭제 : 물리적으로삭제된노드의부모노드가스플레이의 시작노드가됨. 3 원조인 : 어떤스플레이도발생하지않음 분할 : 키 i 를분할한다고가정. 키 i 를포함하고있는노드에 대해먼저스플레이를수행한뒤에트리분할 Copyright 27 DBLAB, Seoul National University 38
상향식스플레이트리 (2/8) 단계정의 q를스플레이가수행되고있는노드라가정 초기에 q는스플레이가시작하는노드 만일 q가 이거나루트이면스플레이종료 만일 q가부모 p는있지만조부모가없는경우회전이수행되고스플레이가종료 만일 q가부모 p와조부모 gp를갖고있다면회전은 LL(p는 gp의왼쪽자식이고 q는 p의왼쪽자식 ) LR(p는 gp의왼쪽자식이고 q는 p의오른쪽자식 ) RR(p는 gp의오른쪽자식이고 q는 p의오른쪽자식 RL(p는 gp의오른쪽자식이고 q는 p의왼쪽자식 ) 분류되다. Copyright 27 DBLAB, Seoul National University 39
상향식스플레이트리 (3/8) p q a q p c gp b c a,b,c는서브트리 q가오른쪽자식이고조부모가없을때의회전 a q gp b q a p p d a p gp p b q gp c q d a b c d c d a b b c RR 타입회전 RL 타입회전 Copyright 27 DBLAB, Seoul National University 4
상향식스플레이트리 (4/8) i 번째연산에대한상환시간정의 (i 번째연산에대한실제시간 ) + P i P i-1 i 번째연산에대한실제시간정의 (i 번째연산에대한상환시간 ) + P i-1 P i 일련의 m 개연산을수행하는데필요한실제시간 (i번째연산에대한상환시간 ) + P P m i 전위함수정의 루트가 i 인서브트리의크기 s(i) 서브트리의총노드수일때 노드 i 의랭크 r(i) = log 2 s(i) 트리의전위 = i r ( i) Copyright 27 DBLAB, Seoul National University 41
Copyright 27 DBLAB, Seoul National University 42 상향식스플레이트리 (5/8) a b c d e f g h i j 1 9 8 2 7 6 3 4 5 (a) 초기탐색트리 a b c d e f g h i j 1 9 8 2 7 6 4 5 3 (b) RR 회전뒤 a b c d e f g h i j 1 9 8 2 7 4 3 6 5 (c) LL 회전뒤 a b d ef g h i j 1 9 8 2 7 4 3 6 5 c (d) LR 회전뒤
상향식스플레이트리 (6/8) 5 1 9 a 2 8 j b 4 6 i c 3 d e f g 7 h (e) RL 회전뒤 Copyright 27 DBLAB, Seoul National University 43
상향식스플레이트리 (7/8) 보조정리 1.3 노드당 n 개의원소를갖는이원탐색트리고려 노드 q 에서시작하는연산의상환비용은 3( log 2 n -r(q))+1 증명 스플레이의정의의 3 단계를고려하면 (1) q 는 이거나루트, 트리의전위를바뀌지않으므로상환비용 = 실제비용, 비용은 1 (2) 회전수행, p 와 q 만랭크영향을받기때문에 Δp = r'(p)+r'(q)-r(p)-r(q), r'(p) r(p) 이므로 Δp = r'(q)-r(q) 상환비용은 r'(q)-r(q)+1 이하 (3) q, p, gp 의랭크만변경 Δp = r'(q)+r'(p)-r'(gp)-r(q)-r(p)-r'(gp), r(gp) = r'(q) 이므로 Δp = r'(p)+r'(gp)-r(q)-r(p) Copyright 27 DBLAB, Seoul National University 44
상향식스플레이트리 (8/8) RR 회전고려 r'(p) r'(q), r'(gp) r'(q), r(q) r(p) 이면 Δp 2(r'(q)-r(q)) gp q r'(q)>r(q) 라면 Δp 3(r'(q)-r(q)) -1 a p p d r'(q)=r(q) 라면 r'(q)=r(q)=r(p)=r(gp), s'(q)>s(q)+s'(g) 따라서 r'(gp)<r'(q) b q gp c r'(gp)=r'(q) 라면 s'(q)>2 r(q) +2 r '(gp) =2 r(q)+1 랭크정의를어기는것이므로 c d a b 식 (1) 로부터 Δp 2(r'(q)-r(q)) -1 = 3(r'(q)-r(q)) -1 RR 타입 따라서 RR 회전의상환비용은 1+3(r'(q)-r(q)) -1 = 3(r'(q)-r(q)) Copyright 27 DBLAB, Seoul National University 45
하향식스플레이트리 (1/6) 하향식스플레이트리 (Top-Down splay trees) 상향식스플레이트리에서적용된것과같이정의 루트에서스플레이노드까지경로를따름 3 개의구성요소 이원탐색트리 small 이원탐색트리 big 스플레이트리 7 개의경로 경우 : x 는스플레이노드인경우분할을종료한다. 경우 L : 스플레이노드가 x 의자식인경우, x 와그오른쪽서브트리는스플레이노드의키보다더큰키를포함 경우 R : 스플레이노드가 x 의오른쪽자식인경우 L 과대칭적임 경우 LR : 경우 L 을처리한후, 경우 R 을처리 경우 RL : 경우 R 을처리한후, 경우 L 을처리 경우 LL : 경우 L 을두번적용하는것이아니라, x 주변으로 LL 회전 경우 RR : 경우 LL 과대칭적임 Copyright 27 DBLAB, Seoul National University 46
하향식스플레이트리 (2/6) x big A b D B AR E DR BL BR (a) L 변형전 ER big x D B b E DR BL BR A ER (b) L 변형뒤 AR Copyright 27 DBLAB, Seoul National University 47
하향식스플레이트리 (3/6) x A big B AR b D C BR E DR ER CL CR (a) LL 변형전 big D x C b E DR CL CR B A ER (b) LL 변형뒤 BR AR Copyright 27 DBLAB, Seoul National University 48
Copyright 27 DBLAB, Seoul National University 49 하샹식스플레이트리의예하향식스플레이트리 (4/6) 8 2 7 6 4 3 5 x b c d e f g h i 1 small s a 9 x big j (a) RL 변형뒤 (b) LR 변형뒤 7 6 4 3 5 c d e f g h x 1 small s a 2 b 9 x big j 8 i
Copyright 27 DBLAB, Seoul National University 5 하향식스플레이트리 (5/6) 3 7 5 e f 1 small a (c) LL 변형뒤 x c d 2 b s 9 8 7 6 i j h g big b (d) RR 변형뒤 5 e f x 1 2 a b small c 4 3 d s 9 8 7 6 i j h g big b
Copyright 27 DBLAB, Seoul National University 51 하향식스플레이트리 (6/6) (e) 스플레이노드의서브트리를이동한뒤 5 x 1 2 a b small c 4 3 d s 9 8 7 6 i j h g big b e f (f) 최종탐색트리 1 2 4 3 d e c 9 8 7 6 i j h g f 5 a b