28 / 69

Binary Search Tree

Ikkilik qidiruv daraxti

Ikkilik qidiruv daraxti (Binary Search Tree — BST) — sonlarning saralangan ro'yxatini tezkor usulda saqlash va boshqarish imkonini beruvchi ma'lumotlar tuzilmasidir:

U ikkilik daraxt (binary tree) deb ataladi, chunki undagi har bir tugun ko'pi bilan ikkita bolaga ega bo'ladi.
U qidiruv daraxti (search tree) deb ataladi, chunki unda biror sonning mavjudligini o'rtacha O(log n) vaqt ichida qidirib topish mumkin.

Ikkilik qidiruv daraxtini oddiy ikkilik daraxtdan ajratib turuvchi asosiy xossalar:

Chap quyi daraxtdagi barcha tugunlarning kalitlari ildiz tugun kalitidan kichik bo'ladi.
O'ng quyi daraxtdagi barcha tugunlarning kalitlari ildiz tugun kalitidan katta bo'ladi.
Har bir tugunning ikkala quyi daraxti ham o'z navbatida ikkilik qidiruv daraxti (BST) hisoblanadi (ya'ni yuqoridagi ikki qoidaga to'liq bo'ysunadi).

BST vs Not BST

BST va BST bo'lmagan daraxt taqqoslanishi

Yuqoridagi rasmning o'ng tomonidagi daraxt BST emas, chunki "3" tugunining o'ng quyi daraxtida undan kichik bo'lgan "2" tuguni joylashib qolgan.

1. Qidirish amali

Qidirish algoritmi BST xossasiga tayanadi: agar qidirilayotgan qiymat ildizdan kichik bo'lsa, u aniq o'ng quyi daraxtda bo'lishi mumkin emas — biz faqat chap quyi daraxtni qidirishimiz kerak. Agar u ildizdan katta bo'lsa, faqat o'ng quyi daraxtni qidiramiz.

Algoritm

text

If root == NULL
    return NULL;
If number == root.data
    return root.data;
If number < root.data
    return search(root.left)
If number > root.data
    return search(root.right)

Qidiruv jarayonini bosqichma-bosqich ko'rib chiqamiz (masalan, 4 qiymatini qidiramiz):

4 qiymati ildiz (8) bilan solishtiriladi. 4 < 8 bo'lgani sababli, chap quyi daraxtga o'tiladi:

4 topilmadi, 8 ning chap quyi daraxtiga o'tish

Endi 4 qiymati 3 bilan solishtiriladi. 4 > 3 bo'lgani uchun o'ng quyi daraxtga o'tiladi:

4 topilmadi, 3 ning o'ng quyi daraxtiga o'tish

Endi 4 qiymati 6 bilan solishtiriladi. 4 < 6 bo'lgani sababli, chap quyi daraxtga o'tiladi:

4 topilmadi, 6 ning chap quyi daraxtiga o'tish

4 qiymati topildi:

4 qiymati muvaffaqiyatli topildi

Agar qiymat topilsa, natija rekursiya zanjiri orqali yuqoriga qaytariladi:

Qiymat rekursiya bo'yicha yuqoriga uzatiladi

Agar qiymat mavjud bo'lmasa, oxir-oqibat barg tugunning bo'sh bolasiga (NULL) yetib boriladi va NULL qaytariladi.

2. Element qo'shish amali

Qiymatni to'g'ri o'ringa qo'shish qidirish amaliga juda o'xshaydi, chunki yangi tugun qo'shilgandan so'ng ham daraxt BST qoidalariga mos qolishi kerak.

Algoritm

text

If node == NULL
    return createNode(data)
if (data < node.data)
    node.left = insert(node.left, data);
else if (data > node.data)
    node.right = insert(node.right, data);
return node;

