Algoritm tushunchasi

Barg yoki terminal tuguni – avlodi mavjud boʻlmagan tugun
Ichki tugun - bu daraxtga avlodi mavjud boʻlgan har qanday tugun
va shuning uchun barg tuguni emas
Uchning darajasi - unga tushgan qirralarning soni.
Sentroid - uch, u olib tashlanganida hosil boʻlgan ulanish
komponentlarining oʻlchamlari n dan oshmaydi (asl daraxtning yarmi
kattaligi)
Tugun. Tugun - bu ba’zi bir qat’iy tabiat obyektiga mos keladigan
ikki turdagi graf elementlaridan birining nusxasi.
Tugunning balandligi - bu tugundan eng pastki tugunga (chekka
tugunga) barg deb ataladigan pastga tushadigan yoʻlning maksimal
uzunligi. Ildiz tugunining balandligi butun daraxtning balandligiga teng.
32 Binar (ikkilik) daraxtlar
Ikkilik daraxt - bu har bir tugunda koʻpi bilan ikkita avlod (bola)
boʻlgan ma’lumotlarning iyerarxik tuzilishi. Odatda, birinchisi ajdod
tuguni, avlodlar esa chap va oʻng merosxoʻrlar deb nomlanadi.

Pryufer Kodi-- Pryufer kodi [1, n] kesmadagi n-2 butun sonlar ketma-ketligiyordamida n uchlari bilan belgilangan daraxtlarni birma-bir kodlash usuli. Ya’ni, Pryufer kodi - bu toʻliq graf va raqamlar ketma-ketligining barcha daraxtlari orasidagi biyeksiyasidir.

33 Tartiblashgan va muvozanatlashgan daraxtlar

Uchlarni muvozanatlash - bu |h(L) − h(R)| = 2 chap va oʻng
pastki daraxtlari balandliklari farqi boʻlgan taqdirda, |h(L) − h(R)| ≤ 2
daraxtining xususiyati tiklanishi uchun ushbu uchlarning pastki
daraxtidagi ajdod va avlod munosabatlarini oʻzgartiradigan amal, aks
holda hech narsani oʻzgartirilmaydi. Muvozanatlash uchun biz har bir
uch uchun uning chap va oʻng diff(i) = h(L) − h(R) pastki daraxtlari
balandliklari orasidagi farqni saqlaymiz. Muvozanatlashgan daraxtlar haqidagi teorema. Adelson-Velskiy va Landis quyidagi teoremani isbotladilar:
Teorema. n ichki tugunli muvozanatli daraxt balandligi lg(n + 1)
va 1.4405 lg(n + 2) − 0.3277 qiymatlar bilan chegaralangan.