Red-Black Tree

Qizil-qora daraxt (Red-Black Tree) — bu o'z-o'zini muvozanatlovchi (self-balancing) ikkilik qidiruv daraxti (Binary Search Tree) bo'lib, unda har bir tugun o'zining rangini (qizil yoki qora) bildiruvchi qo'shimcha bitga (atributga) ega bo'ladi.

Qizil-qora daraxt quyidagi 5 ta asosiy xususiyatga (qoidaga) javob beradi:

1. Qizil/Qora xususiyati (Red/Black Property): Har bir tugun yo qizil, yo qora rangda bo'ladi.
2. Ildiz xususiyati (Root Property): Daraxtning ildizi har doim qora rangda bo'ladi.
3. Barg xususiyati (Leaf Property): Barcha bo'sh barg tugunlar (NIL yoki null) qora rangda hisoblanadi.
4. Qizil rang xususiyati (Red Property): Agar tugun qizil bo'lsa, uning ikkala farzandi ham albatta qora bo'lishi shart (ya'ni ikkita ketma-ket qizil tugun bo'lishi mumkin emas).
5. Qora chuqurlik xususiyati (Depth Property): Ixtiyoriy tugundan boshlab uning avlodlari bo'lgan barg tugunlarga boradigan har qanday oddiy yo'lda bir xil sondagi qora tugunlar (black-depth) bo'ladi.

Qizil-qora daraxtga misol:

Qizil-qora daraxt strukturasi

Har bir tugun quyidagi atributlarga ega:

