Abstrakt. Den viktade sökvägen för optimala binära sökträd avgränsas ovan av Y'./3i + 2 a. + H där H är frekvensfördelningens entropi, /3i är den totala vikten av de inre noderna, och aj är den totala vikten av bladen. Denna gräns är bästa möjliga. En linjär tidsalgoritm för att bygga nästan optimala träd beskrivs. Nyckelord, binärt sökträd, komplexitet, genomsnittlig söktid, entropi En av de populära metoderna för att hämta information genom sitt "namn" är att lagra namnen i ett binärt träd. Vi ges n namn B1, Be,, Bn och 2n + 1 frekvenser 1, ", ", fin, aO", ", en med /3i + Y aj 1. Här ji är frekvensen av mötande namn Bi, och aj är frekvensen av att stöta på ett namn som ligger mellan B och B/I, a0 och en har uppenbara tolkningar [4]. Ett binärt sökträd T för namnen B1, B2, Bn är ett träd med n inre noder (noder med två söner), som vi betecknar med cirklar, och n + 1 blad, som vi betecknar med kvadrater. Det är lika med det förväntade antalet jämförelser som behövs för att hämta ett namn. I [4] D. E. Knuth ger en algoritm för att bygga ett optimalt binärt sökträd, d.v.s. ett träd med minimal viktad sökvägslängd. Hans algoritm fungerar i O(n 2) enheter av tid och O(n2) enheter av rymden. I [6] diskuterar vi följande tumregel för att bygga nästan optimala binära sökträd: välj roten för att utjämna den totala vikten av vänster och höger delträd så mycket som möjligt, sedan fortsätter rekursivt. Den regel som presenteras här samt de regler som beskrivs i [6] kan tillämpas för att arbeta i linjär tid och rum ([2]).
Mehlhorn REF gav en O(n) tid algoritm för att bygga ett binärt sökträd som är nära-optimal.
A Best Possible Bound for The Weighted Path Length of Binary Search Trees
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}