Дерево пошуку
З Вікіпедії, безкоштовно encyclopedia
В інформатиці де́рево пошуку (як структура даних) — це деревоподібна структура даних, яку застосовують для пошуку конкретних ключів усередині множини. Щоб дерево могло функціонувати як дерево пошуку, ключ кожного вузла повинен бути більшим за будь-які ключі в піддеревах ліворуч і менше будь-яких ключів у піддеревах праворуч.
Перевагою дерев пошуку є їх ефективний час пошуку за умови, що дерево достатньо збалансоване, тобто листя на обох кінцях мають подібну глибину. Існують різні види структур даних, які є деревами пошуку. Деякі з них також дозволяють ефективно додавати та видаляти елементи. Операції на таких деревах потім повинні підтримувати баланс дерева.
Дерева пошуку часто застосовуються для реалізації асоціативного масиву. Алгоритм дерева пошуку використовує ключ від пари ключ-значення, щоб знайти місце, а потім програма зберігає всю пару ключ-значення у цьому конкретному місці.