AVL Tree

AVL daraxti (AVL Tree) — har bir tugunida balans omili (balance factor) deb nomlanuvchi qo'shimcha ma'lumotni saqlab boruvchi o'z-o'zini balanslovchi ikkilik qidiruv daraxtidir (self-balancing binary search tree).

AVL daraxti o'z nomini uni kashf qilgan olimlar — G. M. Adelson-Velsky va E. M. Landis nomlarining bosh harflaridan olgan (1962-yil).

Balans omili

AVL daraxtidagi tugunning balans omili (balance factor) — uning chap quyi daraxti balandligi bilan o'ng quyi daraxti balandligi o'rtasidagi farqdir:

Balans omili = (Chap quyi daraxt balandligi - O'ng quyi daraxt balandligi)

AVL daraxtining o'z-o'zini muvozanatlash xossasi aynan ushbu balans omili orqali ta'minlanadi. Daraxtdagi har bir tugunning balans omili faqat -1, 0 yoki 1 ga teng bo'lishi shart.

Balanslangan AVL daraxtiga misol:

Har bir tugunida balans omili ko'rsatilgan AVL daraxti

AVL daraxtida aylantirish amallari

Qo'shish yoki o'chirish amallaridan so'ng daraxtning balans omili buzilsa (ya'ni -1, 0, 1 chegarasidan chiqsa), daraxt aylantirish (rotation) amallari yordamida qayta muvozanatga keltiriladi.

Aylantirishning 4 ta turi mavjud:

1. Left Rotate

Chapga burish:

O'ng tomoni og'ir bo'lib qolgan quyi daraxtni chapga burish orqali muvozanatga keltirish.

1. Boshlang'ich holat:

Chapga burish boshlang'ich holati

2. Agar y ning chap quyi daraxti bo'lsa, x ni y ning chap quyi daraxtining otasi qilib tayinlaymiz:

x ni y ning chap quyi daraxtiga ota qilib belgilash

3. Agar x ning otasi NULL bo'lsa, y daraxtning ildiziga aylanadi. Aks holda x o'z otasining chap bolasi bo'lsa, y ham chap bola bo'ladi; agar o'ng bola bo'lsa, y o'ng bola bo'ladi:

x ning ota bog'lanishini y ga ko'chirish

4. y ni x ning otasi deb belgilaymiz:

y ni x ning otasi qilib belgilash

2. Right Rotate

O'ngga burish:

Chap tomoni og'ir bo'lib qolgan quyi daraxtni o'ngga burish orqali muvozanatga keltirish.

1. Boshlang'ich holat:

O'ngga burish boshlang'ich holati

2. Agar x ning o'ng quyi daraxti bo'lsa, y ni x ning o'ng quyi daraxtining otasi qilib belgilaymiz:

y ni x ning o'ng quyi daraxtiga ota qilib belgilash

3. Agar y ning otasi NULL bo'lsa, x daraxtning ildiziga aylanadi. Aks holda bog'lanishlar mos ravishda yangilanadi:

Ota bog'lanishini x ga o'tkazish

4. x ni y ning otasi deb belgilaymiz:

x ni y ning otasi qilib belgilash

3. Chap-O'ng burish

Dastlab x-y tugunlarida chapga burish, so'ngra y-z tugunlarida o'ngga burish amalga oshiriladi:

1. x-y bo'yicha chapga burish:

x-y bo'yicha chapga burish

2. z-y bo'yicha o'ngga burish:

z-y bo'yicha o'ngga burish

4. O'ng-Chap burish

Dastlab x-y tugunlarida o'ngga burish, so'ngra z-y tugunlarida chapga burish amalga oshiriladi:

1. x-y bo'yicha o'ngga burish:

x-y bo'yicha o'ngga burish

2. z-y bo'yicha chapga burish:

z-y bo'yicha chapga burish

Yangi tugun qo'shish algoritmi

Yangi tugun har doim boshlang'ich balans omili 0 ga teng bo'lgan barg tugun sifatida qo'shiladi.

1. Boshlang'ich daraxt berilgan bo'lsin:

Boshlang'ich daraxt

Qo'shilishi kerak bo'lgan yangi tugun:

Yangi tugun

2. Oddiy BST qoidalariga binoan yangi tugun uchun to'g'ri o'rin qidiriladi:

Yangi tugun joylashadigan o'rinni topish

3. Yangi tugun tegishli barg tugunga ulanadi:

Yangi tugunni joylashtirish

4. Tugunlarning balans omillari qayta hisoblab yangilanadi:

Balans omillarini yangilash

5. Agar tugunlarning balansi buzilgan bo'lsa (|BF| > 1), kerakli aylantirish (rotation) amali bajariladi:
   • Agar balanceFactor > 1 va newNodeKey < leftChildKey bo'lsa: Right rotation qilinadi.
   • Agar balanceFactor > 1 va newNodeKey > leftChildKey bo'lsa: Left-Right rotation qilinadi.

Aylantirish orqali daraxtni balanslash

Qayta muvozanatlash

6. Yakuniy balanslangan daraxt ko'rinishi hosil bo'ladi:

Yakuniy balanslangan AVL daraxti

Tugunni o'chirish algoritmi

Tugun oddiy BST dagi kabi o'chiriladi, so'ngra balans omillari yangilanadi va zarur bo'lsa muvozanatlash amallari bajariladi:

1. O'chirilishi kerak bo'lgan tugun topiladi:

O'chiriladigan tugunni aniqlash

2. Agar tugun 2 ta bolaga ega bo'lsa, uning inorder vorisi (inorder successor) topiladi:

Inorder vorisini topish

3. O'chiriladigan tugun qiymati inorder vorisining qiymati bilan almashtiriladi:

Qiymatni almashtirish

