Junior
Дарахти дугоӣ чист?
sobes.tech AI
Ҷавоб аз AI
Дарахти дуал — ин структураи маълумотҳо дар шакли дарахт аст, ки дар он ҳар як ҳуҷра бештар аз ду фарзанд надорад: чап ва рост.
Хусусиятҳои асосӣ:
- Тамға (Root): Ҳуҷраи болоии дарахт.
- Ҳуҷра (Node): Элемент дар дарахт, ки маълумот ва пайвандҳо ба фарзандони худро дорад.
- Фарзанд (Child): Ҳуҷра, ки бевосита дар зери дигар ҳуҷра (падар) ҷойгир аст.
- Падар (Parent): Ҳуҷра, ки дар зери худ як ё бештар аз фарзанд дорад.
- Барг (Leaf): Ҳуҷра, ки фарзанд надорад.
- Шоха (Branch): Роҳи аз тамға то барг.
- Зердарахт (Subtree): Дарахт, ки аз ҳуҷра ва ҳамаи фарзандони он иборат аст.
Намудҳои гуногуни дарахти дуҷониба:
- Дарахти дуҷониба пурра (Full Binary Tree): Ҳар як ҳуҷра ё 0 ё 2 фарзанд дорад.
- Дарахти дуҷониба комил (Perfect Binary Tree): Ҳама сатҳҳо, ба истиснои охирин, пурра пур шудаанд ва дар сатҳи охирин ҳамаи ҳуҷраҳо то ҳадди имкон чап ҷойгир шудаанд.
- Дарахти дуҷониба баробар (Balanced Binary Tree): Баландии зердараҳтҳои чап ва рости ҳар як ҳуҷра на бештар аз 1 фарқ мекунад. Мисол: дарахти AVL, дарахти сурх-сиёҳ.
- Дарахти дуҷониба заиф (Degenerate Binary Tree): Ҳар як ҳуҷра бештар аз як фарзанд надорад. Дар асл, ин рӯйхати пайвастшуда аст.
Дар алгоритмҳо ва структураҳои маълумот истифода мешавад, масалан, дар дарахтҳои ҷустуҷӯии дуҷониба, кӯҳҳо, дарахтҳои синтаксисӣ.