EN Binært søketre er en datastruktur som brukes i informatikk for å organisere og lagre data på en sortert måte. Hver node i en Binært søketre har høyst to barn, a venstre barn og en Ikke sant barn, med venstre barn som inneholder verdier mindre enn overordnet node og Ikke sant barn som inneholder verdier som er større enn den overordnede noden. Denne hierarkiske strukturen tillater effektiv søker , innsetting , og sletting operasjoner på dataene som er lagret i treet.
Binært søketre
Introduksjon til binært søk:
- Applikasjoner av BST
- Anvendelse, fordeler og ulemper med binært søketre
Grunnleggende operasjoner på BST:
- Innsetting i binært søketre
- Søker i binært søketre
- Sletting i binært søketre
- Binary Search Tree (BST) Traversaler – Inorder, Preorder, Post Order
- Konverter en normal BST til Balansert BST
Enkle standardproblemer på BST:
- Iterativt søk i binært søketre
- Et program for å sjekke om et binært tre er BST eller ikke
- Konvertering av binært tre til binært søketre
- Finn noden med minimumsverdi i et binært søketre
- Sjekk om en matrise representerer Inorder of Binary Search-treet eller ikke
- Hvordan finne ut om et binært tre er høydebalansert?
- Sortert matrise til balansert BST
- Se etter identiske BST-er uten å bygge trærne
- Konverter BST til Min Heap
- Nest største element i BST
- Legg til alle større verdier til hver node i en gitt BST
- Sjekk om to BST-er inneholder samme sett med elementer
- Summen av k minste elementer i BST
Middels standardproblemer på BST:
- Konstruer BST fra gitt forhåndsbestillingsgjennomgang | Sett 1
- Sortert lenket liste til balansert BST
- Transformer et BST til et større sumtre
- BST til et tre med summen av alle mindre nøkler
- Konstruer BST fra dens gitte nivåordregjennomgang
- Sjekk om den gitte matrisen kan representere Nivårekkefølgegjennomgang av binært søketre
- Laveste felles stamfar i et binært søketre
- Finn k-te minste element i BST (Ordrestatistikk i BST)
- K’th Største element i BST med konstant ekstra plass
- Største tall i BST som er mindre enn eller lik N
- Finn avstand mellom to noder i et binært søketre
- Største BST i et binært tre | Sett 2
- Fjern alle bladnoder fra det binære søketreet
- Inorder etterfølger i binært søketre
- Finn et par med gitt sum i BST
- Maksimalt element mellom to noder av BST
- Finn det største BST-undertreet i et gitt binært tre
- Finn et par med gitt sum i en Balansert BST
- To noder av en BST byttes, korriger BST
- Hvordan håndtere duplikater i binært søketre?
- Bladnoder fra forhåndsbestilling av et binært søketre (ved bruk av rekursjon)
Harde standardproblemer på BST:
- Konstruer alle mulige BST-er for nøkler 1 til N
- Konverter BST på stedet til en Min-haug
- Sjekk at gitt matrise med størrelse n kan representere BST på n nivåer eller ikke
- Slå sammen to BST-er med begrenset ekstra plass
- K’th største element i BST når modifikasjon til BST ikke er tillatt
- Sjekk om gitt sortert undersekvens finnes i binært søketre
- Maksimalt unikt element i hver undergruppe av størrelse K
- Tell par fra to BST-er hvis sum er lik en gitt verdi x
- Skriv ut BST-nøkler i gitt område | O(1) Mellomrom
- Bestill forgjenger og etterfølger for en gitt nøkkel i BST
- Finn om det er en triplett i en Balansert BST som legger til null
- Erstatt hvert element med det minste større elementet til høyre
- Tell inversjoner i en matrise | Sett 2 (bruker selvbalanserende BST)
- Bladnoder fra forhåndsbestilling av et binært søketre
- Minimum mulig verdi av |ai + aj – k| for gitt matrise og k.
- Spesielle tosifrede tall i et binært søketre
- Slå sammen to balanserte binære søketrær
Noen quiz:
- 'Quizzer' på binært søketre
- 'Quizzer' på balanserte binære søketrær
Hurtigkoblinger :
- Videoer på binært søketre
Anbefalt:
- Lær datastruktur og algoritmer | DSA veiledning