Algoritmlarning xossalari Algoritmning asosiy xossalari. Algoritmning 5-ta asosiy xossasi bor: Diskretlilik Cheklilik

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.
Eslatma: Patologik BT balandligi: Tugunlar soni-1.


Ikkilik qidiruv daraxti

Ildizida 8 dona bo'lgan 9 va chuqurlik 3 o'lchamdagi ikkilik qidiruv daraxti Barglari chizilmaydi.
Yilda Kompyuter fanlari, a ikkilik qidiruv daraxti (BST), shuningdek, buyurdi yoki saralangan ikkilik daraxt, a ildiz otgan ikkilik daraxt uning ichki tugunlari har birida tugmachaning chap pastki daraxtidagi barcha tugmachalardan kattaroq va uning o'ng pastki daraxtidagi tugmachalardan kichikroq kalit saqlanadi. Ikkilik daraxt - bu bir turi ma'lumotlar tuzilishi raqamlar kabi ma'lumotlarni uyushgan ravishda saqlash uchun. Ikkilik qidiruv daraxtlari imkon beradi ikkilik qidirish tezkor qidirish, ma'lumotlar elementlarini qo'shish va olib tashlash uchun va amalga oshirish uchun ishlatilishi mumkin dinamik to'plamlar va qidiruv jadvallari. BST-dagi tugunlarning tartibi shuni anglatadiki, har bir taqqoslash qolgan daraxtning yarmini o'tkazib yuboradi, shuning uchun butun izlanish talab etiladi vaqt bilan mutanosib The ikkilik logarifma daraxtda saqlanadigan narsalar sonidan. Bu juda yaxshi chiziqli vaqt (saralanmagan) qatorda kalitlarga ko'ra elementlarni topish uchun talab qilinadi, ammo tegishli operatsiyalardan sekinroq xash jadvallar. Ikkilik qidiruv daraxtining bir nechta variantlari o'rganildi.