Двоично дърво

от Уикипедия, свободната енциклопедия

Двоично дърво в информатиката се нарича дърво с разклоненост 2. Понякога наследниците на всеки връх се определят като ляв и десен. Най-често двоичните дървета се използват за реализация на логаритмични структури от данни като двоично дърво за претърсване или приоритетна опашка.

[редактиране] Двоично дърво за претърсване

Двоичното дърво за претърсване е структура от данни, която служи за съхраняване и намиране на данни по ключ, за който съществува наредба. Данните са разпределни в дървото по следния начин: за всеки връх, всички данни, които се намират в лявото му поддърво имат по-малък ключ, а всички данни, които се намират в дясното поддърво, имат по-голям ключ.

[редактиране] Ефикасност на двоичните дървета за търсене

Средната сложност на операциите добавяне и търсене в двоичните дървета за претърсване е O(logN), където N е броят на елементите, добавени в структурата. Ако елементите се добавят подредени по глемина, дървото може да се изроди до свързан списък, което води до сложност O(N). Съществуват алгоритми, които поддържат структурата балансирана и запазват добрите сложности.

[редактиране] Използвана литература

• An Introduction to Data Structures and Algorithms with Java, Glenn W. Rowe, Prentice Hill Europe 1998, ISBN 0-13-857749-8