EN Binært søgetræ er en datastruktur, der bruges i datalogi til at organisere og lagre data på en sorteret måde. Hver knude i en Binært søgetræ har højst to børn, en venstre barn og en højre barn, med venstre barn, der indeholder værdier, der er mindre end den overordnede node og højre barn, der indeholder værdier, der er større end den overordnede node. Denne hierarkiske struktur giver mulighed for effektiv søger , indskud , og sletning operationer på de data, der er gemt i træet.
Binært søgetræ
Introduktion til binær søgning:
- Anvendelser af BST
- Anvendelse, fordele og ulemper ved binært søgetræ
Grundlæggende handlinger på BST:
- Indsættelse i binært søgetræ
- Søgning i binært søgetræ
- Sletning i binært søgetræ
- Binært søgetræ (BST) Traversals – Inorder, Preorder, Post Order
- Konverter en normal BST til Balanceret BST
Lette standardproblemer på BST:
- Iterativ søgning i binært søgetræ
- Et program til at kontrollere, om et binært træ er BST eller ej
- Konvertering af binært træ til binært søgetræ
- Find noden med minimumsværdi i et binært søgetræ
- Tjek, om et array repræsenterer uorden af binært søgetræ eller ej
- Hvordan bestemmer man, om et binært træ er højdebalanceret?
- Sorteret array til Balanceret BST
- Tjek for identiske BST'er uden at bygge træerne
- Konverter BST til Min Heap
- Næststørste element i BST
- Tilføj alle større værdier til hver node i en given BST
- Tjek, om to BST'er indeholder samme sæt elementer
- Summen af k mindste elementer i BST
Medium standardproblemer på BST:
- Konstruer BST ud fra givet forudbestillingsgennemgang | Sæt 1
- Sorteret linket liste til balanceret BST
- Transformér et BST til et større sumtræ
- BST til et træ med summen af alle mindre nøgler
- Konstruer BST ud fra dens givne rækkefølgegennemgang
- Tjek om det givne array kan repræsentere Level Order Traversal af binært søgetræ
- Laveste fælles forfader i et binært søgetræ
- Find k-te mindste element i BST (Ordrestatistik i BST)
- K’th Største element i BST med konstant ekstra plads
- Største tal i BST, som er mindre end eller lig med N
- Find afstanden mellem to noder i et binært søgetræ
- Største BST i et binært træ | Sæt 2
- Fjern alle bladknuder fra det binære søgetræ
- Inorder efterfølger i binært søgetræ
- Find et par med en given sum i BST
- Maksimalt element mellem to noder af BST
- Find det største BST-undertræ i et givet binært træ
- Find et par med en given sum i en Balanceret BST
- To noder af en BST er byttet om, ret BST
- Hvordan håndterer man dubletter i binært søgetræ?
- Bladknuder fra forudbestilling af et binært søgetræ (ved hjælp af rekursion)
Hårde standardproblemer på BST:
- Konstruer alle mulige BST'er for nøglerne 1 til N
- Konverter BST på stedet til en Min-Heap
- Tjek, at givet array af størrelse n kan repræsentere BST på n niveauer eller ej
- Flet to BST'er med begrænset ekstra plads
- K’th største element i BST, når ændring til BST ikke er tilladt
- Tjek om en given sorteret undersekvens findes i binært søgetræ
- Maksimalt unikt element i hver undergruppe af størrelse K
- Tæl par fra to BST'er, hvis sum er lig med en given værdi x
- Udskriv BST-nøgler i et givet område | O(1) Mellemrum
- Indstil forgænger og efterfølger for en given nøgle i BST
- Find om der er en triplet i en Balanceret BST, der lægger til nul
- Udskift hvert element med det mindst større element til højre
- Tæl inversioner i et array | Sæt 2 (Brug af selvbalancerende BST)
- Bladknuder fra forudbestilling af et binært søgetræ
- Minimum mulig værdi af |ai + aj – k| for givet array og k.
- Særlige tocifrede tal i et binært søgetræ
- Flet to balancerede binære søgetræer
Nogle quizzer:
- 'Quizz' på binært søgetræ
- 'Quizz' om balancerede binære søgetræer
Hurtige links :
- Videoer på binært søgetræ
Anbefalede:
- Lær datastruktur og algoritmer | DSA Tutorial