2-Mavzu: Ikkilik daraxtlar bilan ishlash Ikkilik daraxtga qo'shilish

Ikkilik daraxtlarning xususiyatlari

1. 
   Har qanday darajadagi maksimal tugun soni: 2 ^ L bu erda L - bir qator darajalar (0 <= L <= H).
   
2. 
   BT balandlikdagi H tugunlarining minimal va maksimal soni: Minimal- H + 1 va maksimal- 2 ^ (H + 1) - 1 bu erda 0 darajasi 0 ga teng.
   
3. 
   N tugunlarga ega bo'lgan ma'lum bir BTning minimal balandligi: log2 (N + 1) -1 bu erda 0 darajasi 0 ga teng.
   
4. 
   Barg tugunlarining umumiy soni: 2 bolali tugunlarning umumiy soni + 1.
   
5. 
   L bargli tugunlarga ega bo'lgan BT darajalarining minimal soni: (log2 L) +1.
   

Ikkilik daraxtlarning turlari
To'liq ikkilik daraxtlar
Ildiz va oraliq tugunlari 2 ta tugunchadan iborat bo'lgan Ikkilik daraxt. Boshqacha qilib aytganda, barg tugunlaridan tashqari har bir tugunda 2 ta bola tuguni bor deyishimiz mumkin.
Eslatma: To'liq ikkilik daraxtdagi barg tugunlari soni: Ichki tugunlar soni + 1.

To'liq ikkilik daraxt
Oxirgi darajadan tashqari barcha darajalar to'liq to'ldirilgan va barcha tugunlar chapdan o'ngga to'ldirilgan ikkilik daraxt
Eslatma: Binary Heap - bu to'liq binar daraxtning namunasi.

Zo'r ikkitomonlama daraxt
Ichki tugunlari va ildiz tugunida 2 ta bola va barchasi bir xil darajada bo'lgan ikkitomonlama daraxt.
Eslatma: Perfect Binary Tree tugunlarining umumiy soni: 2 ^ H -1 bu erda H - BT balandligi.


Balanslangan ikkilik daraxt
Ikki daraxt, uning chap balandligi h1 va o'ng pastki daraxt balandligi h2 | h1-h2 | <= 1.
Eslatma: AVL va RB daraxti muvozanatli binar daraxtni saqlaydi.

Patologik ikkilamchi daraxt (egri chiziqli) BT / degeneratsiya BT)
Barcha ichki tugunlarida bittadan farzandi bo'lgan Ikkilik daraxt chap bolada bo'lishi mumkin yoki u to'g'ri bola bo'lishi mumkin.