31 / 69

Insertion into a B-tree

B-daraxtga element qo'shish

B-daraxtga yangi element qo'shish ikkita asosiy bosqichdan iborat: yangi elementni joylashtirish uchun mos tugunni qidirish va zarurat tug'ilganda tugunni ikkiga bo'lish (splitting the node). Qo'shish operatsiyasi har doim pastdan yuqoriga qarab (bottom-up approach) amalga oshiriladi.

Keling, ushbu jarayonlarni batafsil ko'rib chiqaylik.

Qo'shish amali

Agar daraxt bo'sh bo'lsa, yangi ildiz tugunini ajrating va kalitni kiriting.
Tugunda ruxsat etilgan kalitlar sonini yangilang.
Elementni qo'shish uchun mos barg (leaf) tugunni qidiring.
Agar tugun to'lgan bo'lsa:
- Elementlarni o'sish tartibida joylashtiring.
- Endi tugunda ruxsat etilgan chegaradan ko'p elementlar bo'ladi. Shuning uchun tugunni o'rta qiymat (median) bo'yicha ikkiga bo'ling (split).
- O'rta kalitni yuqoriga (ota tugunga) suring, chap tarafdagi kalitlarni chap farzand, o'ng tarafdagi kalitlarni esa o'ng farzand qiling.
Agar tugun to'lmagan bo'lsa:
- Elementni tugunga o'sish tartibini saqlagan holda kiriting.

Qo'shish misoli

Quyidagi rasmli misol orqali elementlarni kiritish jarayonini tushunib olaylik.

Kiritiladigan elementlar: 8, 9, 10, 11, 15, 20, 17.

B-daraxtga elementlar qo'shish

B-daraxtga elementlar qo'shish jarayoni

Element qo'shish algoritmi

text

BtreeInsertion(T, k)
r = root[T]
if n[r] == 2t - 1
    s = AllocateNode()
    root[T] = s
    leaf[s] = FALSE
    n[s] = 0
    c_1[s] = r
    BtreeSplitChild(s, 1, r)
    BtreeInsertNonFull(s, k)
else 
    BtreeInsertNonFull(r, k)

BtreeInsertNonFull(x, k)
i = n[x]
if leaf[x]
    while i ≥ 1 and k < key_i[x]
        key_i+1[x] = key_i[x]
        i = i - 1
    key_i+1[x] = k
    n[x] = n[x] + 1
else 
    while i ≥ 1 and k < key_i[x]
        i = i - 1
    i = i + 1
    if n[c_i[x]] == 2t - 1
        BtreeSplitChild(x, i, c_i[x])
        if k > key_i[x]
            i = i + 1
    BtreeInsertNonFull(c_i[x], k)

BtreeSplitChild(x, i, y)
z = AllocateNode()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
    key_j[z] = key_j+t[y]
if not leaf[y]
    for j = 1 to t
        c_j[z] = c_j+t[y]
n[y] = t - 1
for j = n[x] + 1 down to i + 1
    c_j+1[x] = c_j[x]
c_i+1[x] = z
for j = n[x] down to i
    key_j+1[x] = key_j[x]
key_i[x] = key_t[y]
n[x] = n[x] + 1

B-daraxtga element qo'shish dasturiy kodi

package main

import "fmt"

// BTreeNode tugun strukturasi
type BTreeNode struct {
	keys     []int
	children []*BTreeNode
	leaf     bool
	t        int // Minimal daraja (minimum degree)
}

func newBTreeNode(t int, leaf bool) *BTreeNode {
	return &BTreeNode{
		keys:     make([]int, 0, 2*t-1),
		children: make([]*BTreeNode, 0, 2*t),
		leaf:     leaf,
		t:        t,
	}
}

// Tugunlarni aylanib chiqish
func (n *BTreeNode) traverse() {
	i := 0
	for i = 0; i < len(n.keys); i++ {
		if !n.leaf {
			n.children[i].traverse()
		}
		fmt.Printf(" %d", n.keys[i])
	}
	if !n.leaf {
		n.children[i].traverse()
	}
}

// BTree strukturasi
type BTree struct {
	root *BTreeNode
	t    int
}

func NewBTree(t int) *BTree {
	return &BTree{
		root: nil,
		t:    t,
	}
}

func (tree *BTree) Traverse() {
	if tree.root != nil {
		tree.root.traverse()
	}
}

// Element qo'shish (Insert)
func (tree *BTree) Insert(k int) {
	if tree.root == nil {
		tree.root = newBTreeNode(tree.t, true)
		tree.root.keys = append(tree.root.keys, k)
		return
	}

	// Agar ildiz to'lgan bo'lsa, daraxt balandligi oshadi
	if len(tree.root.keys) == 2*tree.t-1 {
		s := newBTreeNode(tree.t, false)
		s.children = append(s.children, tree.root)
		s.splitChild(0, tree.root)

		i := 0
		if s.keys[0] < k {
			i++
		}
		s.children[i].insertNonFull(k)
		tree.root = s
	} else {
		tree.root.insertNonFull(k)
	}
}

// To'lmagan tugunga kalit qo'shish
func (n *BTreeNode) insertNonFull(k int) {
	i := len(n.keys) - 1

	if n.leaf {
		// O'sish tartibida to'g'ri o'rnini topib qo'shish
		n.keys = append(n.keys, 0)
		for i >= 0 && n.keys[i] > k {
			n.keys[i+1] = n.keys[i]
			i--
		}
		n.keys[i+1] = k
	} else {
		// Mos farzandni topish
		for i >= 0 && n.keys[i] > k {
			i--
		}
		i++
		// Agar farzand to'lgan bo'lsa, uni bo'lish (split)
		if len(n.children[i].keys) == 2*n.t-1 {
			n.splitChild(i, n.children[i])
			if n.keys[i] < k {
				i++
			}
		}
		n.children[i].insertNonFull(k)
	}
}

// Farzand tugunni ikkiga bo'lish (Split)
func (n *BTreeNode) splitChild(i int, y *BTreeNode) {
	t := n.t
	z := newBTreeNode(t, y.leaf)

	medianKey := y.keys[t-1]

	// z tugunga o'ng tomondagi kalitlarni ko'chirish
	for j := t; j < len(y.keys); j++ {
		z.keys = append(z.keys, y.keys[j])
	}

	if !y.leaf {
		for j := t; j < len(y.children); j++ {
			z.children = append(z.children, y.children[j])
		}
		y.children = y.children[:t]
	}

	y.keys = y.keys[:t-1]

	// z tugunni n.children ro'yxatiga kiritish
	n.children = append(n.children, nil)
	for j := len(n.children) - 1; j > i+1; j-- {
		n.children[j] = n.children[j-1]
	}
	n.children[i+1] = z

	// O'rta kalitni (median) n.keys ga chiqarish
	n.keys = append(n.keys, 0)
	for j := len(n.keys) - 1; j > i; j-- {
		n.keys[j] = n.keys[j-1]
	}
	n.keys[i] = medianKey
}

func main() {
	t := NewBTree(3)
	t.Insert(8)
	t.Insert(9)
	t.Insert(10)
	t.Insert(11)
	t.Insert(15)
	t.Insert(16)
	t.Insert(17)
	t.Insert(18)
	t.Insert(20)
	t.Insert(23)

	fmt.Print("B-daraxt elementlari: ")
	t.Traverse()
	fmt.Println()
}

B-daraxtga qo'shish murakkabligi

Eng yomon holat vaqti (Worst case): O(t * log_t n) yoki O(log n)
O'rtacha holat vaqti (Average case): O(log n)
Xotira murakkabligi (Space complexity): O(n)

Oldingi

Keyingi