2–3–4 träd
| 2–3–4 träd | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | träd | |||||||||||||||
| Tidskomplexitet i stor O-notation | ||||||||||||||||
| ||||||||||||||||
Inom datavetenskap är ett 2–3–4-träd (även kallat ett 2–4-träd ) en självbalanserande datastruktur som kan användas för att implementera ordböcker . Siffrorna betyder ett träd där varje nod med barn ( intern nod ) har antingen två, tre eller fyra underordnade noder:
- en 2-nod har ett dataelement , och om intern har två undernoder;
- en 3-nod har två dataelement, och om intern har tre barnnoder;
- en 4-nod har tre dataelement, och om intern har fyra barnnoder;
2-nod
3-nod
4-nod
2–3–4 träd är B-träd av ordning 4; som B-träd i allmänhet kan de söka, infoga och radera i O (log n ) tid. En egenskap hos ett 2–3–4-träd är att alla externa noder är på samma djup.
2–3–4 träd är isomorfa till rödsvarta träd , vilket betyder att de är likvärdiga datastrukturer. Med andra ord, för varje 2–3–4 träd finns det minst ett rött–svart träd med dataelement i samma ordning. Dessutom är insättnings- och raderingsoperationer på 2–3–4 träd som orsakar nodexpansion, splittring och sammanslagning likvärdiga med färgvändning och rotationer i röd-svarta träd. Introduktioner till rödsvarta träd introducerar vanligtvis 2–3–4 träd först, eftersom de är konceptuellt enklare. 2–3–4 träd kan dock vara svåra att implementera i de flesta programmeringsspråk på grund av det stora antalet specialfall som är involverade i operationer på trädet. Rödsvarta träd är enklare att implementera, så de brukar användas istället.
Egenskaper
- Varje nod (blad eller intern) är en 2-nod, 3-nod eller en 4-nod, och innehåller ett, två respektive tre dataelement.
- Alla blad är på samma djup (bottennivån).
- All data hålls i sorterad ordning.
Införande
För att infoga ett värde börjar vi vid roten av 2–3–4-trädet:
- Om den aktuella noden är en 4-nod:
- Ta bort och spara mittvärdet för att få en 3-nod.
- Dela upp den återstående 3-noden i ett par 2-noder (det nu saknade mittvärdet hanteras i nästa steg).
- Om detta är rotnoden (som alltså inte har någon förälder):
- mittvärdet blir den nya rotnoden och trädhöjden ökar med 1. Gå upp i roten.
- Annars trycker du upp det mellersta värdet i föräldranoden. Gå upp till föräldranoden.
- Hitta det barn vars intervall innehåller värdet som ska infogas.
- Om det underordnade är ett löv, infoga värdet i den underordnade noden och avsluta.
- Annars, gå ner i barnet och upprepa från steg 1.
Exempel
För att infoga värdet "25" i detta 2–3–4-träd:
- Börja vid roten (10, 20) och gå ner mot barnet längst till höger (22, 24, 29). (Dess intervall (20, ∞) innehåller 25.)
- Noden (22, 24, 29) är en 4-nod, så dess mittelement 24 skjuts upp i modernoden.
- Den återstående 3-noden (22, 29) delas upp i ett par 2-noder (22) och (29). Gå tillbaka till den nya föräldern (10, 20, 24).
- Gå ner mot barnet längst till höger (29). (Dess intervall (24, ∞) innehåller 25.)
- Nod (29) har inget barn längst till vänster. (Barnet för intervall (24, 29) är tomt.) Stanna här och infoga värdet 25 i denna nod.
Radering
Den enklaste möjligheten att ta bort ett element är att bara lämna elementet där och markera det som "raderat", anpassa de tidigare algoritmerna så att borttagna element ignoreras. Raderade element kan sedan återanvändas genom att skriva över dem när en infogning utförs senare. Nackdelen med denna metod är dock att storleken på trädet inte minskar. Om en stor del av elementen i trädet raderas, kommer trädet att bli mycket större än den nuvarande storleken på de lagrade elementen, och prestandan för andra operationer kommer att påverkas negativt av de raderade elementen.
När detta inte är önskvärt kan följande algoritm följas för att ta bort ett värde från 2–3–4-trädet:
- Hitta elementet som ska raderas.
- Om elementet inte är i en bladnod, kom ihåg dess plats och fortsätt söka tills ett blad, som kommer att innehålla elementets efterföljare, nås. Efterträdaren kan antingen vara den största nyckeln som är mindre än den som ska tas bort, eller den minsta nyckeln som är större än den som ska tas bort. Det är enklast att göra justeringar av trädet uppifrån och ner så att den hittade lövnoden inte är en 2-nod. På så sätt, efter bytet, kommer det inte att finnas en tom lövnod.
- Om elementet är i ett 2-nodsblad, gör bara justeringarna nedan.
Gör följande justeringar när en 2-nod – förutom rotnoden – påträffas på vägen till bladet vi vill ta bort:
- Om ett syskon på vardera sidan av denna nod är en 3-nod eller en 4-nod (som alltså har mer än 1 nyckel), utför en rotation med det syskonen:
- Nyckeln från det andra syskonen närmast denna nod flyttas upp till föräldranyckeln som har utsikt över de två noderna.
- Den överordnade nyckeln flyttas ner till denna nod för att bilda en 3-nod.
- Barnet som ursprungligen var med den roterade syskonnyckeln är nu denna nods extra barn.
- Om föräldern är en 2-nod och syskonen också är en 2-nod, kombinera alla tre elementen för att bilda en ny 4-nod och förkorta trädet. (Denna regel kan bara utlösas om den överordnade 2-noden är roten, eftersom alla andra 2-noder längs vägen kommer att ha modifierats till att inte vara 2-noder. Det är därför "förkorta trädet" här bevarar balansen; detta är också ett viktigt antagande för fusionsoperationen.)
- Om föräldern är en 3-nod eller en 4-nod och alla angränsande syskon är 2-noder, gör en fusionsoperation med föräldern och ett angränsande syskon:
- Det intilliggande syskonet och föräldranyckeln med utsikt över de två syskonnoderna går samman för att bilda en 4-nod.
- Överför syskons barn till denna nod.
När det sökta värdet har nåtts kan det nu placeras på den borttagna postens plats utan problem eftersom vi har sett till att bladnoden har mer än 1 nyckel.
Radering i ett 2–3–4-träd är O(log n), förutsatt att överföring och fusion körs i konstant tid (O(1)).
Parallella operationer
Eftersom 2–3–4 träd i strukturen liknar röd-svarta träd , kan parallella algoritmer för röd-svarta träd tillämpas på 2–3–4 träd också.
Se även
externa länkar
- Algoritmer i aktion, med 2–3–4 trädanimationer
- Vänsterlutande röd-svarta träd – Robert Sedgewick, Princeton University, 2008
- Öppna datastrukturer – Avsnitt 9.1 – 2–4 Träd , Pat Morin
- 2–3–4 Trees: A Visual Introduction, 2017