4. Asl barg tugun o'chirib tashlanadi:

Barg tugunni o'chirish

5. Tugunlarning balans omili yangilanadi:

Balans omillarini yangilash

6. Balans omili buzilgan tugunlar uchun mos aylantirish qo'llaniladi:

Balanslash uchun o'ngga burish

7. Yakuniy balanslangan daraxt:

O'chirishdan so'ng yakuniy balanslangan AVL daraxti

Dasturiy namunalar: Go, Python, Java, C va C++

// Go tilida AVL Tree amallari (Qo'shish, O'chirish va Aylanib chiqish)
package main

import "fmt"

type Node struct {
	key    int
	left   *Node
	right  *Node
	height int
}

func newNode(key int) *Node {
	return &Node{
		key:    key,
		height: 1,
	}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func getHeight(n *Node) int {
	if n == nil {
		return 0
	}
	return n.height
}

// Balans omilini (Balance Factor) olish
func getBalanceFactor(n *Node) int {
	if n == nil {
		return 0
	}
	return getHeight(n.left) - getHeight(n.right)
}

// O'ngga burish (Right Rotate)
func rightRotate(y *Node) *Node {
	x := y.left
	T2 := x.right

	x.right = y
	y.left = T2

	y.height = max(getHeight(y.left), getHeight(y.right)) + 1
	x.height = max(getHeight(x.left), getHeight(x.right)) + 1

	return x
}

// Chapga burish (Left Rotate)
func leftRotate(x *Node) *Node {
	y := x.right
	T2 := y.left

	y.left = x
	x.right = T2

	x.height = max(getHeight(x.left), getHeight(x.right)) + 1
	y.height = max(getHeight(y.left), getHeight(y.right)) + 1

	return y
}

// Tugun qo'shish (Insert)
func insertNode(root *Node, key int) *Node {
	if root == nil {
		return newNode(key)
	}

	if key < root.key {
		root.left = insertNode(root.left, key)
	} else if key > root.key {
		root.right = insertNode(root.right, key)
	} else {
		return root
	}

	root.height = 1 + max(getHeight(root.left), getHeight(root.right))
	balance := getBalanceFactor(root)

	// Chap-Chap (LL) holati
	if balance > 1 && key < root.left.key {
		return rightRotate(root)
	}

	// O'ng-O'ng (RR) holati
	if balance < -1 && key > root.right.key {
		return leftRotate(root)
	}

	// Chap-O'ng (LR) holati
	if balance > 1 && key > root.left.key {
		root.left = leftRotate(root.left)
		return rightRotate(root)
	}

	// O'ng-Chap (RL) holati
	if balance < -1 && key < root.right.key {
		root.right = rightRotate(root.right)
		return leftRotate(root)
	}

	return root
}

func nodeWithMinimumValue(node *Node) *Node {
	current := node
	for current.left != nil {
		current = current.left
	}
	return current
}

// Tugunni o'chirish (Delete)
func deleteNode(root *Node, key int) *Node {
	if root == nil {
		return root
	}

	if key < root.key {
		root.left = deleteNode(root.left, key)
	} else if key > root.key {
		root.right = deleteNode(root.right, key)
	} else {
		if root.left == nil || root.right == nil {
			var temp *Node
			if root.left != nil {
				temp = root.left
			} else {
				temp = root.right
			}

			if temp == nil {
				temp = root
				root = nil
			} else {
				*root = *temp
			}
		} else {
			temp := nodeWithMinimumValue(root.right)
			root.key = temp.key
			root.right = deleteNode(root.right, temp.key)
		}
	}

	if root == nil {
		return root
	}

	root.height = 1 + max(getHeight(root.left), getHeight(root.right))
	balance := getBalanceFactor(root)

	if balance > 1 && getBalanceFactor(root.left) >= 0 {
		return rightRotate(root)
	}

	if balance > 1 && getBalanceFactor(root.left) < 0 {
		root.left = leftRotate(root.left)
		return rightRotate(root)
	}

	if balance < -1 && getBalanceFactor(root.right) <= 0 {
		return leftRotate(root)
	}

	if balance < -1 && getBalanceFactor(root.right) > 0 {
		root.right = rightRotate(root.right)
		return leftRotate(root)
	}

	return root
}

// Preorder tartibida chop etish
func printPreOrder(root *Node) {
	if root != nil {
		fmt.Printf("%d ", root.key)
		printPreOrder(root.left)
		printPreOrder(root.right)
	}
}

func main() {
	var root *Node

	root = insertNode(root, 33)
	root = insertNode(root, 13)
	root = insertNode(root, 53)
	root = insertNode(root, 9)
	root = insertNode(root, 21)
	root = insertNode(root, 61)
	root = insertNode(root, 8)
	root = insertNode(root, 11)

	fmt.Print("Preorder traversal: ")
	printPreOrder(root)

	root = deleteNode(root, 13)
	fmt.Print("\nAfter deletion (13): ")
	printPreOrder(root)
	fmt.Println()
}

AVL daraxtining murakkabligi

AVL daraxti har qanday qo'shish va o'chirishdan so'ng o'zini qat'iy muvozanatda ushlab turgani sababli, uning balandligi hech qachon O(log n) dan oshmaydi. Shuning uchun barcha asosiy amallar hatto eng yomon holatda ham O(log n) vaqtda bajariladi.

Xotira murakkabligi barcha amallar uchun O(n) ni tashkil etadi.

AVL daraxtining qo'llanilishi

• Tez-tez kiritish/o'chirishdan ko'ra qidirish amali ancha ko'proq bajariladigan tizimlarda.
• Xotiradagi saralangan to'plamlar va xaritalarni (balanced set/map) tashkil etishda.
• Ma'lumotlar bazalarida indekslarni muvozanatli saqlashda.