Insertion in a Red-Black Tree

Qizil-qora daraxt (Red-Black Tree) — har bir tuguni qizil yoki qora rangga ega bo'lgan o'z-o'zini muvozanatlovchi ikkilik qidiruv daraxtidir.

Yangi tugun qo'shilayotganda, u har doim QIZIL (RED) rangli tugun sifatida qo'shiladi. Yangi tugun kiritilgandan so'ng, qizil-qora daraxt xususiyatlari buzilgan bo'lsa, daraxtni qayta bo'yash (recoloring) va burish (rotations) orqali uning qoidalari tiklanadi.

Yangi tugunni kiritish algoritmi

Yangi elementni kiritish quyidagi bosqichlarda amalga oshiriladi:

1. Kiritilayotgan yangi tugun newNode:

Yangi tugun (newNode)

2. y bo'sh barg tugun (NIL), x esa daraxtning ildizi bo'lsin. Yangi tugun quyidagi daraxtga kiritilmoqda:

Boshlang'ich daraxt

3. Agar daraxt bo'sh bo'lsa (x teng NIL), newNode ni ildiz tugun sifatida kiriting va uning rangini QORA qilib belgilang.
   Aks holda, barg tugunga (NIL) yetguncha quyidagi amallarni takrorlang:
   • Yangi kalit newKey ni joriy tugun kaliti rootKey bilan taqqoslang.
   • Agar newKey > rootKey bo'lsa, o'ng qism-daraxt bo'ylab harakatlaning.
   • Aks holda, chap qism-daraxt bo'ylab harakatlaning:

Kiritiladigan manzil sari yo'nalish

4. Topilgan barg tugunning otasini newNode ning otasi qilib belgilang.
   Agar barg kaliti yangi kalitdan katta bo'lsa, newNode ni chap farzand, aks holda o'ng farzand qiling:

Yangi tugun daraxtga ulandi

5. newNode ning chap va o'ng farzandlarini NIL (null) qilib, rangini QIZIL qilib belgilang:

Yangi tugun rangi QIZIL qilib belgilandi

6. Qizil-qora daraxt xususiyatlari buzilgan bo'lsa, ularni tiklash uchun InsertFix algoritmini chaqiring.

Nima uchun yangi qo'shilgan tugunlar har doim QIZIL bo'ladi?

Chunki qizil tugunni kiritish qizil-qora daraxtning eng qat'iy qoidasi bo'lgan qora chuqurlik (black-depth) xususiyatini buzmaydi (barcha oddiy yo'llardagi qora tugunlar soni o'zgarishsiz qoladi).

Agar qizil tugun boshqa qizil tugunga ulansa, "ikkita qizil tugun ketma-ket kela olmaydi" qoidasi buzilishi mumkin, biroq bu muammoni hal qilish qora chuqurlik muammosini tuzatishdan ancha oson va tezkor kechadi.

Kiritishdan so'ng qoidalarni tiklash algoritmi

Ushbu algoritm yangi tugun kiritilgandan so'ng daraxt qoidalarini tiklaydi. newNode ning ota tuguni p QIZIL bo'lib turguniga qadar quyidagi amallar bajariladi:

Agar p bobo tugun gP ning chap farzandi bo'lsa:

1-Holat: Amaki tugun rangi QIZIL bo'lsa

Agar bobo gP ning o'ng farzandi (amaki tugun) QIZIL bo'lsa:

• gP ning ikkala farzandini (ota va amakini) QORA, gP ning o'zini esa QIZIL rangga bo'yang.
• newNode ni gP ga ko'chiring:

Ota va amaki tugunlar rangini qoraga, boboni qizilga o'zgartirish

newNode ni bobo tugunga ko'chirish

2-Holat: Amaki QORA va newNode o'ng farzand bo'lsa

Agar newNode o'z otasi p ning o'ng farzandi bo'lsa:

• p ni newNode deb belgilang.
• newNode ustida chapga burish (Left-Rotate) amalini bajaring:

newNode ni ota tugunga tayinlash

Chapga burish amali

3-Holat: Amaki QORA va newNode chap farzand bo'lsa

• Ota tugun p ning rangini QORA, bobo gP ning rangini QIZIL qiling.
• Bobo gP ustida o'ngga burish (Right-Rotate) amalini bajaring:

Otaning rangini qora, boboning rangini qizil qilish

Bobo tugunni o'ngga burish

Agar p bobo tugun gP ning o'ng farzandi bo'lsa:

(Yuqoridagi holatlarning simmetrik aksi bajariladi)

• Agar amaki (chap farzand) QIZIL bo'lsa, ota va amakini QORA, boboni QIZIL qilib, newNode ni boboga ko'chiring.
• Aks holda, agar newNode chap farzand bo'lsa, p ustida o'ngga buring.
• So'ng otani QORA, boboni QIZIL qilib, bobo gP ustida chapga buring.

Tugallangach, har qanday holatda ham daraxtning ildiz tuguni rangini QORA qilib belgilang:

Ildiz rangini har doim QORA qilib belgilash

Natijaviy qizil-qora daraxt quyidagicha ko'rinishga ega bo'ladi:

Yakuniy to'g'ri shakllangan qizil-qora daraxt

Qizil-qora daraxtga qo'shish 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()
}

Kiritish murakkabligi

• Eng yomon holat vaqti (Worst case Time Complexity): O(log n)
• O'rtacha holat vaqti (Average case Time Complexity): O(log n)
• Xotira murakkabligi (Space Complexity): O(n)