„Двоично дърво за търсене (BST)“ е дървовидна структура от данни, в която всеки възел има най-много две деца, които се наричат ляво дете и дясно дете, а най-горният възел в дървото се нарича корен. Освен това удовлетворява свойството за двоично търсене, което гласи, че ключът във всеки възел трябва да бъде по-голям или равен на който и да е ключ, съхраняван в лявото поддърво, и по-малък или равен на всеки ключ, съхраняван в дясното поддърво.
Двоичните дървета за търсене позволяват бързо търсене, добавяне и премахване на елементи. Те държат своите ключове в сортиран ред, така че търсенето и другите операции да могат да използват принципа на двоичното търсене: когато търсят ключ в дърво (или място за вмъкване на нов ключ), те обикалят дървото от корен до лист , правейки сравнения с ключове, съхранени във възлите на дървото и решавайки, въз основа на сравнението, да продължи търсенето в левите или десните поддървета. Средно това означава, че всяко сравнение позволява на операциите да пропуснат около половината от дървото, така че всяко търсене, вмъкване или изтриване отнема време, пропорционално на логаритъма на броя елементи, съхранени в дървото. Това е много по-добро от линейното време, необходимо за намиране на елементи по ключ в (несортиран) масив, но по-бавно от съответните операции върху хеш таблици.
В тази публикация сме изброили често задавани въпроси за интервю в Binary Search Tree:
- Вмъкване в BST
- Търсене на даден ключ в BST
- Изтриване от BST (двоично дърво за търсене)
- „Изграждане на балансиран BST от дадените ключове“
- Определете дали дадено двоично дърво е BST или не
- Проверете дали дадените ключове представляват едни и същи BST или не без изграждане на BST
- Намерете предшественик по ред за даден ключ в BST
- Намерете най-ниския общ предшественик (LCA) на два възела в BST
- „Намерете k’-тия най-малък и k’-тия най-голям елемент в BST”
- Намерете пода и тавана в двоично дърво за търсене
- Преобразуване на двоично дърво в BST чрез запазване на оригиналната му структура
- Премахване на възли от BST, които имат ключове извън валиден диапазон
- Намерете чифт с дадена сума в BST
- Намерете k’-тия най-малък възел в двоично дърво за търсене (BST)
- Намерете наследник по ред за даден ключ в BST
- Замени всеки елемент от масива с най-малкия по-голям елемент отдясно
- Коригиране на двоично дърво, което е само на една размяна от превръщането в BST
- Актуализиране на всеки ключ в BST, за да съдържа сумата от всички по-големи ключове
- Проверете дали дадена последователност представлява обхождането на предварителната поръчка на BST
- „Изграждане на двоично дърво за търсене от последователност след поръчка“
- „Изграждане на двоично дърво за търсене от последователност от предварителна поръчка“
- Преброяване на поддървета в BST, чиито възли се намират в даден диапазон
- Намерете размера на най-големия BST в двоично дърво
- Отпечатайте пълно дърво за двоично търсене (BST) във възходящ ред
- Отпечатайте двоична дървовидна структура със съдържанието й в C++
- „Намерете оптималната цена за изграждане на двоично дърво за търсене“
- „Структура на данните за Treap“
- Внедряване на структура на данни на Treap (вмъкване, търсене и изтриване)
- Обединяване на два BST в двойно свързан списък в сортиран ред
- „Изграждане на BST с балансиран по височина от небалансиран BST“
- „Изграждане на BST с балансирана височина от сортиран двойно свързан списък“
- Намерете триплет с дадената сума в BST
- Преобразуване на двоично дърво за търсене в Min Heap
Благодаря, че прочетохте.
