Двійкове дерево пошуку
Двійкове дерево пошуку — інтерактивний експеримент із застосунку «Структури даних», безкоштовної симуляції StudyFi Lab, яка працює просто в браузері.
У кожному вузлі менші значення йдуть ліворуч, більші — праворуч. Тому пошук і вставка проходять одним шляхом від кореня й тривають O(h), де h — висота дерева; у збалансованого дерева h ≈ log₂ n. Видалення має три випадки: лист просто зникає, вузол з одним нащадком замінює цей нащадок, а вузол із двома нащадками бере значення свого симетричного (in-order) наступника. Симетричний обхід видає значення за зростанням; схожі дерева лежать в основі індексів баз даних.
Спробуй: Видали корінь — у нього два нащадки, тож побачиш пошук наступника. Потім натисни «Вставити впорядковані значення»: дерево вироджується у список, а висота зростає до n.
Поширені запитання
Що показує експеримент «Двійкове дерево пошуку»?
У кожному вузлі менші значення йдуть ліворуч, більші — праворуч. Тому пошук і вставка проходять одним шляхом від кореня й тривають O(h), де h — висота дерева; у збалансованого дерева h ≈ log₂ n. Видалення має три випадки: лист просто зникає, вузол з одним нащадком замінює цей нащадок, а вузол із двома нащадками бере значення свого симетричного (in-order) наступника. Симетричний обхід видає значення за зростанням; схожі дерева лежать в основі індексів баз даних.
Як спробувати «Двійкове дерево пошуку»?
Видали корінь — у нього два нащадки, тож побачиш пошук наступника. Потім натисни «Вставити впорядковані значення»: дерево вироджується у список, а висота зростає до n.
Готуєшся до контрольної?
Завантаж свої конспекти, і StudyFi перетворить їх на картки, тести й подкасти.