Двоично дърво
от Уикипедия, свободната енциклопедия
Двоично дърво в информатиката се нарича дърво с разклоненост 2.
Всеки връх на двоично дърво съдържа едно или повече полета с данни, както и два указателя - към левият и десният наследник. Най-горният връх на дървото се нарича корен. Върховете без наследници се наричат листа.
Една от най-честите употреби на двоични дървета е като дървета за търсене.
[редактиране] Операции върху двоични дървета
- Вмъкване на нов връх
- Изтриване на връх
- Показване или посещаване на върховете на дървото
[редактиране] Ефикасност на двоичните дървета за търсене
Сортирането на двоично дърво има комплекситет O(n log n), а търсенето в него е принципно двоично търсене с комплекситет O(log n). Дърветата могат да се сортират и при вмъкване на нови върхове. Такива дървета се наричат балансирани (АВЛ) дървета, наречени по името на руските математици Аделсон, Велски и Ландис, които ги въвеждат през 1962 г.
[редактиране] Използвана литература
- An Introduction to Data Structures and Algorithms with Java, Glenn W. Rowe, Prentice Hill Europe 1998, ISBN: 0-13-857749-8