Дарахти барқарор чӣ гуна аст?

Дарахти барқарор як навъи дарахти дурустии ҷустуҷӯ мебошад, ки дар он баландии зердараҳо барои таъмини амалиётҳои самараноки ҷустуҷӯ, ворид кардан ва хориҷ кардан нигоҳ дошта мешавад. Ҳадафи барқароркунӣ кам кардани баландии дарахт аст, то ки амалиётҳо дар вақти наздик ба O(log n) иҷро шаванд.

Масаланҳои дарахти барқароршуда:

• Дарахти AVL: баландии зердараҳоро нигоҳ медорад, ки фарқият аз 1 зиёд нест.
• Дарахти сурх-сиёҳ: бо истифода аз тамғаҳои ранг дар гулҳо барои нигоҳ доштани тақрибан баробарӣ.

Барқароркунӣ бо истифода аз амалиётҳои махсус (масалан, гардишҳо) ба даст меояд, ки дар тағирёбии сохтори дарахт гулҳоро такрор мекунанд.

Ин барои алгоритмҳо ва структураҳои додаҳо муҳим аст, ки ба онҳо дастрасии зуд, ворид кардан ва хориҷ кардани унсурҳо лозим аст.