A Binärt sökträd är en datastruktur som används inom datavetenskap för att organisera och lagra data på ett sorterat sätt. Varje nod i en Binärt sökträd har högst två barn, a vänster barn och a höger barn, med vänster barn som innehåller värden mindre än den överordnade noden och höger barn som innehåller värden större än den överordnade noden. Denna hierarkiska struktur möjliggör effektiv sökande , införande , och radering operationer på data som lagras i trädet.
vyer och tabeller
Binärt sökträd
Introduktion till binär sökning:
- Tillämpningar av BST
- Tillämpning, fördelar och nackdelar med binärt sökträd
Grundläggande funktioner på BST:
- Infogning i binärt sökträd
- Söker i binärt sökträd
- Borttagning i binärt sökträd
- Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order
- Konvertera en normal BST till Balanserad BST
Enkla standardproblem på BST:
- Iterativ sökning i binärt sökträd
- Ett program för att kontrollera om ett binärt träd är BST eller inte
- Konvertering av binärt träd till binärt sökträd
- Hitta noden med lägsta värde i ett binärt sökträd
- Kontrollera om en array representerar Inorder av binärt sökträd eller inte
- Hur avgör man om ett binärt träd är höjdbalanserat?
- Sorterad array till balanserad BST
- Kontrollera om det finns identiska BST utan att bygga träden
- Konvertera BST till Min Heap
- Näst största element i BST
- Lägg till alla större värden till varje nod i en given BST
- Kontrollera om två BST innehåller samma uppsättning element
- Summan av k minsta element i BST
Medium standardproblem på BST:
- Konstruera BST från given förbeställnings-traversal | Set 1
- Sorterad länkad lista till balanserad BST
- Förvandla ett BST till ett större summaträd
- BST till ett träd med summan av alla mindre nycklar
- Konstruera BST från dess givna nivåorderövergång
- Kontrollera om den givna arrayen kan representera nivåordningsgenomgång av binärt sökträd
- Lägsta gemensamma förfader i ett binärt sökträd
- Hitta k:te minsta elementet i BST (Orderstatistik i BST)
- K’th Största elementet i BST med konstant extra utrymme
- Största talet i BST som är mindre än eller lika med N
- Hitta avståndet mellan två noder i ett binärt sökträd
- Största BST i ett binärt träd | Set 2
- Ta bort alla lövnoder från det binära sökträdet
- Inorder efterträdare i binärt sökträd
- Hitta ett par med given summa i BST
- Maximalt element mellan två noder av BST
- Hitta det största BST-underträdet i ett givet binärt träd
- Hitta ett par med given summa i en Balanserad BST
- Två noder i en BST byts ut, korrigera BST
- Hur hanterar man dubbletter i binärt sökträd?
- Bladnoder från förbeställning av ett binärt sökträd (med rekursion)
Hårda standardproblem på BST:
- Konstruera alla möjliga BST:er för nycklar 1 till N
- Konvertera BST på plats till en Min-Heap
- Kontrollera att given matris med storlek n kan representera BST med n nivåer eller inte
- Slå samman två BST:er med begränsat extra utrymme
- K’th Largest Element i BST när modifiering av BST inte är tillåten
- Kontrollera om en given sorterad undersekvens finns i binärt sökträd
- Maximalt unikt element i varje undergrupp av storlek K
- Räkna par från två BST vars summa är lika med ett givet värde x
- Skriv ut BST-nycklar i givet intervall | O(1) Mellanslag
- Beställ föregångare och efterföljare för en given nyckel i BST
- Ta reda på om det finns en triplett i en balanserad BST som adderas till noll
- Ersätt varje element med det minst större elementet till höger
- Räkna inversioner i en array | Set 2 (med självbalanserande BST)
- Bladnoder från förbeställning av ett binärt sökträd
- Minsta möjliga värde för |ai + aj – k| för given array och k.
- Särskilda tvåsiffriga nummer i ett binärt sökträd
- Slå samman två balanserade binära sökträd
Några frågesporter:
- 'Frågesporter' på Binary Search Tree
- 'Frågesporter' om balanserade binära sökträd
Snabblänkar :
- Videor på Binary Search Tree
Rekommenderad:
- Lär dig datastruktur och algoritmer | Handledning för DSA