lsd/420.html~010066400011770035271000000167730662457466600130300ustar00lsdwww00003110017552 CMSC 420

COMPUTER SCIENCE 420 - DATA STRUCTURES

Larry Davis
A. V. Williams 2113
lsd@umiacs.umd.edu
405-6718

Teaching Assistant:
Kuo-Tung Ku

ktg@cs.umd.edu

Office hours: MW 10:30-12:30, AVW 1151



Syllabus

Texts - no required texts. The followed are recommended reading

  1. Data structures and algorithms in Java, by Goodrich and Tamassi
  2. Notes on Data Structures, Hanan Samet

Programming projects

  1. Project 1 . Also, yoou should read the project FAQ often.
  2. Project 2

Presentations

You can either view the presentations using your viewer, or you can obtain them using anonymous ftp from the ftp site ftp.umiacs.umd.edu. The directory is pub/lsd. You log in using the id ``anonymous'' and using your email address as your password. Then, go to the directory containing the postscript files, and obtain the file using ``get file.ps.'' I will only leave these files on the ftp site for a few weeks because they are large.

  1. Introduction - Current for Fall 1998
  2. Arrays - Current for Fall 1998
  3. Trees - Current for Fall 1998
  4. Dynamic trees - Current for Fall 98
  5. Btrees - Current for Fall 1998
  6. Tries - Current forFall 98
  7. Hashing - current for Fall 98
  8. Data structures for points - Current for 98 (revised October 12)
  9. Regions - Current for 1998 (revised October 21)
  10. Rectangles - NOT included in 1997
  11. Priority Queues - current for Fall 1998
  12. Quadtrees for line segments - current for 1997
  13. Memory Management - current for Fall 1998
  14. Strings - new for 1998
  15. Sorting - NOT included in 1997

Cool web sites on data structures

First Exam: October 8 in Class
The first exam will cover the material up to the section on Brent's method for insertion into a hash table.

An example of a past exam on (most of these) topics can be found here.
You should be able to perform the following operations on the data structures covered in class:

The exam will include a number of questions in which you are given a data structure and asked to show what the data structure looks like after a specified insertion or deletion. In addition to the operations listed above you should also know how to do the following:

    1. Given a binary tree threaded in symmetric order, find any node's preorder successor
    2. Given a sequential encoded enumeration of an arbitrary tree, recover the binary tree representation of that tree
    3. Develop a storage allocation function for k-banded NxN arrays (arrays having nonzero elements only on the main diagonal and the k diagonals above and below the main diagonal)
      1. Check the extra pages on storage allocation for arrays

The second exam is scheduled for class on Thursday November 5

The second exam will cover material up to the lecture on Thursday October 29 and back to the material on extendible hashing. You are responsible for the following topics:

  1. Insertion and deletion of keys into an extendible hash table
  2. Insertion and range searching in a point quadtree
  3. Insertion, deletion and range searching in a k-d tree
  4. Construction of a priority or inverse priority search tree for a given set of points
  5. Insertion and deletion from a PR quadtree
  6. Representation of region maps using Morton Coding and 4-ary trees
  7. Neighbor finding in quadtrees represented as 4-ary trees

Additionally, there are a set of problems for you to think about before the exam:

  1. What is the maximum number of nodes that it would take to store a 2m x 2m square in a quadtree of width 2 n-1?
  2. Given the Morton code and size of a quadtree node, what is the Morton code of its parent? Of its four children?

The last exam is scheduled for class on Tuesday December 8. Topics covered on this exam include:

  1. Priority queues - using both heap and binomial queue representations
  2. Strings - coding using Huffman codes and ZLW; string matching using KMP, Rabin-KARP and FSM's
  3. Memory management - compression schemes, buddy system
  4. Persistence
  5. Dynamic Programming

The exam will be structured similarly to the revious exams- you will be given data structures and will be asked to show the results of inserting, deleting items from that data structure. In addition you should consider the following problems:

  1. Develop a method for compressing used blocks in the buddy system when a request for a block fails

Here are some old exams to look at:

