Sammanfattning. Vi diskuterar två enkla strategier för att bygga binära sökträd: "Placera det vanligaste namnet på roten av trädet, sedan fortsätta liknande på underträden "och" välja roten så att utjämna den totala vikten av vänster och höger underträd så mycket som möjligt, sedan fortsätta på liknande sätt på subtres." Även om den förra regeln kan ge extremt ineffektiva sökträd, den senare regeln alltid producerar nästan optimala träd. "En av de populära metoderna för att hämta information med sitt namn är att lagra namnen i ett binärt träd. Vi ges n namn B1, B~..... /3, och 2n+ t frekvenser fll..... ft., ~o..... c% med ~.flt+~ :r t, Här passar frekvensen av mötande namn B t, och 0r i är frekvensen av att stöta på ett namn som ligger mellan B i och Bi+ 1, cr o och 0% har uppenbara tolkningar" [4]. Vi kan alltid anta w.l.o.g, att fli+~i+fli+l =~0 för alla i. Annars kan i-th (eller (i+t)-th) -tangenten lika gärna tas bort. Ett binärt sökträd T är ett träd med n inre noder (noder med två söner), som vi betecknar med cirklar, och n+ t blad, som vi betecknar med kvadrater. Interiör noderna är märkta av Bi i ökande ordning från vänster till höger och bladen är märkta med intervallerna (Bi, Bi+l) i ökande ordning från vänster till höger. Låt b t vara avståndet mellan inre nod B i från roten och låt en t vara avståndet till blad (Bi, Bi+t) från roten. För att hämta ett namn X, bt+ 1 jämförelser krävs om X=B i och en t jämförelser krävs om B i < X < Bi+ 1. Därför definierar vi den viktade sökvägen för träd T som: Knuth [4] ger en algoritm för att bygga ett optimalt binärt sökträd, dvs.. ett träd med minimal viktad stiglängd. Hans algoritm har 0 (n ~) tid komplexitet och 0 (n ~) utrymme komplexitet. Detta är oöverkomligt för de flesta tillämpningar. Han beskriver också två tumregler för att bygga binära sökträd, som båda kan genomföras i 0 (n log n) tid och 0 (n) utrymme (i bilagan vi skissa en sådan genomförande). Nyligen M. Fredman [t] förbättrade på detta och visade en algoritm som fungerar i 0 (n) enheter av tid och rum. Regel I : Placera det vanligaste namnet på roten av trädet, sedan fortsätta likartat på underträden. Regel II : Välj roten för att utjämna den totala vikten av vänster och höger underträd så mycket som möjligt, sedan fortsätta på samma sätt på underträden.
Kurt Mehlhorn fick en snabbare, O(n) tid algoritm, som approximerar det optimala trädet REF.
Nearly optimal binary search trees
{'venue': 'Acta Informatica', 'journal': 'Acta Informatica', 'mag_field_of_study': ['Computer Science', 'Mathematics']}