AVL Trees

AVL daraxtlari

Oldingi darsda ko'rgan muammoni AVL daraxti qanday hal qilishini ko'raylik. AVL daraxtining siri — rotation (aylantirish): daraxt bir tomonga "og'ib" ketganda, tugunlarni qayta joylashtirib, uni yana tekis holatga qaytaradigan operatsiya.

Buni tarozi bilan solishtiring: agar bir pallaga ko'p yuk tushsa, tarozi bir tomonga og'ib ketadi. Uni tekislash uchun yukning bir qismini boshqa pallaga o'tkazasiz. Daraxtdagi "rotatsiya" ham xuddi shunday — og'ir tomondagi bitta tugunni "markazga" ko'chiradi.

example.go

package main

import "fmt"

type AVLNode struct {
	Value       int
	Left, Right *AVLNode
}

// rotateRight: chap tomonga og'ib ketgan daraxtni o'ngga "aylantiradi"
func rotateRight(y *AVLNode) *AVLNode {
	x := y.Left   // yangi ildiz bo'ladigan tugun
	t := x.Right  // vaqtincha bo'shatib turiladigan qism

	x.Right = y // eski ildiz endi x'ning o'ng bolasi bo'ladi
	y.Left = t  // x'ning eski o'ng qismi endi y'ning chap qismiga o'tadi

	return x // yangi ildiz
}

func main() {
	// Chapga qiyshaygan daraxt: 3 -> 2 -> 1
	root := &AVLNode{Value: 3, Left: &AVLNode{Value: 2, Left: &AVLNode{Value: 1}}}

	fmt.Println(root.Value) // 3 — hali muvozanatsiz ildiz

	balanced := rotateRight(root)
	fmt.Println(balanced.Value) // 2 — endi tekis o'rtadagi qiymat ildiz
}

Boshida daraxt 3 -> 2 -> 1 ko'rinishida, ya'ni butunlay chapga "qiyshaygan" (bu — aynan oldingi darsda ko'rgan muammoli holat). rotateRight chaqirilgach: 2 yangi ildiz bo'ladi, eski ildiz 3 endi 2ning o'ng bolasiga aylanadi, 1 esa 2ning chap bolasi bo'lib qoladi. Natijada daraxt 1, 2, 3 tartibida, lekin endi tekis (2 markazda, 1 va 3 uning ikki yonida) — aynan shu "tekislik" tezlikni qaytaradi.

Haqiqiy AVL implementatsiyasida har bir qo'shishdan keyin balandlik farqi tekshiriladi va kerak bo'lganda avtomatik aylantirish (chapga, o'ngga, yoki ikkalasi ketma-ket) chaqiriladi — bu ancha ko'proq kod talab qiladi. Bu darsning maqsadi shu asosiy "aylantirish" g'oyasini tushunish, chunki aynan shu g'oya ustida Go'ning ko'plab standart va tashqi kutubxonalari (masalan ma'lumotlar bazalarining indekslari) qurilgan.

>_ Exercise

rotateLeft — rotateRight'ning oynadagi aksi — funksiyasini yozing.

•rotateLeft(x *AVLNode) *AVLNode yozing: o'ngga qiyshaygan daraxtni chapga aylantiring
•mantiq rotateRight bilan bir xil, faqat Left/Right almashtirilgan
•1 -> 2 -> 3 (o'ngga qiyshaygan) daraxtni yasab, rotateLeft qiling va yangi ildizni chop eting

Stuck? Reveal a hint to help you.

Hints (0/3)

Key Takeaway

Key Takeaway:

Rotatsiya — daraxtning tartibini (qiymatlar ketma-ketligini) o'zgartirmasdan, uning shaklini tekislaydigan operatsiya; AVL daraxtlari buni har bir qo'shishdan keyin avtomatik bajaradi.

NEXT UP

Trie Fundamentals

OUTPUT

$ go run main.go
Kodingizni ishga tushiring