lsd/420ppt/004077500011770035271000000000000670663436000124425ustar00lsdwww00003110017552lsd/420ppt/sol.ps010066400011770035271000003352770603523334400136110ustar00lsdwww00003110017552%!PS-Adobe-2.0 %%Creator: dvips 5.55 Copyright 1986, 1994 Radical Eye Software %%Title: sol.dvi %%CreationDate: Fri Oct 6 02:31:30 1995 %%Pages: 5 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips sol %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1995.10.06:0230 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[matrix currentmatrix{dup dup round sub abs 0.00001 lt{round}if} forall round exch round exch]setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{ /nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{ /sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0] N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]} if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{ cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail {dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{ 4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{ p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet %%BeginProcSet: special.pro TeXDict begin /SDict 200 dict N SDict begin /@SpecialDefaults{/hs 612 N /vs 792 N /ho 0 N /vo 0 N /hsc 1 N /vsc 1 N /ang 0 N /CLIP 0 N /rwiSeen false N /rhiSeen false N /letter{}N /note{}N /a4{}N /legal{}N}B /@scaleunit 100 N /@hscale{@scaleunit div /hsc X}B /@vscale{@scaleunit div /vsc X}B /@hsize{/hs X /CLIP 1 N}B /@vsize{/vs X /CLIP 1 N}B /@clip{ /CLIP 2 N}B /@hoffset{/ho X}B /@voffset{/vo X}B /@angle{/ang X}B /@rwi{ 10 div /rwi X /rwiSeen true N}B /@rhi{10 div /rhi X /rhiSeen true N}B /@llx{/llx X}B /@lly{/lly X}B /@urx{/urx X}B /@ury{/ury X}B /magscale true def end /@MacSetUp{userdict /md known{userdict /md get type /dicttype eq{userdict begin md length 10 add md maxlength ge{/md md dup length 20 add dict copy def}if end md begin /letter{}N /note{}N /legal{} N /od{txpose 1 0 mtx defaultmatrix dtransform S atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{itransform lineto} }{6 -2 roll transform 6 -2 roll transform 6 -2 roll transform{ itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll curveto}}{{ closepath}}pathforall newpath counttomark array astore /gc xdf pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}if}N /txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1 -1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop 90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr 1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr 2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4 -1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S TR}if}N /cp {pop pop showpage pm restore}N end}if}if}N /normalscale{Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale}if 0 setgray} N /psfts{S 65781.76 div N}N /startTexFig{/psf$SavedState save N userdict maxlength dict begin /magscale false def normalscale currentpoint TR /psf$ury psfts /psf$urx psfts /psf$lly psfts /psf$llx psfts /psf$y psfts /psf$x psfts currentpoint /psf$cy X /psf$cx X /psf$sx psf$x psf$urx psf$llx sub div N /psf$sy psf$y psf$ury psf$lly sub div N psf$sx psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub TR /showpage{}N /erasepage{}N /copypage{}N /p 3 def @MacSetUp}N /doclip{ psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2 roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath moveto}N /endTexFig{end psf$SavedState restore}N /@beginspecial{SDict begin /SpecialSave save N gsave normalscale currentpoint TR @SpecialDefaults count /ocount X /dcount countdictstack N}N /@setspecial {CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR }{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury lineto closepath clip}if /showpage{}N /erasepage{}N /copypage{}N newpath }N /@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{ end}repeat grestore SpecialSave restore end}N /@defspecial{SDict begin} N /@fedspecial{end}B /li{lineto}B /rl{rlineto}B /rc{rcurveto}B /np{ /SaveX currentpoint /SaveY X N 1 setlinecap newpath}N /st{stroke SaveX SaveY moveto}N /fil{fill SaveX SaveY moveto}N /ellipse{/endangle X /startangle X /yrad X /xrad X /savematrix matrix currentmatrix N TR xrad yrad scale 0 0 1 startangle endangle arc savematrix setmatrix}N end %%EndProcSet TeXDict begin 40258431 52099146 1000 300 300 (/a/ringding/dextrose/urhan/421/sol.dvi) @start /Fa 1 51 df<1F0060C06060F070F030603000700070006000C001C00180020004000810101020 207FE0FFE00C137E9211>50 D E /Fb 17 115 df<60F0F06004047C830C>58 D<60F0F0701010101020204080040C7C830C>I<0000038000000F0000003C000000F000 0003C000000F0000003C000000F0000003C000000F0000003C000000F0000000F0000000 3C0000000F00000003C0000000F00000003C0000000F00000003C0000000F00000003C00 00000F000000038019187D9520>I62 D<00000C0000000C0000001C0000001C0000003C0000007C0000 005C0000009C0000008E0000010E0000010E0000020E0000040E0000040E0000080E0000 080E0000100E0000200E00003FFE00004007000040070000800700010007000100070002 00070002000700060007001E000700FF807FF01C1D7F9C1F>65 D<01FE0000FF003E0000 F0002E0001E0002E0002E0002E0002E0002E0004E0004E0009C0004E0009C000470011C0 00470011C000870023800087004380008700438000870083800107010700010701070001 0382070001038207000203840E000203880E000203880E000203900E000403A01C000403 A01C000401C01C000C01C01C001C01803C00FF8103FF80281C7E9B28>77 D<01E3000717000C0F00180F00380E00300E00700E00700E00E01C00E01C00E01C00E01C 00E03880E03880E038806078803199001E0E0011127E9116>97 D<3F00070007000E000E 000E000E001C001C001C001C0039E03A303C1838187018701C701C701CE038E038E038E0 30E070E060E0C061C023001E000E1D7E9C12>I<0007E00000E00000E00001C00001C000 01C00001C000038000038000038000038001E7000717000C0F00180F00380E00300E0070 0E00700E00E01C00E01C00E01C00E01C00E03880E03880E038806078803199001E0E0013 1D7E9C16>100 D<01F007080C0818043808300870307FC0E000E000E000E000E000E004 6008601030600F800E127E9113>I<01C003C003C001800000000000000000000000001C 00270047004700870087000E000E001C001C001C003800388038807080710032001C000A 1C7E9B0E>105 D<0007000F000F00060000000000000000000000000070009C010C020C 021C041C001C001C0038003800380038007000700070007000E000E000E000E001C061C0 F180F300E6007C001024809B11>I<0FC00001C00001C000038000038000038000038000 0700000700000700000700000E07000E18800E21C00E23C01C47801C83001D00001E0000 3F800039C00038E00038E00070E10070E10070E10070E200E06200603C00121D7E9C16> I<381F81F04E20C6184640E81C4680F01C8F00F01C8E00E01C0E00E01C0E00E01C1C01C0 381C01C0381C01C0381C01C0703803807138038071380380E1380380E270070064300300 3820127E9124>109 D<381F004E61804681C04701C08F01C08E01C00E01C00E01C01C03 801C03801C03801C0700380710380710380E10380E2070064030038014127E9119>I<00 F800030C000E06001C0300180300300300700380700380E00700E00700E00700E00E00E0 0E00E01C0060180060300030E0000F800011127E9114>I<383C4E424687470F8E1E8E0C 0E000E001C001C001C001C0038003800380038007000300010127E9113>114 D E /Fc 3 4 df0 D<400020C000606000C030018018 03000C0600060C0003180001B00000E00000E00001B000031800060C000C060018030030 01806000C0C0006040002013147A9320>2 D<01800180018001804182F18F399C0FF003 C003C00FF0399CF18F4182018001800180018010127E9215>I E /Fd 34 120 df<00E001E0038007000E001C001C0038003800700070007000E000E000E0 00E000E000E000E000E000E000700070007000380038001C001C000E000700038001E000 E00B217A9C16>40 DI<01C00001C00001C00001C00071C700F9CF807FFF001FFC0007F0 0007F0001FFC007FFF00F9CF8071C70001C00001C00001C00001C00011127E9516>I<70 F8F8F8700505788416>46 D<01800380038007800F807F80FF8073800380038003800380 03800380038003800380038003800380038003807FF87FFC7FF80E197C9816>49 D<07E0001FF8003FFC00783E00E00700F00780F003806003800003800003800007000007 00000E00001C0000380000700000E00001C0000380000F00001E03803803807FFF80FFFF 807FFF8011197E9816>I<387C7C7C38000000000000000038787C7C3C1C1C3870E04006 18799116>59 D<000180000780001F80003E0000F80001F00007C0000F80003E0000FC00 00F00000FC00003E00000F800007C00001F00000F800003E00001F800007800001801115 7E9616>I<7FFF00FFFF80FFFF80000000000000000000000000000000FFFF80FFFF807F FF00110B7E9116>II<01F18007FB800FFF801F0F803C0780380380700380700380F00000E000 00E00000E00000E00000E00000E00000E00000F000007003807003803803803C07001F0F 000FFE0007FC0001F00011197E9816>67 D73 D76 D<7E1FC0FF3FE07F1FC01D07001D87001D87001D8700 1DC7001DC7001CC7001CC7001CE7001CE7001CE7001C67001C67001C77001C77001C3700 1C37001C37001C17007F1F00FF9F007F0F0013197F9816>78 D<7FF800FFFE007FFF001C 0F801C03801C03C01C01C01C01C01C01C01C03C01C03801C0F801FFF001FFE001FF8001C 00001C00001C00001C00001C00001C00001C00007F0000FF80007F000012197F9816>80 D<7FE000FFF8007FFC001C1E001C0F001C07001C07001C07001C07001C0F001C1E001FFC 001FF8001FFC001C1C001C0E001C0E001C0E001C0E001C0E201C0E701C0E707F07E0FF87 E07F03C014197F9816>82 D87 D<1FE0003FF0007FF800783C0030 0E00000E00000E0003FE001FFE003E0E00700E00E00E00E00E00E00E00783E007FFFE03F E7E00F83E013127E9116>97 D<03F80FFC1FFE3C1E780C7000E000E000E000E000E000F0 00700778073E0E1FFC0FF803F010127D9116>99 D<003F00007F00003F00000700000700 00070000070003C7000FF7001FFF003C1F00780F00700700E00700E00700E00700E00700 E00700E00700700F00700F003C1F001FFFE00FE7F007C7E014197F9816>I<03E00FF81F FC3C1E780E7007E007FFFFFFFFFFFFE000E000700778073C0F1FFE0FFC03F010127D9116 >I<001F00007F8000FF8001E78001C30001C00001C0007FFF00FFFF00FFFF0001C00001 C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C0003FFE007F FF003FFE0011197F9816>I<7E0000FE00007E00000E00000E00000E00000E00000E3C00 0EFE000FFF000F87800F03800E03800E03800E03800E03800E03800E03800E03800E0380 0E03800E03807FC7F0FFE7F87FC7F01519809816>104 D<018003C003C0018000000000 000000007FC07FC07FC001C001C001C001C001C001C001C001C001C001C001C001C07FFF FFFF7FFF101A7D9916>I108 DI<7E3C00FEFE007FFF000F87800F03800E03800E03800E0380 0E03800E03800E03800E03800E03800E03800E03807FC7F0FFE7F87FC7F01512809116> I<03E0000FF8001FFC003C1E00780F00700700E00380E00380E00380E00380E00380F007 80700700780F003C1E001FFC000FF80003E00011127E9116>I<7E3E00FEFF007FFF800F 83C00F00E00E00E00E00700E00700E00700E00700E00700E00700E00E00F01E00F83C00F FF800EFF000E3C000E00000E00000E00000E00000E00000E00007FC000FFE0007FC00014 1B809116>I114 D<0FEC3FFC7FFCF03CE01CE01C70007F801FF007F8003C600EE00EF00EF81EFFFCFFF8C7 E00F127D9116>I<0300000700000700000700000700007FFF00FFFF00FFFF0007000007 000007000007000007000007000007000007010007038007038007038007870003FE0001 FC0000F80011177F9616>I<7E1F80FE3F807E1F800E03800E03800E03800E03800E0380 0E03800E03800E03800E03800E03800E03800E0F800FFFF007FBF803E3F01512809116> I119 D E /Fe 61 123 df<007E0001C1800301800703C00E03C00E01800E00000E00000E0000 0E00000E0000FFFFC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C07F87F8151D809C17>12 D<60F0F8680808081010204080050C7C9C0C>39 D<004000800100020006000C000C0018 001800300030007000600060006000E000E000E000E000E000E000E000E000E000E000E0 00E000600060006000700030003000180018000C000C00060002000100008000400A2A7D 9E10>I<800040002000100018000C000C000600060003000300038001800180018001C0 01C001C001C001C001C001C001C001C001C001C001C00180018001800380030003000600 06000C000C00180010002000400080000A2A7E9E10>I<00060000000600000006000000 060000000600000006000000060000000600000006000000060000000600000006000000 060000FFFFFFE0FFFFFFE000060000000600000006000000060000000600000006000000 0600000006000000060000000600000006000000060000000600001B1C7E9720>43 D<60F0F0701010101020204080040C7C830C>II<60F0F0600404 7C830C>I<03C00C301818300C300C700E60066006E007E007E007E007E007E007E007E0 07E007E007E007E007E00760066006700E300C300C18180C3007E0101D7E9B15>48 D<030007003F00C700070007000700070007000700070007000700070007000700070007 00070007000700070007000700070007000F80FFF80D1C7C9B15>I<07C01830201C400C 400EF00FF80FF807F8077007000F000E000E001C001C00380070006000C0018003000601 0C01180110023FFE7FFEFFFE101C7E9B15>I<07E01830201C201C781E780E781E381E00 1C001C00180030006007E00030001C001C000E000F000F700FF80FF80FF80FF00E401C20 1C183007E0101D7E9B15>I<000C00000C00001C00003C00003C00005C0000DC00009C00 011C00031C00021C00041C000C1C00081C00101C00301C00201C00401C00C01C00FFFFC0 001C00001C00001C00001C00001C00001C00001C0001FFC0121C7F9B15>I<300C3FF83F F03FC020002000200020002000200023E024302818301C200E000E000F000F000F600FF0 0FF00FF00F800E401E401C2038187007C0101D7E9B15>I<00F0030C06040C0E181E301E 300C700070006000E3E0E430E818F00CF00EE006E007E007E007E007E007600760077006 300E300C18180C3003E0101D7E9B15>I<03E00C301008200C2006600660066006700678 0C3E083FB01FE007F007F818FC307E601E600FC007C003C003C003C00360026004300C1C 1007E0101D7E9B15>56 D<03C00C301818300C700C600EE006E006E007E007E007E007E0 076007700F300F18170C2707C700060006000E300C780C78187010203030C00F80101D7E 9B15>I<60F0F0600000000000000000000060F0F06004127C910C>I<7FFFFFC0FFFFFFE0 0000000000000000000000000000000000000000000000000000000000000000FFFFFFE0 7FFFFFC01B0C7E8F20>61 D<000600000006000000060000000F0000000F0000000F0000 0017800000178000001780000023C0000023C0000023C0000041E0000041E0000041E000 0080F0000080F0000180F8000100780001FFF80003007C0002003C0002003C0006003E00 04001E0004001E000C001F001E001F00FF80FFF01C1D7F9C1F>65 DI<001F808000E061800180198007000780 0E0003801C0003801C00018038000180780000807800008070000080F0000000F0000000 F0000000F0000000F0000000F0000000F0000000F0000000700000807800008078000080 380000801C0001001C0001000E000200070004000180080000E03000001FC000191E7E9C 1E>IIII72 DI76 D78 D<003F800000E0E00003803800 07001C000E000E001C0007003C00078038000380780003C0780003C0700001C0F00001E0 F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0F00001E0700001C0780003C0 780003C0380003803C0007801C0007000E000E0007001C000380380000E0E000003F8000 1B1E7E9C20>II<07E0801C198030058070 0380600180E00180E00080E00080E00080F00000F800007C00007FC0003FF8001FFE0007 FF0000FF80000F800007C00003C00001C08001C08001C08001C0C00180C00180E00300D0 0200CC0C0083F800121E7E9C17>83 D<7FFFFFC0700F01C0600F00C0400F0040400F0040 C00F0020800F0020800F0020800F0020000F0000000F0000000F0000000F0000000F0000 000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000 000F0000000F0000000F0000001F800003FFFC001B1C7F9B1E>I86 DI91 D93 D<1FC000307000783800781C00301C00001C00001C0001 FC000F1C00381C00701C00601C00E01C40E01C40E01C40603C40304E801F870012127E91 15>97 DI<07E00C30187830787030 6000E000E000E000E000E000E00060007004300418080C3007C00E127E9112>I<003F00 00070000070000070000070000070000070000070000070000070000070003E7000C1700 180F00300700700700600700E00700E00700E00700E00700E00700E00700600700700700 300700180F000C370007C7E0131D7E9C17>I<03E00C301818300C700E6006E006FFFEE0 00E000E000E00060007002300218040C1803E00F127F9112>I<00F8018C071E061E0E0C 0E000E000E000E000E000E00FFE00E000E000E000E000E000E000E000E000E000E000E00 0E000E000E000E000E007FE00F1D809C0D>I<00038003C4C00C38C01C3880181800381C 00381C00381C00381C001818001C38000C300013C0001000003000001800001FF8001FFF 001FFF803003806001C0C000C0C000C0C000C06001803003001C0E0007F800121C7F9215 >II<18003C003C00180000000000 00000000000000000000FC001C001C001C001C001C001C001C001C001C001C001C001C00 1C001C001C001C00FF80091D7F9C0C>I107 DIII<03F0000E1C00180600300300700380600180E001C0E001C0 E001C0E001C0E001C0E001C06001807003803003001806000E1C0003F00012127F9115> II114 D<1F9030704030C010C010E010F8 007F803FE00FF000F880388018C018C018E010D0608FC00D127F9110>I<040004000400 04000C000C001C003C00FFE01C001C001C001C001C001C001C001C001C001C101C101C10 1C101C100C100E2003C00C1A7F9910>IIII<7F8FF00F03800F030007020003840001C80001D80000F00000700000780000F80000 9C00010E00020E000607000403801E07C0FF0FF81512809116>II<7FFC70386038407040F040E041C003C0038007000F040E041C043C0C38087008 7038FFF80E127F9112>I E /Ff 12 116 df45 D<00600001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0 0003E0007FFF807FFF80111B7D9A18>49 D<07F8001FFE00383F80780FC0FC07C0FC07E0 FC03E0FC03E07803E00007E00007C00007C0000F80001F00001E0000380000700000E000 0180600300600600600800E01FFFC03FFFC07FFFC0FFFFC0FFFFC0131B7E9A18>I<78FC FCFCFC7800000000000078FCFCFCFC7806127D910D>58 D<001FE02000FFF8E003F80FE0 07C003E00F8001E01F0000E03E0000E03E0000607E0000607C000060FC000000FC000000 FC000000FC000000FC000000FC000000FC000000FC0000007C0000607E0000603E000060 3E0000C01F0000C00F80018007C0030003F80E0000FFFC00001FE0001B1C7D9B22>67 D<0FF8001C1E003E0F803E07803E07C01C07C00007C0007FC007E7C01F07C03C07C07C07 C0F807C0F807C0F807C0780BC03E13F80FE1F815127F9117>97 DI<03FC000E0E001C1F003C1F00781F00780E00F80000F800 00F80000F80000F80000F800007800007801803C01801C03000E0E0003F80011127E9115 >I<000FF0000FF00001F00001F00001F00001F00001F00001F00001F00001F00001F001 F9F00F07F01C03F03C01F07801F07801F0F801F0F801F0F801F0F801F0F801F0F801F078 01F07801F03C01F01C03F00F0FFE03F9FE171D7E9C1B>I<01FC000F07001C03803C01C0 7801C07801E0F801E0F801E0FFFFE0F80000F80000F800007800007C00603C00601E00C0 0F038001FC0013127F9116>I110 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018 F830CFC00E127E9113>115 D E /Fg 11 120 df<00100000700001F0000FF000FEF000 F0F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000 00F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000 00F00000F00000F00000F00000F00000F00000F00000F00001F8007FFFE07FFFE013287B A71E>49 D<00FE0007FF800E07E01803F02001F82000F840007C40007CF8007EFC007EFC 003EFC003EFC003E78007E00007E00007C00007C0000F80000F80001F00001E00003C000 0780000700000E00001C0000380000700000600000C0000180020300020600040C000418 000410000C3FFFFC7FFFF8FFFFF8FFFFF817287DA71E>I<007F000003FFC0000701F000 0C00F80010007C001C007C003E007E003E003E003E003E001E003E000C007E0000007C00 00007C00000078000000F0000000E0000001C0000007000000FF00000001E0000000F000 0000780000003C0000003E0000001F0000001F0000001F8000001F8030001F8078001F80 FC001F80FC001F80FC001F00F8001F0040003F0040003E0030007C001800F8000F01F000 03FFC000007F000019297EA71E>I<00006000000060000000E0000001E0000001E00000 03E0000003E0000005E0000009E0000009E0000011E0000021E0000021E0000041E00000 81E0000081E0000101E0000201E0000201E0000401E0000801E0000801E0001001E00030 01E0002001E0004001E000C001E000FFFFFF80FFFFFF800001E0000001E0000001E00000 01E0000001E0000001E0000001E0000001E0000003F000007FFF80007FFF8019287EA71E >I<78FCFCFCFC78000000000000000000000000000078FCFCFCFC78061A7B9911>58 D<00001800000000180000000018000000003C000000003C000000003C000000007E0000 00007E00000000FF000000009F000000009F000000011F800000010F800000010F800000 0207C000000207C000000207C000000403E000000403E000000403E000000801F0000008 01F000001801F800001000F800001000F800002000FC000020007C00003FFFFC00007FFF FE000040003E000040003E000080001F000080001F000080001F000100000F800100000F 800100000F8002000007C007000007C01F80000FE0FFF000FFFFFFF000FFFF282A7EA92D >65 D<007E0003C3800700E00E00F01C00703C00783C003878003C78003CF8003CF8003C FFFFFCF80000F80000F80000F80000F800007800007C00003C00043C00041E00080E0010 07002001C0C0007F00161A7E991B>101 D<0783F800FF8C1C00FF900E000FA0070007A0 078007C0078007C007800780078007800780078007800780078007800780078007800780 078007800780078007800780078007800780078007800780078007800780078007800780 078007800780FFFCFFFCFFFCFFFC1E1A7F9921>110 D<0787C0FF98E0FF91F00FA1F007 C1F007C0E007C00007800007800007800007800007800007800007800007800007800007 800007800007800007800007800007800007800007C000FFFE00FFFE00141A7F9917> 114 D<07F8401C06C03001C06000C06000C0E00040E00040F00040F800007E00007FF000 3FFE000FFF0003FF80003FC00007C08001E08001E0C000E0C000E0C000E0E000C0F001C0 F80180C4070083F800131A7E9918>I119 D E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 32 162 a Fg(Answ)n(ers:)-30 261 y(Answ)n(er)20 b(1:)-30 361 y Ff(a-)14 b Fe(See)h(Figure)28 b(1.)495 510 y 15156103 11840716 4407377 14471987 35785277 37561384 startTexFig 495 510 a %%BeginDocument: thread1.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save 63.5 592.5 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 7.500 slw % Ellipse n 1500 2100 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 600 3300 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1875 3300 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4500 2100 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2700 825 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5550 3300 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6600 4500 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3900 3300 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3450 4425 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7275 5475 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 2475 975 m 1650 1950 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1350 2250 m 675 3150 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1650 2250 m 1875 3075 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2925 975 m 4425 1950 l 4425 1950 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4350 2250 m 3975 3075 l 3975 3075 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3825 3525 m 3600 4275 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 5775 3450 m 6450 4350 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 6675 4650 m 7125 5250 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4650 2250 m 5475 3075 l gs 0.75 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 2025 3450 m 2116.41 3577.97 2172.66 3615.47 2250 3600 curveto 2456.25 3558.75 2504.62 3273.33 2550 3150 curveto 2657.71 2857.24 2682.81 2168.17 2700 1875 curveto 2707.53 1746.55 2707.53 1559.05 2700 1125 curveto gs col-1 s gr [] 0 setdash n 2644.17 1366.00 m 2700.00 1125.00 l 2764.15 1363.92 l 2704.66 1365.46 l 2644.17 1366.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 1800 3450 m 1749.38 3618.75 1711.88 3675.00 1650 3675 curveto 1567.50 3675.00 1519.70 3515.07 1500 3450 curveto 1438.53 3246.98 1438.53 2965.73 1500 2325 curveto gs col-1 s gr [] 0 setdash n 1417.35 2558.17 m 1500.00 2325.00 l 1536.81 2569.63 l 1477.58 2564.40 l 1417.35 2558.17 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 675 3525 m 768.14 3650.45 824.39 3687.95 900 3675 curveto 1039.81 3651.05 1082.27 3451.03 1125 3375 curveto 1217.03 3211.23 1372.03 2803.17 1425 2625 curveto 1443.81 2561.74 1462.56 2467.99 1500 2250 curveto gs col-1 s gr [] 0 setdash % Interp Spline [100.0] 0 setdash n 450 3450 m 250.31 3613.12 194.06 3688.12 225 3750 curveto 225.00 3750.00 225.00 3750.00 225 3750 curveto gs col-1 s gr [] 0 setdash % Interp Spline [100.0] 0 setdash n 3375 4650 m 3324.38 4875.00 3286.88 4950.00 3225 4950 curveto 3060.00 4950.00 2963.98 4506.96 2925 4350 curveto 2784.40 3783.91 2765.65 2977.66 2850 1125 curveto gs col-1 s gr [] 0 setdash n 2779.15 1362.02 m 2850.00 1125.00 l 2899.02 1367.48 l 2839.58 1365.25 l 2779.15 1362.02 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 3675 4650 m 3904.33 4554.93 3998.08 4498.68 4050 4425 curveto 4110.54 4339.09 4128.76 4142.97 4125 4050 curveto 4120.97 3950.45 4083.47 3819.20 3975 3525 curveto gs col-1 s gr [] 0 setdash n 4001.73 3770.94 m 3975.00 3525.00 l 4114.32 3729.43 l 4058.52 3750.68 l 4001.73 3770.94 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 4050 3375 m 4231.02 3536.66 4324.77 3574.16 4425 3525 curveto 4605.66 3436.39 4564.11 3129.59 4575 3000 curveto 4585.16 2879.11 4566.41 2710.36 4500 2325 curveto gs col-1 s gr [] 0 setdash n 4481.63 2571.70 m 4500.00 2325.00 l 4599.89 2551.32 l 4541.26 2562.01 l 4481.63 2571.70 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 5475 3525 m 5186.67 3598.06 5055.42 3598.06 4950 3525 curveto 4778.43 3406.10 4766.81 3065.77 4725 2925 curveto 4691.16 2811.08 4653.66 2642.33 4575 2250 curveto gs col-1 s gr [] 0 setdash % Interp Spline [100.0] 0 setdash n 6375 4650 m 6277.39 4769.54 6221.14 4807.04 6150 4800 curveto 5926.78 4777.90 5774.67 4492.52 5700 4350 curveto 5626.21 4209.16 5588.71 4002.91 5550 3525 curveto gs col-1 s gr [] 0 setdash n 5509.57 3769.06 m 5550.00 3525.00 l 5629.18 3759.37 l 5569.88 3764.72 l 5509.57 3769.06 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 7050 5625 m 6738.94 5787.37 6588.94 5806.12 6450 5700 curveto 6287.53 5575.90 6363.45 5303.10 6375 5175 curveto 6382.75 5089.07 6420.25 4976.57 6525 4725 curveto gs col-1 s gr [] 0 setdash n 6377.36 4923.50 m 6525.00 4725.00 l 6488.14 4969.62 l 6433.25 4947.06 l 6377.36 4923.50 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 7425 5550 m 7521.84 5739.04 7578.09 5814.04 7650 5850 curveto 7650.00 5850.00 7650.00 5850.00 7650 5850 curveto gs col-1 s gr [] 0 setdash /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 525 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1350 1725 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 450 2925 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1950 2925 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4425 1725 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3675 3000 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3300 4125 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5700 3075 m gs 1 -1 sc (s) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6750 4275 m gs 1 -1 sc (t) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7575 5325 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 75 3975 m gs 1 -1 sc (NIL) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 6150 m gs 1 -1 sc (NIL) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 504 1352 a Fe(Figure)14 b(1:)k(Binary)c(tree)h(with)f(symmetric)e (order)i(threads)-30 1459 y Ff(b-)g Fe(If)g(the)h(left)g(p)q(oin)o(ter) f(is)h(not)f(a)g(thread)i(and)e(is)g(not)h(NIL)f(then)i(left)e(c)o (hild)g(is)g(the)i(preorder)g(successor.)22 b(Otherwise)16 b(,if)d(the)-30 1509 y(righ)o(t)h(p)q(oin)o(ter)g(is)g(not)g(a)g (thread)h(and)f(is)g(not)g(NIL)g(then)h(righ)o(t)f(c)o(hild)g(is)g(the) g(preorder)i(successor.)22 b(If)13 b(neither)i(of)f(these)i(cases)-30 1559 y(is)e(true,)i(then)f(the)g(righ)o(t)f(p)q(oin)o(ter)h(m)o(ust)e (b)q(e)j(a)e(thread.)21 b(W)m(e)14 b(follo)o(w)e(the)k(righ)o(t)e (thread,)h(and)f(k)o(eep)h(follo)o(wing)d(righ)o(t)i(p)q(oin)o(ters)-30 1609 y(atthe)j(next)g(no)q(de,)f(so)h(long)e(as)h(they)h(are)g (threads.)26 b(W)m(e)16 b(stop)h(when)f(w)o(e)h(\014nd)f(a)g (non-thread)h(righ)o(t)f(p)q(oin)o(ter.)25 b(If)16 b(it)g(is)g(NIL)-30 1658 y(then)f(the)f(successor)i(is)e(NIL,)g(otherwise)g(the)h (successor)h(is)e(the)h(righ)o(t)e(c)o(hild.)-30 1758 y Ff(c-)h Fe(See)h(Figure)28 b(2.)-30 1858 y Ff(d-)13 b Fe(There)i(are)g(t)o(w)o(o)e(cases)i(to)f(b)q(e)g(considered)-30 1957 y Ff(Case)i(1:)-30 2007 y Fe(The)d(no)q(de)h(is)f(the)g(left)g(c)o (hild)g(of)f(the)i(paren)o(t.)k(In)13 b(this)g(case)h(if)e(the)i(righ)o (t)f(p)q(oin)o(ter)g(is)g(a)f(thread)i(then)g(it)e(p)q(oin)o(ts)h(to)g (the)h(paren)o(t.)-30 2057 y(Otherwise)k(follo)o(w)c(the)j(righ)o(t)e (p)q(oin)o(ters)i(un)o(til)f(y)o(ou)f(\014nd)i(a)f(righ)o(t)f(thread)i (at)f(a)g(no)q(de)h(along)e(the)h(p)q(oth.)26 b(The)16 b(no)q(de)h(that)f(is)-30 2107 y(p)q(oin)o(ted)f(b)o(y)g(this)g(thread) h(is)f(the)h(paren)o(t)g(of)e(the)i(no)q(de.)22 b(\(Note)16 b(that)f(if)g(the)h(no)q(de)f(is)g(not)g(the)h(left)f(c)o(hild)g(of)f (its)h(paren)o(t)h(and)-30 2157 y(w)o(e)e(execute)i(this)e(algorithm)d (w)o(e)j(will)f(either)h(get)g(NIL)g(or)g(a)g(no)q(de)g(whic)o(h)g(is)g (not)f(a)h(paren)o(t.W)m(e'll)e(utilize)i(this)g(later\))-30 2256 y Ff(Case)i(2:)-30 2306 y Fe(This)e(case)h(is)f(symmetrical.)i(If) e(the)h(no)q(de)f(is)g(the)h(righ)o(t)f(c)o(hild)f(of)h(its)g(paren)o (t)h(and)f(if)f(the)i(left)f(p)q(oin)o(ter)g(is)g(a)g(thread)h(then)f (the)-30 2356 y(no)q(de)f(p)q(oin)o(ted)g(b)o(y)g(this)g(thread)g(is)g (the)g(paren)o(t.)18 b(Otherwise)d(w)o(e)e(follo)o(w)e(the)i(left)g(p)q (oin)o(ters)g(un)o(til)f(w)o(e)h(\014nd)g(a)g(left)f(thread.)19 b(The)-30 2406 y(no)q(de)14 b(p)q(oin)o(ted)g(b)o(y)f(this)h(thread)h (will)d(b)q(e)i(the)g(paren)o(t.)19 b(\(Also)13 b(in)h(this)g(case,)g (If)f(the)h(no)q(de)h(is)e(the)h(left)g(c)o(hild)f(of)g(its)h(paren)o (t)g(and)-30 2455 y(w)o(e)g(execute)i(this)e(algorithm)d(w)o(e)j(get)g (a)g(NIL)g(v)n(alue)f(or)h(a)g(no)q(de)g(whic)o(h)g(is)f(not)h(a)g (paren)o(t.\))32 2505 y(The)f(problem)e(with)h(this)g(algorithm)e(is,)h (w)o(e)i(don't)f(kno)o(w)f(whic)o(h)h(case)i(applies.)j(Ho)o(w)o(ev)o (er)c(w)o(e)f(tak)o(e)g(a)g(guess)h(and)f(assume)-30 2555 y(that)h(Case)g(1)f(holds.)17 b(It)c(will)e(return)j(either)f(NIL) g(v)n(alue)f(or)g(a)h(no)q(de.)18 b(If)12 b(the)h(no)q(de)g(is)f(the)i (real)e(paren)o(t)h(\(w)o(e)g(can)g(c)o(hec)o(k)h(this)e(b)o(y)-30 2605 y(lo)q(oking)g(at)h(the)g(c)o(hildren)h(of)e(the)i(no)q(de)g (found\))f(then)h(w)o(e)f(are)h(done.)k(Ho)o(w)o(ev)o(er)13 b(it)g(ma)o(y)f(b)q(e)h(that)h(the)f(returned)i(v)n(alue)e(is)g(NIL)-30 2655 y(or)g(a)h(no)q(de)f(whic)o(h)h(is)f(not)g(a)g(paren)o(t.)19 b(This)13 b(happ)q(ens)i(if)d(our)i(initial)d(assumption)h(w)o(as)h (wrong.)18 b(In)c(this)f(case)h(w)o(e)g(execute)h(the)-30 2705 y(algorithm)10 b(for)j(case)h(2.)j(It)c(will)f(return)i(either)g (NIL)f(or)g(a)g(no)q(de.)18 b(If)12 b(the)i(v)n(alue)e(is)h(NIL)g(the)h (no)q(de)f(w)o(as)g(the)h(ro)q(ot)f(so)g(it)f(do)q(esn't)965 2855 y(1)p eop %%Page: 2 2 2 1 bop 225 120 a 23681433 11840716 -4078469 14471987 44336906 37561384 startTexFig 225 120 a %%BeginDocument: thread2.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -91.0 592.5 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 7.500 slw % Ellipse n 2025 2101 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1125 3301 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2400 3301 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5025 2101 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3225 826 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6075 3301 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7125 4501 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4425 3301 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3975 4426 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7800 5476 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 3000 976 m 2175 1951 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1875 2251 m 1200 3151 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2175 2251 m 2400 3076 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3450 976 m 4950 1951 l 4950 1951 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4875 2251 m 4500 3076 l 4500 3076 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4350 3526 m 4125 4276 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 6300 3451 m 6975 4351 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7200 4651 m 7650 5251 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 5175 2251 m 6000 3076 l gs 0.75 setgray ef gr gs col-1 s gr 45.000 slw % Interp Spline n 2550 3600 m 2651.11 3715.44 2707.36 3752.94 2775 3750 curveto 2935.17 3743.05 3083.83 3554.71 3150 3450 curveto 3330.48 3164.40 3401.92 2471.29 3450 2175 curveto 3480.41 1987.61 3516.43 1538.99 3525 1350 curveto 3526.55 1315.78 3490.37 1218.84 3525 1200 curveto 3787.97 1056.93 4106.72 1263.18 4800 2025 curveto gs col-1 s gr n 4565.69 1589.23 m 4800.00 2025.00 l 4388.18 1750.76 l 4477.43 1670.49 l 4565.69 1589.23 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline n 6375 3225 m 6792.42 3418.77 6961.17 3531.27 7050 3675 curveto 7116.21 3782.13 7134.96 3932.13 7125 4275 curveto gs col-1 s gr n 7258.89 3798.69 m 7125.00 4275.00 l 7018.99 3791.72 l 7139.44 3795.70 l 7258.89 3798.69 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline n 4050 4725 m 4195.66 4846.71 4270.66 4884.21 4350 4875 curveto 4534.75 4853.56 4734.81 4657.39 4800 4500 curveto 4892.19 4277.42 4517.81 3901.88 4725 3675 curveto 4800.03 3592.84 4950.26 3705.96 5025 3675 curveto 5104.28 3642.16 5214.60 3524.71 5250 3450 curveto 5333.86 3273.03 5138.55 2781.89 5325 2700 curveto 5464.14 2638.89 5614.14 2751.39 5925 3150 curveto gs col-1 s gr n 5724.44 2697.70 m 5925.00 3150.00 l 5535.19 2845.29 l 5630.32 2771.99 l 5724.44 2697.70 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline n 1125 3525 m 1183.56 3792.69 1239.81 3886.44 1350 3900 curveto 1492.53 3917.55 1606.22 3705.70 1650 3600 curveto 1711.92 3450.51 1620.13 3140.74 1650 3000 curveto 1677.58 2870.05 1752.58 2701.30 1950 2325 curveto gs col-1 s gr n 1620.74 2694.31 m 1950.00 2325.00 l 1833.27 2805.80 l 1727.50 2750.55 l 1620.74 2694.31 l clp gs 0.00 setgray ef gr gs col-1 s gr 15.000 slw % Interp Spline [100.0] 0 setdash n 2550 3451 m 2641.41 3578.97 2697.66 3616.47 2775 3601 curveto 2981.25 3559.75 3029.62 3274.33 3075 3151 curveto 3182.71 2858.24 3207.81 2169.17 3225 1876 curveto 3232.53 1747.55 3232.53 1560.05 3225 1126 curveto gs col-1 s gr [] 0 setdash n 3169.17 1367.00 m 3225.00 1126.00 l 3289.15 1364.92 l 3229.66 1366.46 l 3169.17 1367.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 1200 3526 m 1293.14 3651.45 1349.39 3688.95 1425 3676 curveto 1564.81 3652.05 1607.27 3452.03 1650 3376 curveto 1742.03 3212.23 1897.03 2804.17 1950 2626 curveto 1968.81 2562.74 1987.56 2468.99 2025 2251 curveto gs col-1 s gr [] 0 setdash % Interp Spline [100.0] 0 setdash n 975 3451 m 775.31 3614.12 719.06 3689.12 750 3751 curveto 750.00 3751.00 750.00 3751.00 750 3751 curveto gs col-1 s gr [] 0 setdash % Interp Spline [100.0] 0 setdash n 4200 4651 m 4429.33 4555.93 4523.08 4499.68 4575 4426 curveto 4635.54 4340.09 4653.76 4143.97 4650 4051 curveto 4645.97 3951.45 4608.47 3820.20 4500 3526 curveto gs col-1 s gr [] 0 setdash n 4526.73 3771.94 m 4500.00 3526.00 l 4639.32 3730.43 l 4583.52 3751.68 l 4526.73 3771.94 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 4575 3376 m 4756.02 3537.66 4849.77 3575.16 4950 3526 curveto 5130.66 3437.39 5089.11 3130.59 5100 3001 curveto 5110.16 2880.11 5091.41 2711.36 5025 2326 curveto gs col-1 s gr [] 0 setdash n 5006.63 2572.70 m 5025.00 2326.00 l 5124.89 2552.32 l 5066.26 2563.01 l 5006.63 2572.70 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline [100.0] 0 setdash n 7950 5551 m 8046.84 5740.04 8103.09 5815.04 8175 5851 curveto 8175.00 5851.00 8175.00 5851.00 8175 5851 curveto gs col-1 s gr [] 0 setdash 45.000 slw % Interp Spline n 1800 1950 m 1422.47 1888.14 1253.72 1888.14 1125 1950 curveto 880.80 2067.37 505.45 2347.10 525 2700 curveto 534.72 2875.37 647.22 2987.87 975 3150 curveto gs col-1 s gr n 597.96 2829.63 m 975.00 3150.00 l 491.55 3044.75 l 545.25 2937.69 l 597.96 2829.63 l clp gs 0.00 setgray ef gr gs col-1 s gr % Interp Spline n 3075 600 m 2317.07 496.79 1979.57 515.54 1725 675 curveto 1531.15 796.43 1313.72 1090.98 1350 1350 curveto 1376.16 1536.79 1507.41 1668.04 1875 1875 curveto gs col-1 s gr n 1515.61 1534.94 m 1875.00 1875.00 l 1397.86 1744.08 l 1457.24 1640.01 l 1515.61 1534.94 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 1200 m gs 1 -1 sc (Preorder successors of) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 1614 m gs 1 -1 sc (various nodes. Thick lines) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 2028 m gs 1 -1 sc (show the search path for the ) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 2442 m gs 1 -1 sc (successor.) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3150 526 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1875 1726 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 975 2926 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2475 2926 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4950 1726 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4200 3001 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 4126 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6225 3076 m gs 1 -1 sc (s) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7275 4276 m gs 1 -1 sc (t) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8100 5326 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 600 3976 m gs 1 -1 sc (NIL) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8025 6151 m gs 1 -1 sc (NIL) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7500 3000 m gs 1 -1 sc (Some of the threads are omitted) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 538 961 a Fe(Figure)14 b(2:)k(Preorder)e(successors)g(in)e(a)f (threaded)i(tree)-30 1094 y(ha)o(v)o(e)f(a)f(paren)o(t.)19 b(Ho)o(w)o(ev)o(er)14 b(if)f(the)i(algorithm)c(returns)k(a)f(no)q(de)g (then)h(this)f(is)g(the)g(real)g(paren)o(t.)35 1235 y Fd(\(*)22 b(assume)e(case)h(1)h(holds)f(*\))35 1285 y(P=Node;)35 1335 y(While)g(RC\(P\))g(is)g(not)g(a)h(thread)f(do)101 1385 y(P=RC\(P\);)35 1484 y(if)h(\()f(RC\(P\)<>)g(NIL)g(and)g(P)h(is)f (the)g(parent)g(of)g(N\))g(then)101 1534 y(return)f(P;)35 1634 y(\(*)i(RC\(P\))f(was)g(NIL)g(or)g(it)h(wasn;t)e(the)h(correct)g (parent.)101 1683 y(Now)g(assume)f(case)h(2)h(holds*\))35 1783 y(P=Node;)35 1833 y(While)f(LC\(P\))g(is)g(not)g(a)h(thread)f(do) 101 1883 y(P=LC\(P\);)35 1982 y(if)h(\(LC\(P\)==NIL\))d(then)195 b(\(*)22 b(Node)f(was)g(the)g(root)g(*\))101 2032 y(return)f(NIL)35 2082 y(else)101 2132 y(return)g(LC\(P\);)-30 2223 y Fg(Answ)n(er)g(2) -30 2323 y Ff(a-)14 b Fe(There)h(are)f(10)9 b(+)h(9)f(+)g(9)g(+)h(8)e (+)i(8)h(=)h(44)h(nonzero)i(elemen)o(ts)f(in)f(a)h(10x10)f(2-banded)g (arra)o(y)m(.)-30 2422 y Ff(b-)g Fe(The)i(n)o(um)o(b)q(er)e(of)g (nonzero)i(elemen)o(ts:)32 2472 y(2)9 b Fc(\003)g Fe([)p Fb(n)g Fe(+)g(\()p Fb(n)h Fe(+)f(1\))g(+)h(\()p Fb(n)f Fe(+)h(2\))f(+)g Fb(:::)f Fe(+)i(\()p Fb(n)f Fc(\000)g Fb(m)p Fe(\)])h Fc(\000)f Fb(n)-30 2522 y(or)o(:::)-30 2572 y Fe(2)p Fb(nm)g Fe(+)h Fb(n)f Fc(\000)h Fb(m)215 2557 y Fa(2)243 2572 y Fc(\000)f Fb(m)-30 2671 y Ff(c-)k Fe(One)h(solution)f(migh)o(t)e(b)q(e)i(\014rst)h(allo)q(cate)f(the)h (elemen)o(ts)f(on)g(the)h(diagonal,)d(and)i(then)h(allo)q(cate)e(t)o(w) o(o)h(bands)h(that)f(are)g(near)-30 2721 y(the)h(diagonal.)j(Eac)o(h)d (of)f(these)i(diagonals)e(con)o(tain)g(\(n-1\))h(elemen)o(ts.)j(After)e (this)f(second)h(pair)e(of)g(bands)h(are)h(allo)q(cated.)i(So)965 2855 y(2)p eop %%Page: 3 3 3 2 bop -30 162 a Fe(items)11 b(closer)j(to)e(the)h(diagonal)d(will)h (b)q(e)i(stored)g(b)q(efore)g(other)g(items.)k(See)c(Figure)25 b(3.)17 b(The)c(form)o(ula)d(\(index)i(to)g(the)h(memory)-30 211 y(lo)q(cation)g(assuming)f(the)j(base)f(is)g(0\))g(is)g(as)f(follo) o(ws:)-30 261 y(Arra)o(y)h Fb(A)g Fe(is)g(an)f Fb(n)d Fc(\002)f Fb(n)14 b(k)c Fc(\000)f Fb(banded)k Fe(arra)o(y)m(,)g(and)h (w)o(e)g(w)o(an)o(t)f(to)h(access)i(elemen)o(t)d Fb(A)p Fe([)p Fb(i;)7 b(j)r Fe(])p Fb(:M)18 b Fe(represen)o(ts)e(the)f(memory) m(.)-30 361 y(if)e(\()p Fb(i)f Fe(=)g Fb(j)r Fe(\))i(then)h Fb(A)p Fe([)p Fb(i;)7 b(j)r Fe(])k(=)h Fb(M)5 b Fe([)p Fb(i)j Fc(\000)i Fe(1])-30 411 y(if)j(\()p Fb(i)f(<)g(j)r Fe(\))i(then)h Fb(A)p Fe([)p Fb(i;)7 b(j)r Fe(])k(=)h Fb(M)5 b Fe([\(2)j Fc(\002)i Fb(n)f Fc(\000)g Fb(j)j Fe(+)d Fb(i)h Fe(+)f(1\))h Fc(\002)f Fe(\()p Fb(j)j Fc(\000)d Fb(i)p Fe(\))h Fc(\000)g Fb(n)f Fe(+)g Fb(i)h Fc(\000)f Fe(1])-30 460 y(if)k(\()p Fb(i)f(>)g(j)r Fe(\))i(then)h Fb(A)p Fe([)p Fb(i;)7 b(j)r Fe(])k(=)h Fb(M)5 b Fe([\(2)j Fc(\002)i Fb(n)f Fc(\000)g Fb(i)h Fe(+)f Fb(j)r Fe(\))h Fc(\002)g Fe(\()p Fb(i)f Fc(\000)h Fb(j)r Fe(\))g(+)f Fb(j)j Fc(\000)d Fe(1])225 560 y 23681433 18945146 -1841889 9801482 42166108 42297671 startTexFig 225 560 a %%BeginDocument: array.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -62.5 745.0 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 15.000 slw % Polyline n 602 9002 m 10202 9002 l 10202 9602 l 602 9602 l clp gs col-1 s gr % Polyline n 1202 9002 m 1202 9602 l gs col-1 s gr % Polyline n 1802 9002 m 1802 9602 l gs col-1 s gr % Polyline n 2402 9002 m 2402 9602 l gs col-1 s gr % Polyline n 3002 9002 m 3002 9602 l gs col-1 s gr % Polyline n 3602 9002 m 3602 9602 l gs col-1 s gr % Polyline n 4202 9002 m 4202 9602 l gs col-1 s gr % Polyline n 4802 9002 m 4802 9602 l gs col-1 s gr % Polyline n 5402 9002 m 5402 9602 l gs col-1 s gr % Polyline n 6002 9002 m 6002 9602 l gs col-1 s gr % Polyline n 6602 9002 m 6602 9602 l gs col-1 s gr % Polyline n 7202 9002 m 7202 9602 l gs col-1 s gr % Polyline n 9602 9002 m 9602 9602 l gs col-1 s gr % Polyline n 9002 9002 m 9002 9602 l gs col-1 s gr % Polyline n 8402 9002 m 8402 9602 l gs col-1 s gr % Polyline n 5402 8702 m 5402 9902 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2027 9377 m gs 1 -1 sc (2) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1427 9377 m gs 1 -1 sc (1) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 827 9377 m gs 1 -1 sc (0) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2627 9377 m gs 1 -1 sc (3) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3227 9377 m gs 1 -1 sc (4) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3827 9377 m gs 1 -1 sc (5) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4427 9377 m gs 1 -1 sc (6) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5027 9377 m gs 1 -1 sc (7) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5627 9377 m gs 1 -1 sc (8) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6227 9377 m gs 1 -1 sc (9) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6677 9377 m gs 1 -1 sc (10) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8552 9377 m gs 1 -1 sc (31) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9152 9377 m gs 1 -1 sc (32) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9752 9377 m gs 1 -1 sc (33) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7577 9302 m gs 1 -1 sc (...) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 601 8626 m gs 1 -1 sc (Allocation in the memory) col-1 show gr % Polyline n 1200 2100 m 6000 2100 l 6000 6900 l 1200 6900 l clp gs col-1 s gr % Polyline n 3600 2100 m 3600 6900 l gs col-1 s gr % Polyline n 1200 4500 m 6000 4500 l gs col-1 s gr % Polyline n 1200 5700 m 6000 5700 l gs col-1 s gr % Polyline n 1200 6300 m 6000 6300 l gs col-1 s gr % Polyline n 1200 5100 m 6000 5100 l gs col-1 s gr % Polyline n 1200 2700 m 6000 2700 l gs col-1 s gr % Polyline n 1200 3900 m 6000 3900 l gs col-1 s gr % Polyline n 1200 3300 m 6000 3300 l gs col-1 s gr % Polyline n 2400 2100 m 2400 6900 l gs col-1 s gr % Polyline n 3000 2100 m 3000 6900 l gs col-1 s gr % Polyline n 4800 2100 m 4800 6900 l gs col-1 s gr % Polyline n 5400 2100 m 5400 6900 l gs col-1 s gr % Polyline n 4200 2100 m 4200 6900 l gs col-1 s gr % Polyline n 1800 2100 m 1800 6900 l gs col-1 s gr % Polyline n 4500 6900 m 5700 8100 l 5700 8100 l gs col-1 s gr % Polyline n 5100 6900 m 6000 7800 l gs col-1 s gr % Polyline n 6000 6900 m 6300 7200 l gs col-1 s gr % Polyline n 6000 6000 m 6900 6900 l gs col-1 s gr % Polyline n 6000 5400 m 6900 6300 l gs col-1 s gr % Polyline n 6300 7200 m 6450 7350 l gs col-1 s gr % Polyline n 6900 6300 m 7200 6600 l gs col-1 s gr % Interp Spline n 9000 5550 m 9315.19 5621.93 9446.44 5678.18 9525 5775 curveto 9735.39 6034.29 9812.55 6595.22 9750 6900 curveto 9670.60 7286.86 9354.96 7925.49 8925 8100 curveto 8473.34 8283.32 7764.08 7981.47 7425 7800 curveto 7407.37 7790.56 7388.62 7771.81 7350 7725 curveto gs col-1 s gr n 7456.45 7948.31 m 7350.00 7725.00 l 7549.02 7871.94 l 7503.24 7910.63 l 7456.45 7948.31 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1425 1875 m gs 1 -1 sc (1) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2025 1875 m gs 1 -1 sc (2) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 1875 m gs 1 -1 sc (3) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3225 1875 m gs 1 -1 sc (4) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 1875 m gs 1 -1 sc (5) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4425 1875 m gs 1 -1 sc (6) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5025 1875 m gs 1 -1 sc (7) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5625 1875 m gs 1 -1 sc (8) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 2550 m gs 1 -1 sc (1) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 3075 m gs 1 -1 sc (2) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 3675 m gs 1 -1 sc (3) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 4275 m gs 1 -1 sc (4) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 4875 m gs 1 -1 sc (5) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 5475 m gs 1 -1 sc (6) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 6075 m gs 1 -1 sc (7) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 6675 m gs 1 -1 sc (8) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7200 3900 m gs 1 -1 sc (8x8 2-banded array) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1425 2475 m gs 1 -1 sc (0) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1950 3075 m gs 1 -1 sc (1) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 3675 m gs 1 -1 sc (2) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3225 4275 m gs 1 -1 sc (3) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 4875 m gs 1 -1 sc (4) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4425 5475 m gs 1 -1 sc (5) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5025 6075 m gs 1 -1 sc (6) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5625 6675 m gs 1 -1 sc (7) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2025 2475 m gs 1 -1 sc (8) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 3075 m gs 1 -1 sc (9) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3075 3675 m gs 1 -1 sc (10) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3750 4275 m gs 1 -1 sc (11) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4275 4875 m gs 1 -1 sc (12) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4875 5475 m gs 1 -1 sc (13) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5475 6075 m gs 1 -1 sc (14) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1275 3075 m gs 1 -1 sc (15) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1875 3675 m gs 1 -1 sc (16) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2475 4275 m gs 1 -1 sc (17) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3075 4875 m gs 1 -1 sc (18) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3750 5475 m gs 1 -1 sc (19) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4275 6075 m gs 1 -1 sc (20) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4950 6675 m gs 1 -1 sc (21) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2550 2475 m gs 1 -1 sc (22) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3750 3675 m gs 1 -1 sc (24) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4350 4275 m gs 1 -1 sc (25) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4950 4875 m gs 1 -1 sc (26) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5550 5475 m gs 1 -1 sc (27) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1350 3675 m gs 1 -1 sc (28) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1950 4275 m gs 1 -1 sc (29) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2550 4875 m gs 1 -1 sc (30) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3150 5475 m gs 1 -1 sc (31) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3750 6075 m gs 1 -1 sc (32) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4350 6675 m gs 1 -1 sc (33) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3150 3075 m gs 1 -1 sc (23) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7650 5175 m gs 1 -1 sc (Allocation order of the ) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7650 5589 m gs 1 -1 sc (blocks:) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6525 7650 m gs 1 -1 sc (1) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7050 7125 m gs 1 -1 sc (2) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6150 8025 m gs 1 -1 sc (3) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7350 6750 m gs 1 -1 sc (4) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5775 8400 m gs 1 -1 sc (5) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 421 1851 a Fe(Figure)14 b(3:)k(Con)o(tiguous)13 b(storage)i(allo)q (cation)d(for)h(a)h(k-banded)g(arra)o(y)32 1959 y Fg(Answ)n(er)20 b(3:)-30 2059 y Ff(a-)14 b Fe(See)h(Figure)28 b(4.)-30 2158 y Ff(b-)13 b Fe(See)i(Figure)28 b(5.)32 2308 y Fg(Answ)n(er)20 b(4:)-30 2407 y Ff(a)c(and)f(b-)f Fe(See)g(Figure)28 b(6.)965 2855 y(3)p eop %%Page: 4 4 4 3 bop 300 264 a 21313290 14208860 -3749560 7893811 44073779 44139560 startTexFig 300 264 a %%BeginDocument: splay.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -70.5 777.5 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 7.500 slw % Ellipse n 9900 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 9450 5700 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 9750 5025 m 9525 5475 l gs 0.75 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9750 4575 m gs 1 -1 sc (t) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9375 5400 m gs 1 -1 sc (s) col-1 show gr % Polyline n 4426 2926 m 5851 2926 l gs 0.75 setgray ef gr gs col-1 s gr n 5611.00 2866.00 m 5851.00 2926.00 l 5611.00 2986.00 l 5611.50 2926.50 l 5611.00 2866.00 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3976 2476 m gs 1 -1 sc (double rotation) col-1 show gr 7.500 slw % Ellipse n 4203 9828 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5028 8928 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3678 10728 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4728 10728 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 4878 9078 m 4353 9678 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4053 9978 m 3753 10503 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4353 9978 m 4653 10503 l gs 0.75 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4953 8628 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4053 9528 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4878 10428 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3453 10428 m gs 1 -1 sc (a) col-1 show gr 7.500 slw % Ellipse n 6228 9903 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5703 10728 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 6078 10053 m 5778 10578 l 5853 10578 l gs 0.75 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6078 9603 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5628 10428 m gs 1 -1 sc (n) col-1 show gr 7.500 slw % Ellipse n 7577 8927 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7127 9752 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 7427 9077 m 7202 9527 l gs 0.75 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7427 8627 m gs 1 -1 sc (t) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7052 9452 m gs 1 -1 sc (s) col-1 show gr % Polyline n 3452 7728 m 4877 7728 l gs 0.75 setgray ef gr gs col-1 s gr n 4637.00 7668.00 m 4877.00 7728.00 l 4637.00 7788.00 l 4637.50 7728.50 l 4637.00 7668.00 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3002 7278 m gs 1 -1 sc (double rotation) col-1 show gr 7.500 slw % Ellipse n 6301 8026 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7801 7426 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 5251 9001 m 6076 9751 l gs col-1 s gr % Polyline n 5176 8776 m 6076 8101 l gs col-1 s gr % Polyline n 6526 7951 m 7576 7501 l gs col-1 s gr % Polyline n 6451 8176 m 7426 8776 l 7426 8776 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6226 7651 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7726 7051 m gs 1 -1 sc (u) col-1 show gr % Arc n 3382.59 4716.81 m 3300.00 4950.00 l 3263.13 4705.38 l 3323.36 4711.59 l 3382.59 4716.81 l clp gs 0.00 setgray ef gr gs col-1 s gr n 3960.33 5013.18 663.34 54.02 -174.53 arcn gs col-1 s gr 7.500 slw % Ellipse n 9601 3151 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 10426 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 975 3150 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1800 2250 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 450 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1500 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3375 3150 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2775 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2250 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4200 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4875 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5475 5625 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7201 3151 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 8026 2251 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6676 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7726 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 9001 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 8476 4876 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 8251 2326 m 9451 3001 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 9451 3301 m 9076 3901 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 9751 3301 m 10276 3901 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1650 2400 m 1125 3000 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 825 3300 m 525 3825 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1125 3300 m 1425 3825 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2025 2325 m 3225 3000 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3225 3300 m 2850 3900 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3525 3300 m 4050 3900 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4350 4200 m 4725 4725 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 5025 5025 m 5400 5475 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2625 4200 m 2325 4725 l 2400 4725 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 10275 4200 m 9975 4650 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4725 3975 m 5250 3975 l gs col-1 s gr n 4965.00 4035.00 m 4725.00 3975.00 l 4965.00 3915.00 l 4965.50 3975.50 l 4965.00 4035.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 5400 4800 m 5925 4800 l gs col-1 s gr n 5640.00 4860.00 m 5400.00 4800.00 l 5640.00 4740.00 l 5640.50 4800.50 l 5640.00 4860.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 5925 5700 m 6450 5700 l gs col-1 s gr n 6165.00 5760.00 m 5925.00 5700.00 l 6165.00 5640.00 l 6165.50 5700.50 l 6165.00 5760.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 8700 2175 m 9225 2175 l gs col-1 s gr n 8940.00 2235.00 m 8700.00 2175.00 l 8940.00 2115.00 l 8940.50 2175.50 l 8940.00 2235.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 10050 3075 m 10575 3075 l gs col-1 s gr n 10290.00 3135.00 m 10050.00 3075.00 l 10290.00 3015.00 l 10290.50 3075.50 l 10290.00 3135.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 10950 4050 m 11475 4050 l gs col-1 s gr n 11190.00 4110.00 m 10950.00 4050.00 l 11190.00 3990.00 l 11190.50 4050.50 l 11190.00 4110.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 7876 2401 m 7351 3001 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7051 3301 m 6751 3826 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7351 3301 m 7651 3826 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 8851 4201 m 8551 4726 l 8626 4726 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 8175 7425 m 9675 7425 l gs col-1 s gr n 8415.00 7485.00 m 8175.00 7425.00 l 8415.00 7365.00 l 8415.50 7425.50 l 8415.00 7485.00 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9526 2851 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1725 1950 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 2850 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1650 3750 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 225 3750 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3300 2850 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 3750 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4425 3825 m gs 1 -1 sc (s) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5100 4725 m gs 1 -1 sc (t) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5700 5400 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2175 4575 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 10350 3675 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7951 1951 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7051 2851 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7876 3751 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6451 3751 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8851 3751 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8401 4576 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8775 7200 m gs 1 -1 sc (u appears at the root) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 694 1256 a Fe(Figure)14 b(4:)k(Spla)o(y)13 b(op)q(eration)h(on)g(u)300 1586 y 21313290 14208860 -3617996 7893811 43876433 44139560 startTexFig 300 1586 a %%BeginDocument: avl.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -68.0 777.5 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 7.500 slw % Ellipse n 9601 3151 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 10426 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7201 3151 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 8026 2251 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6676 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7726 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 9001 4051 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 8476 4876 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 10950 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 11625 5550 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 8251 2326 m 9451 3001 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 9451 3301 m 9076 3901 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 9751 3301 m 10276 3901 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7876 2401 m 7351 3001 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7051 3301 m 6751 3826 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7351 3301 m 7651 3826 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 8851 4201 m 8551 4726 l 8626 4726 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 10575 4200 m 10875 4650 l gs col-1 s gr % Polyline n 11100 5025 m 11475 5400 l gs col-1 s gr 7.500 slw % Polyline [150.0] 0 setdash n 12225 5925 m 10594 3034 l 8906 5891 l clp gs col-1 s gr [] 0 setdash /AvantGarde-Demi findfont 360.00 scalefont setfont 9526 2851 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7951 1951 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7051 2851 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7876 3751 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6451 3751 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8851 3751 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8401 4576 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 11625 5250 m gs 1 -1 sc (w) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 11100 4650 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 10575 3750 m gs 1 -1 sc (s) col-1 show gr % Arc n 3062.86 5312.22 m 3150.00 5400.00 l 3031.80 5363.55 l 3047.83 5338.38 l 3062.86 5312.22 l clp gs 0.00 setgray ef gr gs col-1 s gr [100.0] 0 setdash n 2714.93 6119.14 840.50 177.90 -58.83 arc gs col-1 s gr [] 0 setdash % Ellipse n 975 3150 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1800 2250 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 450 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 1500 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 3375 3150 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2775 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 2250 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4200 4050 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4875 4875 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4125 5400 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7127 9002 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7952 9902 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4727 9002 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5552 8102 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 4202 9902 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 5252 9902 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6527 9902 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 6002 10727 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 8476 10726 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr % Ellipse n 7350 10725 212 212 0 360 DrawEllipse gs 0.75 setgray ef gr gs col-1 s gr 15.000 slw % Polyline n 1650 2400 m 1125 3000 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 825 3300 m 525 3825 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 1125 3300 m 1425 3825 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2025 2325 m 3225 3000 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3225 3300 m 2850 3900 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 3525 3300 m 4050 3900 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4350 4200 m 4725 4725 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 2625 4200 m 2325 4725 l 2400 4725 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline [150.0] 0 setdash n 4650 4950 m 4275 5250 l gs col-1 s gr [] 0 setdash % Polyline [150.0] 0 setdash n 4425 5475 m 5250 5475 l gs col-1 s gr [] 0 setdash n 5010.00 5415.00 m 5250.00 5475.00 l 5010.00 5535.00 l 5010.50 5475.50 l 5010.00 5415.00 l clp gs 0.00 setgray ef gr gs col-1 s gr 7.500 slw % Polyline [100.0] 0 setdash n 6075 5775 m 4314 3109 l 2886 5966 l clp gs col-1 s gr [] 0 setdash 15.000 slw % Polyline n 4426 2926 m 5851 2926 l gs 0.75 setgray ef gr gs col-1 s gr n 5611.00 2866.00 m 5851.00 2926.00 l 5611.00 2986.00 l 5611.50 2926.50 l 5611.00 2866.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 750 8250 m 2175 8250 l gs 0.75 setgray ef gr gs col-1 s gr n 1935.00 8190.00 m 2175.00 8250.00 l 1935.00 8310.00 l 1935.50 8250.50 l 1935.00 8190.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 5777 8177 m 6977 8852 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 6977 9152 m 6602 9752 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 7277 9152 m 7802 9752 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 5402 8252 m 4877 8852 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4577 9152 m 4277 9677 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 4877 9152 m 5177 9677 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 6377 10052 m 6077 10577 l 6152 10577 l gs 0.75 setgray ef gr gs col-1 s gr % Polyline n 8101 10051 m 8401 10501 l gs col-1 s gr % Polyline n 7800 10050 m 7500 10500 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1725 1950 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 825 2850 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1650 3750 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 225 3750 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3300 2850 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2625 3750 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4425 3825 m gs 1 -1 sc (s) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2175 4575 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5100 4650 m gs 1 -1 sc (w) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 5100 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5475 5550 m gs 1 -1 sc (inserted) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 1050 6300 m gs 1 -1 sc (needs balancing) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3976 2476 m gs 1 -1 sc (rotation\(right\)) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 750 7800 m gs 1 -1 sc (rotation\(left\)) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7052 8702 m gs 1 -1 sc (r) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5477 7802 m gs 1 -1 sc (h) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4577 8702 m gs 1 -1 sc (d) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5402 9602 m gs 1 -1 sc (e) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3977 9602 m gs 1 -1 sc (a) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6377 9602 m gs 1 -1 sc (o) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5927 10427 m gs 1 -1 sc (n) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7125 10425 m gs 1 -1 sc (s) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7950 9525 m gs 1 -1 sc (u) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8700 10500 m gs 1 -1 sc (w) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 8100 7950 m gs 1 -1 sc (The tree is now balanced) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 643 2577 a Fe(Figure)g(5:)j(Insertion)e(in)o(to)e(an)h(A)-5 b(VL)14 b(tree)965 2855 y(4)p eop %%Page: 5 5 5 4 bop 75 175 a 28417720 37890293 -6380830 -18813583 46705049 70846955 startTexFig 75 175 a %%BeginDocument: 23tree.ps /$F2psDict 200 dict def $F2psDict begin $F2psDict /mtrx matrix put /col-1 {} def /col0 {0.000 0.000 0.000 srgb} bind def /col1 {0.000 0.000 1.000 srgb} bind def /col2 {0.000 1.000 0.000 srgb} bind def /col3 {0.000 1.000 1.000 srgb} bind def /col4 {1.000 0.000 0.000 srgb} bind def /col5 {1.000 0.000 1.000 srgb} bind def /col6 {1.000 1.000 0.000 srgb} bind def /col7 {1.000 1.000 1.000 srgb} bind def /col8 {0.000 0.000 0.560 srgb} bind def /col9 {0.000 0.000 0.690 srgb} bind def /col10 {0.000 0.000 0.820 srgb} bind def /col11 {0.530 0.810 1.000 srgb} bind def /col12 {0.000 0.560 0.000 srgb} bind def /col13 {0.000 0.690 0.000 srgb} bind def /col14 {0.000 0.820 0.000 srgb} bind def /col15 {0.000 0.560 0.560 srgb} bind def /col16 {0.000 0.690 0.690 srgb} bind def /col17 {0.000 0.820 0.820 srgb} bind def /col18 {0.560 0.000 0.000 srgb} bind def /col19 {0.690 0.000 0.000 srgb} bind def /col20 {0.820 0.000 0.000 srgb} bind def /col21 {0.560 0.000 0.560 srgb} bind def /col22 {0.690 0.000 0.690 srgb} bind def /col23 {0.820 0.000 0.820 srgb} bind def /col24 {0.500 0.190 0.000 srgb} bind def /col25 {0.630 0.250 0.000 srgb} bind def /col26 {0.750 0.380 0.000 srgb} bind def /col27 {1.000 0.500 0.500 srgb} bind def /col28 {1.000 0.630 0.630 srgb} bind def /col29 {1.000 0.750 0.750 srgb} bind def /col30 {1.000 0.880 0.880 srgb} bind def /col31 {1.000 0.840 0.000 srgb} bind def end save -113.5 1354.5 translate 1 -1 scale /clp {closepath} bind def /ef {eofill} bind def /gr {grestore} bind def /gs {gsave} bind def /l {lineto} bind def /m {moveto} bind def /n {newpath} bind def /s {stroke} bind def /slc {setlinecap} bind def /slj {setlinejoin} bind def /slw {setlinewidth} bind def /srgb {setrgbcolor} bind def /rot {rotate} bind def /sc {scale} bind def /tr {translate} bind def /tnt {dup dup currentrgbcolor 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add 4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb} bind def /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul 4 -2 roll mul srgb} bind def /DrawEllipse { /endangle exch def /startangle exch def /yrad exch def /xrad exch def /y exch def /x exch def /savematrix mtrx currentmatrix def x y tr xrad yrad sc 0 0 1 startangle endangle arc closepath savematrix setmatrix } def /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def /$F2psEnd {$F2psEnteredState restore end} def $F2psBegin 10 setmiterlimit 0.06000 0.06000 sc 15.000 slw % Polyline n 8626 5101 m 10726 5101 l gs col-1 s gr n 10486.00 5041.00 m 10726.00 5101.00 l 10486.00 5161.00 l 10486.50 5101.50 l 10486.00 5041.00 l clp gs 0.00 setgray ef gr gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 9076 4801 m gs 1 -1 sc (Delete E) col-1 show gr % Polyline n 1501 7201 m 2101 7801 l gs col-1 s gr % Polyline n 2101 7201 m 1501 7801 l gs col-1 s gr % Polyline n 3301 4801 m 4501 4801 l 4501 5401 l 3301 5401 l clp gs col-1 s gr % Polyline n 3901 4801 m 3901 5401 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3526 5176 m gs 1 -1 sc (H) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4126 5176 m gs 1 -1 sc (R) col-1 show gr % Polyline n 3301 6001 m 4501 6001 l 4501 6601 l 3301 6601 l clp gs col-1 s gr % Polyline n 3901 6001 m 3901 6601 l gs col-1 s gr % Polyline n 4501 7201 m 5701 7201 l 5701 7801 l 4501 7801 l clp gs col-1 s gr % Polyline n 5101 7201 m 5101 7801 l gs col-1 s gr % Polyline n 3301 13801 m 3901 14401 l gs col-1 s gr % Polyline n 3901 13801 m 3301 14401 l gs col-1 s gr % Polyline n 3302 8702 m 4502 8702 l 4502 9302 l 3302 9302 l clp gs col-1 s gr % Polyline n 3902 8702 m 3902 9302 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3527 9077 m gs 1 -1 sc (H) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4127 9077 m gs 1 -1 sc (R) col-1 show gr % Polyline n 3302 9902 m 4502 9902 l 4502 10502 l 3302 10502 l clp gs col-1 s gr % Polyline n 3902 9902 m 3902 10502 l gs col-1 s gr % Polyline n 4502 11102 m 5702 11102 l 5702 11702 l 4502 11702 l clp gs col-1 s gr % Polyline n 5102 11102 m 5102 11702 l gs col-1 s gr % Polyline n 302 11102 m 1502 11102 l 1502 11702 l 302 11702 l clp gs col-1 s gr % Polyline n 902 11102 m 902 11702 l gs col-1 s gr % Polyline n 4206 26105 m 4806 26705 l gs col-1 s gr % Polyline n 4207 26706 m 5407 26706 l 5407 27306 l 4207 27306 l clp gs col-1 s gr % Polyline n 4807 26706 m 4807 27306 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4431 27080 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5031 27080 m gs 1 -1 sc (Q) col-1 show gr % Polyline n 4205 22204 m 4805 22804 l gs col-1 s gr % Polyline n 4206 22805 m 5406 22805 l 5406 23405 l 4206 23405 l clp gs col-1 s gr % Polyline n 4806 22805 m 4806 23405 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4430 23179 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5030 23179 m gs 1 -1 sc (Q) col-1 show gr % Polyline n 4204 18603 m 4804 19203 l gs col-1 s gr % Polyline n 4205 19204 m 5405 19204 l 5405 19804 l 4205 19804 l clp gs col-1 s gr % Polyline n 4805 19204 m 4805 19804 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4429 19578 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5029 19578 m gs 1 -1 sc (Q) col-1 show gr % Polyline n 901 18001 m 1501 18601 l gs col-1 s gr % Polyline n 1501 18001 m 901 18601 l gs col-1 s gr % Arc n 1775.16 10182.75 m 1725.00 10425.00 l 1655.26 10187.65 l 1715.71 10185.70 l 1775.16 10182.75 l clp gs 0.00 setgray ef gr gs col-1 s gr n 2337.50 10400.00 613.01 16.59 177.66 arcn gs col-1 s gr % Arc n 1769.75 22406.70 m 1725.00 22650.00 l 1649.99 22414.26 l 1710.37 22410.98 l 1769.75 22406.70 l clp gs 0.00 setgray ef gr gs col-1 s gr n 1385.71 22671.43 339.96 170.93 -3.61 arc gs col-1 s gr % Ellipse n 9075 8025 270 270 0 360 DrawEllipse gs col-1 s gr % Ellipse n 1200 10200 270 270 0 360 DrawEllipse gs col-1 s gr % Ellipse n 2100 23100 270 270 0 360 DrawEllipse gs col-1 s gr % Polyline n 900 6000 m 1500 6000 l 1500 6600 l 900 6600 l clp gs col-1 s gr % Polyline n 300 7200 m 900 7200 l 900 7800 l 300 7800 l clp gs col-1 s gr % Polyline n 1500 7200 m 2100 7200 l 2100 7800 l 1500 7800 l clp gs col-1 s gr % Polyline n 2700 7200 m 3300 7200 l 3300 7800 l 2700 7800 l clp gs col-1 s gr % Polyline n 6900 6000 m 7500 6000 l 7500 6600 l 6900 6600 l clp gs col-1 s gr % Polyline n 6300 7200 m 6900 7200 l 6900 7800 l 6300 7800 l clp gs col-1 s gr % Polyline n 7500 7200 m 8100 7200 l 8100 7800 l 7500 7800 l clp gs col-1 s gr % Polyline n 3600 7200 m 4200 7200 l 4200 7800 l 3600 7800 l clp gs col-1 s gr % Polyline n 1500 6000 m 3300 5400 l gs col-1 s gr % Polyline n 3900 5400 m 3900 6000 l gs col-1 s gr % Polyline n 4500 5400 m 6900 6000 l gs col-1 s gr % Polyline n 6900 6600 m 6600 7200 l gs col-1 s gr % Polyline n 7500 6600 m 7800 7200 l gs col-1 s gr % Polyline n 4500 6600 m 5100 7200 l gs col-1 s gr % Polyline n 3900 6600 m 3900 7200 l gs col-1 s gr % Polyline n 3300 6600 m 3000 7200 l gs col-1 s gr % Polyline n 1500 6600 m 1800 7200 l gs col-1 s gr % Polyline n 900 6600 m 600 7200 l gs col-1 s gr % Polyline n 2475 11400 m 1650 11400 l gs col-1 s gr n 1890.00 11460.00 m 1650.00 11400.00 l 1890.00 11340.00 l 1890.50 11400.50 l 1890.00 11460.00 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 902 13802 m 1502 13802 l 1502 14402 l 902 14402 l clp gs col-1 s gr % Polyline n 6902 13802 m 7502 13802 l 7502 14402 l 6902 14402 l clp gs col-1 s gr % Polyline n 6302 15002 m 6902 15002 l 6902 15602 l 6302 15602 l clp gs col-1 s gr % Polyline n 7502 15002 m 8102 15002 l 8102 15602 l 7502 15602 l clp gs col-1 s gr % Polyline n 3602 15002 m 4202 15002 l 4202 15602 l 3602 15602 l clp gs col-1 s gr % Polyline n 1502 13802 m 3302 13202 l gs col-1 s gr % Polyline n 3902 13202 m 3902 13802 l gs col-1 s gr % Polyline n 4502 13202 m 6902 13802 l gs col-1 s gr % Polyline n 6902 14402 m 6602 15002 l gs col-1 s gr % Polyline n 7502 14402 m 7802 15002 l gs col-1 s gr % Polyline n 4502 14402 m 5102 15002 l gs col-1 s gr % Polyline n 3902 14402 m 3902 15002 l gs col-1 s gr % Polyline n 901 14401 m 676 15001 l gs col-1 s gr % Polyline n 3903 13803 m 3903 14403 l gs col-1 s gr % Polyline n 3303 12603 m 4503 12603 l 4503 13203 l 3303 13203 l clp gs col-1 s gr % Polyline n 3903 12603 m 3903 13203 l gs col-1 s gr % Polyline n 4503 15003 m 5703 15003 l 5703 15603 l 4503 15603 l clp gs col-1 s gr % Polyline n 5103 15003 m 5103 15603 l gs col-1 s gr % Polyline n 303 15003 m 1503 15003 l 1503 15603 l 303 15603 l clp gs col-1 s gr % Polyline n 903 15003 m 903 15603 l gs col-1 s gr % Polyline n 1800 15000 m 2400 15000 l 2400 15600 l 1800 15600 l clp gs col-1 s gr % Polyline n 1500 14400 m 2100 15000 l gs col-1 s gr % Polyline [150.0] 0 setdash n 3525 13800 m 6825 13200 l gs col-1 s gr [] 0 setdash n 6578.14 13183.90 m 6825.00 13200.00 l 6599.60 13301.96 l 6589.37 13243.43 l 6578.14 13183.90 l clp gs 0.00 setgray ef gr gs col-1 s gr % Polyline n 3300 13800 m 4500 13800 l 4500 14400 l 3300 14400 l clp gs col-1 s gr % Polyline n 901 9901 m 1501 9901 l 1501 10501 l 901 10501 l clp gs col-1 s gr % Polyline n 2701 11101 m 3301 11101 l 3301 11701 l 2701 11701 l clp gs col-1 s gr % Polyline n 6901 9901 m 7501 9901 l 7501 10501 l 6901 10501 l clp gs col-1 s gr % Polyline n 6301 11101 m 6901 11101 l 6901 11701 l 6301 11701 l clp gs col-1 s gr % Polyline n 7501 11101 m 8101 11101 l 8101 11701 l 7501 11701 l clp gs col-1 s gr % Polyline n 3601 11101 m 4201 11101 l 4201 11701 l 3601 11701 l clp gs col-1 s gr % Polyline n 1501 9901 m 3301 9301 l gs col-1 s gr % Polyline n 3901 9301 m 3901 9901 l gs col-1 s gr % Polyline n 4501 9301 m 6901 9901 l gs col-1 s gr % Polyline n 6901 10501 m 6601 11101 l gs col-1 s gr % Polyline n 7501 10501 m 7801 11101 l gs col-1 s gr % Polyline n 4501 10501 m 5101 11101 l gs col-1 s gr % Polyline n 3901 10501 m 3901 11101 l gs col-1 s gr % Polyline n 3301 10501 m 3001 11101 l gs col-1 s gr % Polyline n 900 10500 m 675 11100 l gs col-1 s gr % Polyline n 6905 25505 m 7505 25505 l 7505 26105 l 6905 26105 l clp gs col-1 s gr % Polyline n 6305 26705 m 6905 26705 l 6905 27305 l 6305 27305 l clp gs col-1 s gr % Polyline n 7505 26705 m 8105 26705 l 8105 27305 l 7505 27305 l clp gs col-1 s gr % Polyline n 1505 25505 m 3305 24905 l gs col-1 s gr % Polyline n 4505 24905 m 6905 25505 l gs col-1 s gr % Polyline n 6905 26105 m 6605 26705 l gs col-1 s gr % Polyline n 7505 26105 m 7805 26705 l gs col-1 s gr % Polyline n 3306 24306 m 4506 24306 l 4506 24906 l 3306 24906 l clp gs col-1 s gr % Polyline n 3906 24306 m 3906 24906 l gs col-1 s gr % Polyline n 3602 25502 m 4202 25502 l 4202 26102 l 3602 26102 l clp gs col-1 s gr % Polyline n 3005 26702 m 3605 26702 l 3605 27302 l 3005 27302 l clp gs col-1 s gr % Polyline n 3602 26102 m 3302 26702 l gs col-1 s gr % Polyline n 3902 24902 m 3902 25502 l gs col-1 s gr % Polyline n 901 25501 m 1501 25501 l 1501 26101 l 901 26101 l clp gs col-1 s gr % Polyline n 901 26101 m 601 26701 l gs col-1 s gr % Polyline n 6904 21604 m 7504 21604 l 7504 22204 l 6904 22204 l clp gs col-1 s gr % Polyline n 6304 22804 m 6904 22804 l 6904 23404 l 6304 23404 l clp gs col-1 s gr % Polyline n 7504 22804 m 8104 22804 l 8104 23404 l 7504 23404 l clp gs col-1 s gr % Polyline n 1504 21604 m 3304 21004 l gs col-1 s gr % Polyline n 4504 21004 m 6904 21604 l gs col-1 s gr % Polyline n 6904 22204 m 6604 22804 l gs col-1 s gr % Polyline n 7504 22204 m 7804 22804 l gs col-1 s gr % Polyline n 3305 20405 m 4505 20405 l 4505 21005 l 3305 21005 l clp gs col-1 s gr % Polyline n 3905 20405 m 3905 21005 l gs col-1 s gr % Polyline n 305 22805 m 1505 22805 l 1505 23405 l 305 23405 l clp gs col-1 s gr % Polyline n 905 22805 m 905 23405 l gs col-1 s gr % Polyline n 1802 22802 m 2402 22802 l 2402 23402 l 1802 23402 l clp gs col-1 s gr % Polyline n 1502 22202 m 2102 22802 l gs col-1 s gr % Polyline n 3601 21601 m 4201 21601 l 4201 22201 l 3601 22201 l clp gs col-1 s gr % Polyline n 3004 22801 m 3604 22801 l 3604 23401 l 3004 23401 l clp gs col-1 s gr % Polyline n 3601 22201 m 3301 22801 l gs col-1 s gr % Polyline n 3901 21001 m 3901 21601 l gs col-1 s gr % Polyline n 900 21600 m 1500 21600 l 1500 22200 l 900 22200 l clp gs col-1 s gr % Polyline n 900 22200 m 600 22800 l gs col-1 s gr % Polyline n 6903 18003 m 7503 18003 l 7503 18603 l 6903 18603 l clp gs col-1 s gr % Polyline n 6303 19203 m 6903 19203 l 6903 19803 l 6303 19803 l clp gs col-1 s gr % Polyline n 7503 19203 m 8103 19203 l 8103 19803 l 7503 19803 l clp gs col-1 s gr % Polyline n 1503 18003 m 3303 17403 l gs col-1 s gr % Polyline n 4503 17403 m 6903 18003 l gs col-1 s gr % Polyline n 6903 18603 m 6603 19203 l gs col-1 s gr % Polyline n 7503 18603 m 7803 19203 l gs col-1 s gr % Polyline n 902 18602 m 677 19202 l gs col-1 s gr % Polyline n 3304 16804 m 4504 16804 l 4504 17404 l 3304 17404 l clp gs col-1 s gr % Polyline n 3904 16804 m 3904 17404 l gs col-1 s gr % Polyline n 304 19204 m 1504 19204 l 1504 19804 l 304 19804 l clp gs col-1 s gr % Polyline n 904 19204 m 904 19804 l gs col-1 s gr % Polyline n 1801 19201 m 2401 19201 l 2401 19801 l 1801 19801 l clp gs col-1 s gr % Polyline n 1501 18601 m 2101 19201 l gs col-1 s gr % Polyline n 3600 18000 m 4200 18000 l 4200 18600 l 3600 18600 l clp gs col-1 s gr % Polyline n 3003 19200 m 3603 19200 l 3603 19800 l 3003 19800 l clp gs col-1 s gr % Polyline n 3600 18600 m 3300 19200 l gs col-1 s gr % Polyline n 3900 17400 m 3900 18000 l gs col-1 s gr % Polyline n 900 18000 m 1500 18000 l 1500 18600 l 900 18600 l clp gs col-1 s gr % Polyline n 300 26700 m 900 26700 l 900 27300 l 300 27300 l clp gs col-1 s gr % Polyline n 1500 26700 m 2100 26700 l 2100 27300 l 1500 27300 l clp gs col-1 s gr % Polyline n 1500 26100 m 1800 26700 l gs col-1 s gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1125 6375 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 525 7575 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1725 7575 m gs 1 -1 sc (E) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3525 6375 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4125 6375 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7125 6375 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6525 7575 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7725 7575 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2850 7575 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 7575 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4725 7575 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5325 7575 m gs 1 -1 sc (Q) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 5625 m gs 1 -1 sc (\(E is deleted, then B and D) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 5913 m gs 1 -1 sc (unifies.\)) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 9450 m gs 1 -1 sc (Here a rotation is needed to ) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 9738 m gs 1 -1 sc (fill the previous slot of D.) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 10026 m gs 1 -1 sc (L goes up, H goes to the bucket) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 10314 m gs 1 -1 sc (denoted by circle, and the bucket) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 10602 m gs 1 -1 sc (containing J is attached to) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 8625 10890 m gs 1 -1 sc (H) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 7050 13050 m gs 1 -1 sc (Simply delete this entry.) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4127 14177 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7127 14177 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6527 15377 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7727 15377 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3827 15377 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4727 15377 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5327 15377 m gs 1 -1 sc (Q) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 526 15376 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1051 15376 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4128 12978 m gs 1 -1 sc (R) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1050 14175 m gs 1 -1 sc (H) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3525 12975 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2025 15375 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 1050 16500 m gs 1 -1 sc (Now delete H:) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 6375 16500 m gs 1 -1 sc (Replace H with its successor J and then ) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 6375 16788 m gs 1 -1 sc (delete J.Notice that this causes rotation) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 6375 17076 m gs 1 -1 sc (from BD to old bucket of J.) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3526 10276 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4126 10276 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7126 10276 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6526 11476 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7726 11476 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2851 11476 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3826 11476 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4726 11476 m gs 1 -1 sc (P) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 5326 11476 m gs 1 -1 sc (Q) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 525 11475 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1050 11475 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7130 25880 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6530 27080 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7730 27080 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 529 27079 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4131 24681 m gs 1 -1 sc (R) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3528 24678 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3827 25877 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3227 27077 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7129 21979 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6529 23179 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7729 23179 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 528 23178 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1053 23178 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4130 20780 m gs 1 -1 sc (R) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3527 20777 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3826 21976 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3226 23176 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1050 21975 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7128 18378 m gs 1 -1 sc (U) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 6528 19578 m gs 1 -1 sc (T) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 7728 19578 m gs 1 -1 sc (Z) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 527 19577 m gs 1 -1 sc (B) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1052 19577 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 4129 17179 m gs 1 -1 sc (R) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1051 18376 m gs 1 -1 sc (H) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3526 17176 m gs 1 -1 sc (L) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 2026 19576 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3825 18375 m gs 1 -1 sc (N) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 3225 19575 m gs 1 -1 sc (M) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1125 25875 m gs 1 -1 sc (D) col-1 show gr /AvantGarde-Demi findfont 360.00 scalefont setfont 1650 27075 m gs 1 -1 sc (J) col-1 show gr /AvantGarde-Demi findfont 270.00 scalefont setfont 450 24225 m gs 1 -1 sc (Finally We have:) col-1 show gr showpage $F2psEnd restore %%EndDocument endTexFig 677 2667 a Fe(Figure)14 b(6:)k(Deletion)c(from)e(2-3)h(tree.)965 2855 y(5)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF l clp gs col-1 s gr % Polyline n 905 22805 m 905 23405 l gs col-1 s gr % Polyline n 1802 22802 m 2402 22802 l 2402 23402 l 1802 23402 l clp gs col-1 s gr % Polyline n 1502 22202 m 2102 22802 l gs col-1 s gr % Polyline n 3601 21601 m 4201 21601 l 4201 22201 l 3601 22201 l clp gs col-1 s gr % Polyline n 3lsd/420ppt/exam2.ans010066400011770035271000003300220605220421500141400ustar00lsdwww00003110017552begin 644 ex2.s M)2%04RU!9&]B92TR+C *)25##H@," P(#8Q,B W.3(*)25%;F1#;VUM96YT"YPV5X8VA]3@HO6'M3($Y]0B O5%)[=')A;G-L871E?4X@+VES;',@ M9F%LF4@,3$@-S(@;75L($X@+VAS:7IE(#@N-2 W,@IM=6P@ M3B O;&%N9'!L=7,Y,'MF86QS97UD968@+T!R:6=I;GMIULP(&QA;F1P M;'5S.3![,2 M,7U[+3$@,7T*:69E;'-E(# @," P76-O;F-A='UI9B W,B!2 M97-O;'5T:6]N(&1I=B W,B!64F5S;VQU=&EO;B!D:78@;F5G('-C86QE"FES M;'-[;&%N9'!L=7,Y,'M64F5S;VQU=&EO;B W,B!D:78@=G-I>F4@;75L(# @ M97AC:'U[4F5S;VQU=&EO;B M-S(@9&EV"FAS:7IE(&UU;" P?6EF96QS92!4 M4GUI9B!297-O;'5T:6]N(%9297-O;'5T:6]N('9S:7IE("TW,B!D:78@,2!A M9&0@;75L"E126VUA=')I>"!C=7)R96YT;6%TV1U<"!D=7 @W)O=6YD?6EF?0IF;W)A;&P@&-H77-E=&UA=')I>'U.("] ;&%N9'-C87!E>R]IT-H87)"=6EL M9&5R?4X@+T5N8V]D:6YG($E%($X*96YD(&1U<'LO9F]O('-E=&9O;G1],B!A M2!C;W!Y(&-V>"!.(&QO860@,"!N;B!P=70@+V-TPHO"!&36%T($X@9&8M=&%I;'U"("]D9G-[9&EV("]S M9B!8("]F;G1R>%MS9B P(# @PHQ,C@@8V@M9&%T M82!D=7 @;&5N9W1H(#,@6]F9GMC:"UD871A M(&1U<"!L96YG=&@@,B!S=6(*9V5T(#$R-R!S=6)]0B O8V@M9'A[8V@M9&%T M82!D=7 @;&5N9W1H(#$@7!E("]S=')I;F=T>7!E(&YE>V-T"!G970@4R O0FET36%PV)O<"UH;V]K?6EF("]322!S879E($X@0')I9VEN M"C @,"!M;W9E=&\@+U8@;6%TU-)(')EV5O<"UH;V]K?6EF M?4X@+T!S=&%R='MUF4@6" V-3" P($X@+W)U;&5Y(# @3B O=GLOWU"("]25B!S=&%T=7-D:6-T(&)E9VEN("]PW!O M<"!PV9A;'-E?6EF96QS92!E;F1[>V=S879E(%12 M("TN,2 N,2!44B Q(#$@WMG&-H(')O=6YD(&5X8V@@:71R86YS9F]R;2!M;W9E=&\@ MU,@<"!D M96QT82!A9&0@=&%I;'U"("]B>U,@<"!T86EL?4(@+V-[+30@37T*0B O9'LM M,R!-?4(@+V5[+3(@37U"("]F>RTQ($U]0B O9WLP($U]0B O:'LQ($U]0B O M:7LR($U]0B O:GLS($U]0B O:WL*-"!-?4(@+W=[,"!R;6]V971O?4(@+VQ[ M<" M-"!W?4(@+VU[<" M,R!W?4(@+VY[<" M,B!W?4(@+V][<" M,2!W?4(@ M+W%["G @,2!W?4(@+W)[<" R('=]0B OW @-"!W?4(@ M+WA[,"!3(')M;W9E=&]]0B O>7LS(#(@R]34R!S M879E($Y]0B O96]S>U-3(')ER]H MR]VR]H;R!8 M?4(@+T!V;V9FR]V;R!8?4(@+T!A;F=L97LO86YG(%A]0B O0')W:7L* M,3 @9&EV("]R=VD@6" OR]L;'@@6'U"("] ;&QY M>R]L;'D@6'U"("] =7)X>R]UR]U7!E"B]D:6-T='EP92!E<7MU&QE;F=T:"!G97LO;60@ M;60@9'5P"FQE;F=T:" R,"!A9&0@9&EC="!C;W!Y(&1E9GUI9B!E;F0@;60@ M8F5G:6X@+VQE='1E'!O M"!D969A=6QT;6%TW1R86YS9F]R;7MI=')A;G-F;W)M M(&UO=F5T;WU]>W1R86YS9F]R;7MI=')A;G-F;W)M(&QI;F5T;WT*?7LV("TR M(')O;&P@=')A;G-F;W)M(#8@+3(@WL*8VQOW!O M<"!3(&YE9R!3(%12('!O<" Q.# @W!P M&9L:7 @>69L:7 @;F]T(&%N9'M44B!P;W @<&]