3.3 Balancerede binære søgetræer
I dette afsnit betragtes en slags binære søgetræer som garanterer logaritmiske køretider. Træerne er næsten perfekt balancerede, således at højden garanteret ikke overstiger \(2 \operatorname{lg} N\).
2-3-søgetræer.
Vi opnår den nødvendige fleksibilitet for at kunne garantere søgertræernes balance ved at tillade knuder at indeholder mere end én nøgle.Definition.
Et 2-3-søgetræ (eller bare 2-3-træ) er et træ, som er enten tomt eller- en 2-knude med en nøgle (samt tilhørende værdi) og to referencer: en venstrereference til et 2-3-søgetræ med mindre nøgler og en højrereference til et 2-3-søgetræ med større nøgler.
- en 3-knude med to nøgler (samt tilhørende værdier) og tre referencer: en venstrereference til et 2-3-søgetræ med mindre nøgler, en midterreference til et 2-3-søgetræ med nøgler mellem knudenøglerne og en højrereference til et 2-3-søgetræ med større nøgler.
- Søgning.
For at afgøre om søgenøglen er i et 2-3-søgetræ, sammenlignes den med
nøglerne i roden.
Hvis søgenøglen er identisk med en af rodnøglerne, lykkes søgningen.
Ellers følges en reference fra roden svarende til det interval, der
kan indeholde søgenøglen, og søgningen fortsætter rekursivt nedad i
det pågældende undertræ.
- Indsættelse i en 2-knude. For at indsætte en ny knude
i et 2-3-søgetræ, er vi fristede at imitere strategien for binære
søgetræer:
udfør en forgæves søgning og hægt den nye knude til et blads
nulreference.
Men dette forstyrrer invarianten om at 2-3-søgetræet skal være
perfekt balanceret.
Hvis den forgæves søgning ender i en 2-knude, er det nemt nok at
opretholde invarianten ved at erstatte knuden med en 3-knude
bestående af 2-knudens nøgle og den nye nøgle.
- Indsættelse i et træ bestående af en enkelt 3-knude.
Antag nu at vi prøver at indsætte i et lillebitte 2-3-søgetræ, som
blot består af en enkelt 3-knude.
Sådan et træ har to nøgler, men ikke plads til den nye nøgle i sin
ene knude.
For at udføre indsættelsen, skaber en midlertidig
4-knude, som altså består af 3 nøgler og 4 referencer.
Herfra er det nemt at konvertere træet til et 2-3-søgetræ bestående
af tre 2-knuder: en rodknude, som indeholder den midterste nøgle, og
hvis venstrereference peger på en bladknude, som indeholder den
mindste nøgle, og hvis højrereference peger på en bladknude, som
indeholder den største nøgle.
- Indsættelse i en 3-knude, hvis forælder er en 2-knude.
Antag nu, at søgningen ender i bunden af træet i en 3-knude, hvis forælder er
en 2-knude.
I dette tilfælde kan vi gøre plads til den nye nøgle og opretholde
balanceringsinvarianten ved at skabe en midlertidig 4-knude som
beskrevet foroven, dele 4-knuden som beskrevet foroven, men flytte
den midterste nøgle til knudens forælder.
- Indsættelse i en 3-knude, hvis forælder er en 3-knude.
Antag nu, at søgningen ender i bunden af træet i en 3-knude, hvis
forælder også er en 3-knude.
Vi skaber igen en midlertidig 4-knude som beskrevet foroven, deler den
og flytter midternøglen op til forælderen.
Nu bliver forælderen selv til en midlertidig 4-knude som indeholder
midternøglen fra det delte 4-knude-barn.
Her foretager vi akkurat samme transformation som et niveau længere
nede og flytter igen en midterste nøgle opad. Denne proces fortsætter
indtil vi møder en 2-knude, som erstattes med en 3-knude og ikke
nødvendiggør flere delinger, eller indtil vi når en 3-knude ved roden.
- Deling af roden. Hvis vi har mødt 3-knuder ved
indsættelse hele vejen op til roden, ender vi midlertidigt med en
4-knude i roden.
Denne deles nu i tre 2-knuder.
- Lokale transformationer. Kernen i indsættelsesstrategien i 2-3-søgetræer er, at alle transformationer er helt lokale: Ingen andre dele af 2-3-søgetræet hverken undersøges eller ændres end dem, der er på vejen fra den nyindsatte knude op til roden. Antallet af referencer, som skal ændres ved hver transformation, er begrænset af en lille konstant. Hver transformation sender en enkelt nøgle op fra en 4-knude til dens forælder og opdaterer de nødvendige referencer, men berører ingen andre dele i træet.
- Globale egenskaber. De lokale transformationer opretholder de globale invarianter at træet opretholder søgetræsordningen og er perfekt balanceret.
Påstand.
Søgning og indsættelse i et 2-3-søgetræ med \(N\) nøgler besøger højst \(\operatorname{lg} N\) knuder.
Vi er dog kun kommet halvvejs i at beskrive en fulstændig implementation. Godt nok ville det være muligt at skrive kode som implementerer transformationerne på datatyper svarende til 2-, 3- og måske sågar 4-knuder, men en sådan direkte repræsentation er meget kringlet at håndtere.
Rød-sorte træer.
Vi betrager nu en enkel repræsentation af 2-3-søgetræer kaldet rød-sorte, binære søgetræer eller bare rød-sorte træer, som leder til en naturlig implementation af indsættelsesstrategien.- Repræsentation af 3-knuder. Grundidén ved
et rød-sort træ er at indkode 2-3-søgetræet som et sædvanligt binært
træ, dvs.
et træ af 2-knuder, som indeholder yderligere information for at
repræsentere 3-knuderne.
We opfatter træets kanter som værende af to typer:
røde kanter forbinder to 2-knuder for at repræsentere en
3-knude, og sorte kanter forbinder knuderne i det
oprindelige 2-3-søgetræ.
Specifikt repræsenterer vi hver 3-knude som to 2-knuder forbundet af
en venstreorienteret, rød kant.
En af fordelene ved at bruge denne repræsentation er at vi kan genbruge opslagsmetoden get() fra almindelige, binære søgetræer uden ændring.
- Ækvivalent definition af rød-sorte træer. Alternativt kan vi definere rød-sorte træer fra bunden: Et rødt-sort træ er et binært søgetræ, hvis kanter er sorte eller røde, og som opfylder følgende betingelser: (1) alle røde kanter er venstrereferencer, (2) ingen knude er forbundet med mere end én rød kant, (3) hver vej fra blad til rod indeholder det samme antal sorte kanter.
- En en-til-en-korrespondence. Given et 2-3-træ kan vi
konstruere det tilsvarende rød-sorte træ ved at konvertere hver knude
som beskrevet foroven.
Givet et rødt-sort træ, kan vi tegne alle røde kanter horizontalt,
hvorved alle nulreferencer får samme afstand fra knuden.
Når vi så kollapser de knuder, der forbindes af røde kanter, opnås
et 2-3-søgetræ.
Implementation.
Programmet RedBlackBST.java implementerer et venstreorienteret rødt-sort træ. Programmet RedBlackLiteBST.java er en enklere udgave, der kun implementerer indsættelse og søgning.
