Ik heb binaire bomen en binair zoeken genoemd in verschillende boeken die ik de laatste tijd heb gelezen, maar aangezien ik nog aan het begin sta van mijn studie informatica, moet ik nog een cursus volgen die echt wordt behandeld algoritmen en datastructuren op een serieuze manier.
Ik heb de typische bronnen (Wikipedia, Google) doorzocht en de meeste beschrijvingen van het nut en de implementatie van (met name) Rood-zwarte bomen komen over als compact en moeilijk te begrijpen. Ik weet zeker dat het voor iemand met de nodige achtergrond volkomen logisch is, maar op dit moment leest het bijna als een vreemde taal.
Dus wat maakt binaire bomen nuttig bij sommige van de veelvoorkomende taken die u tijdens het programmeren uitvoert? Daarnaast, welke bomen gebruik je het liefst (voeg een voorbeeldimplementatie toe) en waarom?
Antwoord 1, autoriteit 100%
Roodzwarte bomen zijn goed voor het creëren van uitgebalanceerde bomen. Het grootste probleem met binaire zoekbomen is dat je ze heel gemakkelijk uit balans kunt brengen. Stel je voor dat je eerste getal een 15 is. Dan worden alle getallen daarna steeds kleiner dan 15. Je hebt dan een boom die erg zwaar is aan de linkerkant en niets aan de rechterkant.
Roodzwarte bomen lossen dat op door je stamboom te dwingen in evenwicht te zijn wanneer je iets invoegt of verwijdert. Het bereikt dit door een reeks rotaties tussen voorouderknooppunten en onderliggende knooppunten. Het algoritme is eigenlijk vrij eenvoudig, hoewel het een beetje lang is. Ik raad je aan om het CLRS (Cormen, Lieserson, Rivest en Stein) leerboek “Introduction to Algorithms” te pakken en je te verdiepen in RB Trees.
De implementatie is ook niet echt zo kort, dus het is waarschijnlijk niet echt het beste om het hier op te nemen. Desalniettemin worden bomen uitgebreidgebruikt voor krachtige apps die toegang tot veel gegevens nodig hebben. Ze bieden een zeer efficiënte manier om knooppunten te vinden, met een relatief kleine overhead van invoeging/verwijdering. Nogmaals, ik raad aan om naar CLRS te kijken om te zien hoe ze worden gebruikt.
Hoewel BST’s mogelijk niet expliciet worden gebruikt, is een voorbeeld van het gebruik van bomen in het algemeen in bijna elk modern RDBMS. Op dezelfde manier wordt uw bestandssysteem vrijwel zeker weergegeven als een soort boomstructuur, en bestanden worden ook op die manier geïndexeerd. Bomen voeden Google. Bomen voeden zowat elke website op internet.
Antwoord 2, autoriteit 31%
Ik wil alleen ingaan op de vraag “Dus wat maakt binaire bomen nuttig bij sommige van de veelvoorkomende taken die u tijdens het programmeren doet?”
Dit is een groot onderwerp waar veel mensen het niet over eens zijn. Sommigen zeggen dat de algoritmen die in een CS-graad worden onderwezen, zoals binaire zoekbomen en gerichte grafieken, niet worden gebruikt in de dagelijkse programmering en daarom niet relevant zijn. Anderen zijn het daar niet mee eens en zeggen dat deze algoritmen en datastructuren de basis vormen voor al onze programmering en dat het essentieel is om ze te begrijpen, zelfs als je er nooit zelf een hoeft te schrijven. Dit filtert in gesprekken over goede sollicitatie- en wervingspraktijken. Steve Yeggeheeft bijvoorbeeld een artikel over interview bij Googlewaarin deze vraag wordt beantwoord. Onthoud dit debat; ervaren mensen zijn het daar niet mee eens.
In typische zakelijke programmering hoeft u misschien niet vaak binaire bomen of zelfs bomen te maken. U zult echter veel klassen gebruiken die intern werken met bomen. Veel van de kernorganisatieklassen in elke taal gebruiken bomen en hashes om gegevens op te slaan en te openen.
Als u betrokken bent bij meer hoogwaardige inspanningen of situaties die enigszins buiten de norm van zakelijke programmering vallen, zult u merken dat bomen een directe vriend zijn. Zoals een andere poster zei, zijn bomen kerngegevensstructuren voor allerlei soorten databases en indexen. Ze zijn nuttig bij datamining en visualisatie, geavanceerde grafische afbeeldingen (2d en 3d) en tal van andere rekenproblemen.
Ik heb binaire bomen gebruikt in de vorm van BSP (binary space partitioning) bomenin 3D grafiek. Ik kijk momenteel weer naar bomen om grote hoeveelheden geogecodeerde gegevens en andere gegevens te sorteren voor informatievisualisatie in Flash/Flex-toepassingen. Wanneer u de grens van de hardware verlegt of op lagere hardwarespecificaties wilt werken, kan het begrijpen en selecteren van het beste algoritme het verschil maken tussen mislukking en succes.
Antwoord 3, autoriteit 20%
Geen van de antwoorden vermeldt waar BST’s precies goed voor zijn.
Als u gewoon wilt zoeken op waarden, dan is een hashtabel veel sneller, O(1) invoegen en opzoeken (afgeschreven in het beste geval).
Een BST is O(log N) lookup waarbij N het aantal knooppunten in de boom is, inserts zijn ook O(log N).
RB- en AVL-bomen zijn belangrijk, net als een ander antwoord dat vanwege deze eigenschap wordt genoemd. Als een gewone BST wordt gemaakt met waarden in de juiste volgorde, zal de boom zo hoog zijn als het aantal ingevoegde waarden, dit is slecht voor de opzoekprestaties.
Het verschil tussen RB- en AVL-bomen zit in de rotaties die nodig zijn om opnieuw te balanceren na een invoeging of verwijdering, AVL-bomen zijn O(log N) voor herbalanceringen, terwijl RB-bomen O(1) zijn. Een voorbeeld van een voordeel van deze constante complexiteit is in het geval dat u een persistente gegevensbron aanhoudt. Als u wijzigingen wilt bijhouden om terug te draaien, moet u O(log N) mogelijke wijzigingen bijhouden met een AVL-boom.
Waarom zou je bereid zijn te betalen voor de kosten van een boom in plaats van een hasjtafel? VOLGORDE! Hash-tabellen hebben geen volgorde, BST’s daarentegen zijn altijd van nature geordend op grond van hun structuur. Dus als je merkt dat je een heleboel gegevens in een array of een andere container gooit en deze later sorteert, kan een BST een betere oplossing zijn.
De ordereigenschap van de structuur geeft u een aantal geordende iteratiemogelijkheden, in-order, depth-first, width-first, pre-order, post-order. Deze iteratie-algoritmen zijn handig in verschillende omstandigheden als je ze wilt opzoeken.
Roodzwarte bomen worden intern gebruikt in bijna elke geordende container met taalbibliotheken, C++ Set en Map, .NET SortedDictionary, Java TreeSet, enz…
Dus bomen zijn erg handig, en je kunt ze heel vaak gebruiken zonder het te weten. U zult hoogstwaarschijnlijk nooit nodigom er zelf een te schrijven, hoewel ik het ten zeerste zou aanbevelen als een interessante programmeeroefening.
Antwoord 4, autoriteit 7%
Roodzwarte bomen en B-bomen worden gebruikt in allerlei soorten permanente opslag; omdat de bomen in evenwicht zijn, worden de prestaties van breedte- en dieptetraversen verminderd.
Bijna alle moderne databasesystemen gebruiken bomen voor gegevensopslag.
Antwoord 5, autoriteit 4%
BST’s laten de wereld draaien, zoals Micheal zei. Als je op zoek bent naar een goede boom om te implementeren, kijk dan eens naar AVL-bomen(Wikipedia ). Ze hebben een balancerende toestand, dus ze zijn gegarandeerd O(logn). Dit soort zoekefficiëntie maakt het logisch om in elk soort indexeringsproces te stoppen. Het enige dat efficiënter zou zijn, zou een hash-functie zijn, maar die worden snel, snel en gehaast lelijk. Ook kom je de Birthday Paradoxtegen (ook bekend als het duivenhokprobleem).
Welk leerboek gebruik je? We gebruikten Datastructuren en analyse in Javavan Mark Allen Weiss. Ik heb het eigenlijk open op mijn schoot terwijl ik dit typ. Het heeft een geweldige sectie over rood-zwarte bomen en bevat zelfs de code die nodig is om alle bomen te implementeren waar het over gaat.
Antwoord 6, autoriteit 4%
Roodzwarte bomen blijven in balans, dus je hoeft niet diep te graven om voorwerpen eruit te halen. De bespaarde tijd maakt RB-bomen O(log()n)) in het SLECHTSTE geval, terwijl ongelukkige binaire bomen in een scheve configuratie kunnen komen en opvragingen in O(n) een slecht geval kunnen veroorzaken. Dit gebeurt wel in de praktijk of op willekeurige data. Dus als u tijdkritische code nodig heeft (database ophalen, netwerkserver enz.), gebruikt u RB-bomen om geordende of ongeordende lijsten/sets te ondersteunen.
Maar RBtrees zijn voor noobs! Als je AI doet en je moet een zoekopdracht uitvoeren, merk je dat je de staatsinformatie veel gebruikt. U kunt een aanhoudende rood-zwart gebruiken om nieuwe toestanden in O(log(n)) te splitsen. Een persistente roodzwarte boom houdt een kopie van de boom bij voor en na een morfologische operatie (insert/delete), maar zonder de hele boom te kopiëren (normaal en O(log(n)) operatie). Ik heb open source een hardnekkige rood-zwarte boom voor java
Antwoord 7, autoriteit 4%
De beste beschrijving van rood-zwarte bomen die ik heb gezien, is die in Cormen, Leisersen en Rivest’s ‘Introduction to Algorithms’. Ik kon het zelfs voldoende begrijpen om er een gedeeltelijk te implementeren (alleen invoegen). Er zijn ook nogal wat applets zoals Dezeop verschillende webpagina’s die het proces animeren en u in staat stellen een grafische weergave van het algoritme te bekijken en door een boomstructuur te stappen.
Antwoord 8, autoriteit 2%
Omdat je vraagt welke boom mensen gebruiken, moet je weten dat een roodzwarte boom in wezen een 2-3-4 B-boom is (d.w.z. een B-boom van orde 4). Een B-tree is nietgelijk aan een binaire tree (zoals gevraagd in uw vraag).
Hieris een uitstekende bron die de initiële abstractie beschrijft die bekend staat als de symmetrische binaire B -boom die later uitgroeide tot de RBtree. Je zou B-trees goed moeten begrijpen voordat het logisch is. Samenvattend: een ‘rode’ link op een roodzwarte boom is een manier om knooppunten weer te geven die deel uitmaken van een B-boomknooppunt (waarden binnen een sleutelbereik), terwijl ‘zwarte’ links knooppunten zijn die verticaal zijn verbonden in een B -boom.
Dus, dit is wat je krijgt als je de regels van een roodzwarte boom vertaalt in termen van een B-boom (ik gebruik het formaat Roodzwarte boomregel=> B Tree-equivalent):
1) Een knoop is rood of zwart. => Een knoop in een b-tree kan deel uitmaken van een knoop, of als een knoop in een nieuw niveau.
2) De wortel is zwart. (Deze regel wordt soms weggelaten, omdat het de analyse niet beïnvloedt) => Het hoofdknooppunt kan worden gezien als een onderdeel van een intern hoofdknooppunt of als een kind van een denkbeeldig bovenliggend knooppunt.
3) Alle bladeren (NIL) zijn zwart. (Alle bladeren hebben dezelfde kleur als de wortel.) => Aangezien een manier om een RB-boom weer te geven is door de bladeren weg te laten, kunnen we dit uitsluiten.
4)Beide kinderen van elke rode knoop zijn zwart. => De kinderen van een interne knoop in een B-boom liggen altijd op een ander niveau.
5) Elk eenvoudig pad van een bepaald knooppunt naar een van de onderliggende bladeren bevat hetzelfde aantal zwarte knooppunten. => Een B-boom wordt in evenwicht gehouden omdat het vereist dat alle bladknopen zich op dezelfde diepte bevinden (vandaar dat de hoogte van een B-boomknoop wordt weergegeven door het aantal zwarte schakels van de wortel naar het blad van een roodzwarte boom)
Er is ook een eenvoudigere ‘niet-standaard’ implementatie door Robert Sedgewick hier: (Hij is de auteur van het boek Algorithmssamen met Wayne)
Antwoord 9, autoriteit 2%
Heel veel warmte hier, maar niet veel licht, dus laten we kijken of we voor wat kunnen zorgen.
Ten eerste, een RB-boom is een associatieve gegevensstructuur, in tegenstelling tot bijvoorbeeld een array, die geen sleutel kan nemen en een bijbehorende waarde kan retourneren, tenzij dat een geheel getal is “sleutel” in een 0 % schaarse index van aaneengesloten gehele getallen. Een array kan ook niet in omvang groeien (ja, ik weet ook van realloc(), maar onder de dekens vereist dat een nieuwe array en vervolgens een memcpy()), dus als je een van deze vereisten hebt, is een array niet voldoende . De geheugenefficiëntie van een array is perfect. Geen afval, maar niet erg slim of flexibel – realloc() niet weerstaan.
Ten tweede, in tegenstelling tot een bsearch() op een array van elementen, die een associatieve gegevensstructuur IS, kan een RB-boom zichzelf dynamisch in omvang laten groeien (EN verkleinen). De bsearch() werkt prima voor het indexeren van een gegevensstructuur van een bekende grootte, die die grootte zal behouden. Dus als je van tevoren niet weet hoe groot je gegevens zijn, of als er nieuwe elementen moeten worden toegevoegd of verwijderd, is er een bsearch() beschikbaar. Bsearch() en qsort() worden beide goed ondersteund in klassieke C en hebben een goede geheugenefficiëntie, maar zijn niet dynamisch genoeg voor veel toepassingen. Ze zijn echter mijn persoonlijke favoriet omdat ze snel en gemakkelijk zijn, en als je niet met realtime apps te maken hebt, zijn ze vaak flexibel genoeg. Bovendien kunt u in C/C++ een array van verwijzingen naar gegevensrecords sorteren, bijvoorbeeld verwijzend naar het struc{}-lid dat u wilt vergelijken, en vervolgens de aanwijzer in de aanwijzerarray herschikken zodat de aanwijzers in volgorde worden gelezen aan het einde van de aanwijzer levert sortering uw gegevens in gesorteerde volgorde op. Het gebruik hiervan met in het geheugen toegewezen gegevensbestanden is extreem geheugenefficiënt, snel en redelijk eenvoudig. Het enige dat u hoeft te doen, is een paar “*”-en aan uw vergelijkingsfunctie(s) toevoegen.
Ten derde, in tegenstelling tot een hashtabel, die ook een vaste grootte moet hebben en niet kan worden gekweekt als deze eenmaal is gevuld, zal een RB-boom automatisch groeien en zichzelf in evenwicht houden om zijn O(log( n)) prestatiegarantie. Vooral als de sleutel van de RB-tree een int is, kan deze sneller zijn dan een hash, want hoewel de complexiteit van een hashtabel O(1) is, kan die 1 een erg dure hash-berekening zijn. De meervoudige 1-clock integers van een tree presteren vaak beter dan 100-clock+ hash-berekeningen, om nog maar te zwijgen van rehashing, en malloc()ing-ruimte voor hash-botsingen en rehashes. Ten slotte, als u ISAM-toegang wilt, evenals sleuteltoegang tot uw gegevens, is een hash uitgesloten, omdat er geen volgorde van de gegevens is die inherent is aan de hashtabel, in tegenstelling tot de natuurlijke volgorde van gegevens in elke boomimplementatie. Het klassieke gebruik van een hash-tabel is om ingetoetste toegang te bieden tot een tabel met gereserveerde woorden voor een compiler. De geheugenefficiëntie is uitstekend.
Vierde, en zeer laag op elke lijst, is de gekoppelde of dubbel gekoppelde lijst, die, in tegenstelling tot een array, natuurlijk het invoegen en verwijderen van elementen ondersteunt, en zoals dat impliceert, het formaat wijzigen . Het is de langzaamste van alle datastructuren, omdat elk element alleen weet hoe het naar het volgende element moet gaan, dus je moet gemiddeld (element_knt/2) links zoeken om je datum te vinden. Het wordt meestal gebruikt waar invoegingen en verwijderingen ergens in het midden van de lijst gebruikelijk zijn, en vooral waar de lijst cirkelvormig is en een duur proces voedt waardoor de tijd om de links te lezen relatief klein is. Mijn algemene RX is om een willekeurig grote array te gebruiken in plaats van een gekoppelde lijst als je enige vereiste is dat deze in omvang kan toenemen. Als je geen grootte meer hebt met een array, kun je een grotere array opnieuw toewijzen. De STL doet dit voor u “onder de dekens” wanneer u een vector gebruikt. Grof, maar potentieel duizenden keren sneller als u geen invoegingen, verwijderingen of ingetoetste zoekopdrachten nodig hebt. De geheugenefficiëntie is slecht, vooral voor dubbel gelinkte lijsten. In feite is een dubbel gekoppelde lijst, waarvoor twee wijzers nodig zijn, precies even inefficiënt als een rood-zwarte boom, terwijl hij GEEN van zijn aantrekkelijke snelle, geordende ophaalkenmerken heeft.
Ten vijfde, bomen ondersteunen veel extra bewerkingen op hun gesorteerde gegevens dan enige andere gegevensstructuur. Veel databasequery’s maken bijvoorbeeld gebruik van het feit dat een reeks bladwaarden eenvoudig kan worden gespecificeerd door hun gemeenschappelijke ouder te specificeren en vervolgens de daaropvolgende verwerking te concentreren op het deel van de boom dat de ouder “bezit”. Het potentieel voor multi-threading dat door deze benadering wordt geboden, zou duidelijk moeten zijn, aangezien slechts een klein deel van de boom hoeft te worden vergrendeld – namelijk alleen de knooppunten waarvan de ouder eigenaar is, en de ouder zelf.
Kortom, bomen zijn de Cadillac van datastructuren. Je betaalt een hoge prijs qua geheugengebruik, maar je krijgt wel een volledig zelfonderhoudende datastructuur. Dit is de reden waarom, zoals aangegeven in andere antwoorden hier, transactiedatabases bijna uitsluitend gebruik maken van bomen.
Antwoord 10
Als je wilt zien hoe een rood-zwarte boom er grafisch uit zou moeten zien, heb ik een implementatie van een rood-zwarte boom gecodeerd die je kunt download hier
Antwoord 11
IME, bijna niemand begrijpt het RB-boomalgoritme. Mensen kunnen de regels voor je herhalen, maar ze begrijpen niet waaromdie regels en waar ze vandaan komen. Ik ben geen uitzondering 🙂
Om deze reden geef ik de voorkeur aan het AVL-algoritme, omdat het gemakkelijk te begrijpen. Als je het eenmaal begrijpt, kun je het helemaal opnieuw coderen, omdat het logisch voor je is.
Antwoord 12
Bomen kunnen snel zijn. Als je een miljoen knooppunten in een gebalanceerde binaire boom hebt, zijn er gemiddeld twintig vergelijkingen nodig om een item te vinden. Als je een miljoen nodes in een gelinkte lijst hebt, zijn er gemiddeld vijfhonderdduizend vergelijkingen nodig om hetzelfde item te vinden.
Als de boom echter uit balans is, kan deze net zo traag zijn als een lijst, enook meer geheugen in beslag nemen. Stel je een boom voor waar de meeste knopen een rechterkind hebben, maar geen linkerkind; het iseen lijst, maar je moet nog steeds geheugenruimte vrijhouden om in het linkerknooppunt te plaatsen als er een verschijnt.
Hoe dan ook, de AVL-boomwas het eerste gebalanceerde binaire boomalgoritme, en het Wikipedia-artikel daarop is vrij duidelijk. Het Wikipedia-artikel over rood-zwarte bomen is eerlijk gezegd zo helder als modder.
Naast binaire bomen, zijn B-Trees bomen waar elk knooppunt veel waarden kan hebben. B-Tree is geeneen binaire boom, het is toevallig de naam ervan. Ze zijn erg handig om het geheugen efficiënt te gebruiken; elk knooppunt van de boom kan zo groot worden gemaakt dat het in één geheugenblok past, zodat je niet (langzaam) tonnen verschillende dingen in het geheugen vindt die naar schijf zijn gepagineerd. Hier is een fenomenaal voorbeeld van de B-Tree.