Qo'shish jarayonini amalda ko'ramiz (masalan, 4 sonini qo'shamiz):

4 < 8, shuning uchun 8 ning chap bolasiga o'tamiz:

4<8 so, transverse through the left child of 8

4 < 8, chap bolaga o'tish

4 > 3, shuning uchun 3 ning o'ng bolasiga o'tamiz:

4>3 so, transverse through the right child of 4

4 > 3, o'ng bolaga o'tish

4 < 6, shuning uchun 6 ning chap bolasiga o'tamiz:

4<6 so, transverse through the left child of 6

4 < 6, chap bolaga o'tish

6 ning chap bolasi bo'sh bo'lganligi sababli, 4 ni shu yerga yangi tugun qilib qo'shamiz:

Insert 4 as a left child of 6

4 ni 6 ning chap bolasi sifatida qo'shish

Daraxt bo'ylab ortga qaytishda har bir tugunning bog'lanishlarini saqlab qolish uchun funksiya yakunida return node qilinadi:

Image showing the importance of returning the root element at the end

Ildiz tugunlarni saqlagan holda yuqoriga qaytish

3. Elementni o'chirish amali

Ikkilik qidiruv daraxtidan tugunni o'chirishning 3 ta holati mavjud:

1-holat: O'chiriladigan tugun barg tugun bo'lsa

Agar tugunning bolalari bo'lmasa, uni shunchaki daraxtdan olib tashlash kifoya:

4 is to be deleted

Barg tugunni (4) tanlash

Delete the node

Barg tugunni o'chirish

2-holat: O'chiriladigan tugun faqat bitta bolaga ega bo'lsa

Ushbu holatda:

O'chiriladigan tugun o'zining yagona bola tuguni bilan almashtiriladi.
Bola tugun o'zining avvalgi joyidan o'chiriladi.

6 is to be deleted

6 tugunini tanlash (uning faqat bitta bolasi bor: 7)

copy the value of its child to the node

Bola qiymatini o'rniga ko'chirish

Final tree

Yakuniy daraxt holati

3-holat: O'chiriladigan tugun ikkita bolaga ega bo'lsa

Ushbu holatda:

O'chirilishi kerak bo'lgan tugunning inorder vorisi (inorder successor) topiladi (ya'ni, uning o'ng quyi daraxtidagi eng kichik qiymatli tugun).
O'chiriladigan tugunning qiymati inorder vorisining qiymati bilan almashtiriladi.
Inorder vorisi bo'lgan asl tugun o'chiriladi.

3 is to be deleted

Ikkita bolaga ega bo'lgan 3 tugunini o'chirish

Copy the value of the inorder successor (4) to the node

Inorder vorisi (4) ning qiymatini 3 ning o'rniga ko'chirish

delete the inorder successor

Inorder vorisini asl o'rnidan o'chirish

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

// Go tilida Ikkilik qidiruv daraxti (Binary Search Tree - BST) amallari
package main

import "fmt"

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

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

// Inorder aylanib chiqish (saralangan tartibda)
func inorder(root *Node) {
	if root != nil {
		inorder(root.left)
		fmt.Printf("%d-> ", root.key)
		inorder(root.right)
	}
}

// Tugun qo'shish (Insert)
func insert(node *Node, key int) *Node {
	// Agar daraxt bo'sh bo'lsa, yangi tugun qaytariladi
	if node == nil {
		return newNode(key)
	}

	// Qiymatiga qarab chap yoki o'ng quyi daraxtga yo'naltiriladi
	if key < node.key {
		node.left = insert(node.left, key)
	} else if key > node.key {
		node.right = insert(node.right, key)
	}

	return node
}

// Inorder vorisini (o'ng quyi daraxtdagi eng kichik elementni) topish
func minValueNode(node *Node) *Node {
	current := node
	for current != nil && 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 {
		// 1 yoki 0 ta bolaga ega bo'lgan holat
		if root.left == nil {
			return root.right
		} else if root.right == nil {
			return root.left
		}

		// 2 ta bolaga ega bo'lgan holat:
		// O'ng quyi daraxtdagi eng kichik tugun (inorder successor) topiladi
		temp := minValueNode(root.right)
		root.key = temp.key

		// Inorder successor o'chirib tashlanadi
		root.right = deleteNode(root.right, temp.key)
	}

	return root
}

func main() {
	var root *Node
	root = insert(root, 8)
	root = insert(root, 3)
	root = insert(root, 1)
	root = insert(root, 6)
	root = insert(root, 7)
	root = insert(root, 10)
	root = insert(root, 14)
	root = insert(root, 4)

	fmt.Print("Inorder traversal: ")
	inorder(root)

	fmt.Println("\n\n10 o'chirilmoqda (Delete 10)")
	root = deleteNode(root, 10)
	fmt.Print("Inorder traversal: ")
	inorder(root)
	fmt.Println()
}

Ikkilik qidiruv daraxtining murakkabligi

Vaqt murakkabligi

Amal (Operation)	Eng yaxshi holat (Best Case)	O'rtacha holat (Average Case)	Eng yomon holat (Worst Case)
Qidirish (Search)	`O(log n)`	`O(log n)`	`O(n)`
Qo'shish (Insertion)	`O(log n)`	`O(log n)`	`O(n)`
O'chirish (Deletion)	`O(log n)`	`O(log n)`	`O(n)`

Bu yerda n — daraxtdagi tugunlarning umumiy soni. Eng yomon holat daraxt bitta chiziqqa cho'zilib (skewed tree) ketganda yuzaga keladi.

Xotira murakkabligi

Barcha amallar uchun xotira murakkabligi O(n) ni tashkil etadi.

Ikkilik qidiruv daraxtining qo'llanilishi

Ma'lumotlar bazalarida ko'p darajali indekslashda (multilevel indexing).
Dinamik saralashda (ma'lumotlar doimiy qo'shilib turganda ularni saralangan holda saqlash).
Unix operatsion tizimi yadrosida virtual xotira sohalarini boshqarishda.

Oldingi

Keyingi