• color (rang: Qizil yoki Qora)
• key (kalit / qiymat)
• leftChild (chap farzand ko'rsatkichi)
• rightChild (o'ng farzand ko'rsatkichi)
• parent (ota tugun ko'rsatkichi)

Qizil-qora daraxt o'z-o'zini qanday muvozanatlaydi?

Tugunlarning qizil va qora ranglari daraxt muvozanatini saqlashga xizmat qiladi.

Yuqoridagi rang cheklovlari ildizdan barggacha bo'lgan har qanday oddiy yo'l boshqa ixtiyoriy shunday yo'ldan ko'pi bilan 2 barobardan ortiq uzun bo'lmasligini kafolatlaydi. Natijada daraxt balandligi har doim O(log n) bo'lib qoladi va qidiruv, qo'shish hamda o'chirish amallari kafolatlangan O(log n) vaqtda bajariladi.

Qizil-qora daraxt ustida burish amallari

Qo'shish yoki o'chirish amallari natijasida qizil-qora daraxt qoidalari buzilganda, daraxtni qayta muvozanatlash uchun burish (rotation) amallaridan foydalaniladi. Burish paytida qism-daraxt tugunlarining o'rni almashtiriladi, lekin ikkilik qidiruv daraxti tartibi buzilmaydi.

Asosiy burish turlari:

1. Left Rotate

Chapga burish: Chapga burishda o'ng tarafdagi tugunlar chap tarafga o'tkaziladi.

1. Boshlang'ich daraxt:

Boshlang'ich holat

2. Agar y ning chap qism-daraxti bo'lsa, x ni uning ota tuguni qilib belgilang:

y ning chap qism-daraxtini x ga bog'lash

3. Agar x ning otasi NULL bo'lsa, y ni ildiz qiling. Aks holda x o'z otasi p ning chap farzandi bo'lsa y ni p ning chap farzandi, o'ng farzandi bo'lsa y ni o'ng farzandi qilib belgilang:

Ota ko'rsatkichini y ga o'tkazish

4. y ni x ning otasi qilib belgilang:

y ni x ning otasi qilib belgilash (Chapga burish tugallandi)

2. Right Rotate

O'ngga burish: O'ngga burishda chap tarafdagi tugunlar o'ng tarafga o'tkaziladi.

1. Boshlang'ich daraxt:

Boshlang'ich holat

2. Agar x ning o'ng qism-daraxti bo'lsa, y ni uning otasi qilib belgilang:

x ning o'ng qism-daraxtini y ga bog'lash

3. y ning ota ko'rsatkichini x ga o'tkazing:

Ota ko'rsatkichini x ga o'tkazish

4. x ni y ning otasi qilib belgilang:

x ni y ning otasi qilib belgilash (O'ngga burish tugallandi)

3. Left-Right and Right-Left Rotations

Chap-o'ng va o'ng-chap burishlar:

• Chap-o'ng burish (Left-Right Rotate): Avval x-y ustida chapga burish, so'ngra y-z ustida o'ngga burish bajariladi:

1-qadam: x-y chapga burish

2-qadam: z-y o'ngga burish

• O'ng-chap burish (Right-Left Rotate): Avval x-y ustida o'ngga burish, so'ngra z-y ustida chapga burish bajariladi:

1-qadam: x-y o'ngga burish

2-qadam: z-y chapga burish

Batafsil kiritish va o'chirish amallari uchun quyidagi darslarga qarang:

• Qizil-qora daraxtga element qo'shish (Insertion)
• Qizil-qora daraxtdan element o'chirish (Deletion)

Qizil-qora daraxt dasturiy kodi

package main

import "fmt"

type Color bool

const (
	RED   Color = true
	BLACK Color = false
)

type Node struct {
	data   int
	color  Color
	left   *Node
	right  *Node
	parent *Node
}

type RedBlackTree struct {
	TNULL *Node
	root  *Node
}

func NewRedBlackTree() *RedBlackTree {
	tnull := &Node{color: BLACK}
	return &RedBlackTree{
		TNULL: tnull,
		root:  tnull,
	}
}

func (tree *RedBlackTree) leftRotate(x *Node) {
	y := x.right
	x.right = y.left
	if y.left != tree.TNULL {
		y.left.parent = x
	}
	y.parent = x.parent
	if x.parent == nil {
		tree.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}
	y.left = x
	x.parent = y
}

func (tree *RedBlackTree) rightRotate(x *Node) {
	y := x.left
	x.left = y.right
	if y.right != tree.TNULL {
		y.right.parent = x
	}
	y.parent = x.parent
	if x.parent == nil {
		tree.root = y
	} else if x == x.parent.right {
		x.parent.right = y
	} else {
		x.parent.left = y
	}
	y.right = x
	x.parent = y
}

func (tree *RedBlackTree) insertFix(k *Node) {
	for k.parent != nil && k.parent.color == RED {
		if k.parent == k.parent.parent.right {
			u := k.parent.parent.left // amaki (uncle)
			if u.color == RED {
				u.color = BLACK
				k.parent.color = BLACK
				k.parent.parent.color = RED
				k = k.parent.parent
			} else {
				if k == k.parent.left {
					k = k.parent
					tree.rightRotate(k)
				}
				k.parent.color = BLACK
				k.parent.parent.color = RED
				tree.leftRotate(k.parent.parent)
			}
		} else {
			u := k.parent.parent.right // amaki (uncle)
			if u.color == RED {
				u.color = BLACK
				k.parent.color = BLACK
				k.parent.parent.color = RED
				k = k.parent.parent
			} else {
				if k == k.parent.right {
					k = k.parent
					tree.leftRotate(k)
				}
				k.parent.color = BLACK
				k.parent.parent.color = RED
				tree.rightRotate(k.parent.parent)
			}
		}
		if k == tree.root {
			break
		}
	}
	tree.root.color = BLACK
}

func (tree *RedBlackTree) Insert(key int) {
	node := &Node{
		data:   key,
		color:  RED,
		left:   tree.TNULL,
		right:  tree.TNULL,
		parent: nil,
	}

	var y *Node = nil
	x := tree.root

	for x != tree.TNULL {
		y = x
		if node.data < x.data {
			x = x.left
		} else {
			x = x.right
		}
	}

	node.parent = y
	if y == nil {
		tree.root = node
	} else if node.data < y.data {
		y.left = node
	} else {
		y.right = node
	}

	if node.parent == nil {
		node.color = BLACK
		return
	}

	if node.parent.parent == nil {
		return
	}

	tree.insertFix(node)
}

func (tree *RedBlackTree) printHelper(root *Node, indent string, last bool) {
	if root != tree.TNULL {
		fmt.Print(indent)
		if last {
			fmt.Print("R----")
			indent += "   "
		} else {
			fmt.Print("L----")
			indent += "|  "
		}
		sColor := "RED"
		if root.color == BLACK {
			sColor = "BLACK"
		}
		fmt.Printf("%d(%s)\n", root.data, sColor)
		tree.printHelper(root.left, indent, false)
		tree.printHelper(root.right, indent, true)
	}
}

func (tree *RedBlackTree) PrintTree() {
	tree.printHelper(tree.root, "", true)
}

func main() {
	tree := NewRedBlackTree()
	elements := []int{55, 40, 65, 60, 75, 57}
	for _, e := range elements {
		tree.Insert(e)
	}

	fmt.Println("Qizil-qora daraxt strukturasi:")
	tree.PrintTree()
}

Qizil-qora daraxtning qo'llanilishi

• Chekli xaritalar (finite maps) va lug'atlarni amalga oshirishda.
• Java: java.util.TreeMap va java.util.TreeSet to'plamlarining asosi sifatida.
• C++ STL: std::set, std::map, std::multiset va std::multimap konteynerlarida.
• Linux Kernel: Jarayonlar rejalashtiruvchisi (Completely Fair Scheduler — CFS) da jarayonlarni boshqarish uchun.