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

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

Двоично дърво в информатиката се нарича дърво с разклоненост 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