AVL-tree (kaşfiyotçilari Adelson-Velsky va Landis'lardan olingan) yana bir balanslangan binary search tree. AVL-tree'ga ötişdan oldin, balanced binary tree haqida eslab olamiz.

Balanced binary tree. Agar binary tree’ning uzunligi (height) O(log n) bölsa, balanced binary tree deyiladi. Bunda n – tree’dagi node’lar soni.

Balanced va non balanced binary tree.
Image credit: https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

Demak, balans bölişi uçun öng va çap çild'larning uzunligi bir xil bölişi yoki uzunlik −1 ≤ x ≤ 1  orasida farqlanişi kerak.

Red-black tree esingizdami? U daraxtni balansda uşlab turiş uçun node'larni çapga yoki öngga buriş yoki ranglarni almaştiriş amallarini bajarardi.

Biz örganmoqçi bölgan AVL-tree - balans bölişi uçun node'larni çapga yoki öngga buriş amallarini bajaradi. Ya'ni AVL-tree aslida qizil boğlanişlari yöq bölgan Red-black tree ekan. Tarix aslida bu tarifning xato ekanligini aytadi, sababi AVL-tree tuşunçasi 1966-yilda, 2-3 tree paydo bölmasidan avval öylab topilgan.

AVL-tree ga qöşiş (Insert)

Qöşiş odatiy uslubda, Binary Search tree'dagi kabi böladi. Element qöşib bölingaç, tree'ning balansi tekşiriladi. Lozim bölganda, balans töğrilanadi.

Quyidagi AVL-tree ga element qöşişni körib çiqamiz.

Tree'ga 23 qöşamiz. Dastlab qöşiş uçun kerakli pozitsiya topiladi, söngra element qöşiladi.

Tree'da balans yöqoldi, sababi 29 node'ning çap çild'i uzunligi 2, öng çild'i 0. 2 - 0 > 1. Balansni töğrilaş uçun 29 node'ni** öngga buramiz**. Şunda 26 parent bölib qoladi, uning çap çild'i - 23, öng çild'i 29 böladi.

Tree'ga balans qaytdi.

Yana bir misol. Tree'ga 55 qöşamiz.

Endi 65 node'ning çap çild'ining uzunligi - 2, öng çild'niki - 0. E'tiborlisi - endi bitta buriş bilan balansga keltira olmaymiz, yana bir uriniş kerak böladi.

50 node'ni çapga buramiz, 55 parent bölib qoladi:

Endi 55 ning parent'i - 65ni öngga buramiz. Daraxtga yana balans qaytdi:

Demak, AVL-tree'ni balansini töğrilaş uçun bizga bir yoki ikki buriş kerak bölarkan.

Burişlardan xulosa qilib, buriş qoidasini umumlaştiramiz:

• node'ning çap tarafi uzun (oğir) - > 1:

• uning çap çild'ining çap çild'i bor - node'ni öngga buramiz.

• uning çap çild'ining öng çild'i bor - node'ning çap çildi'ni çapga buramiz, node'ni öngga buramiz

• node'ning öng tarafi uzun (oğir) - > 1:

• uning öng çild'ining öng çild'i bor - node'ni çapga buramiz.

• uning öng çild'ining çap çild'i bor - node'ning öng çildi'ni öngga buramiz, node'ni çapga buramiz

Öçiriş (Deletion)

Öçirişda ham ikki qadam - node'ni öçiramiz va balansni qaytadan töğrilaymiz.

---

Keyingi maqolada AVL-tree ustida amallar uçun API yozamiz...