Insertion on a B+ Tree

package main

import "fmt"

// BPNode B+ daraxt tugun strukturasi
type BPNode struct {
	isLeaf   bool
	keys     []int
	children []*BPNode
	next     *BPNode // Barg tugunlar uchun bog'langan ro'yxat ko'rsatkichi
}

func newBPNode(isLeaf bool) *BPNode {
	return &BPNode{
		isLeaf:   isLeaf,
		keys:     make([]int, 0),
		children: make([]*BPNode, 0),
		next:     nil,
	}
}

// BPlusTree strukturasi
type BPlusTree struct {
	root  *BPNode
	order int // Har bir tugundagi maksimal farzandlar soni (m)
}

func NewBPlusTree(order int) *BPlusTree {
	root := newBPNode(true)
	return &BPlusTree{
		root:  root,
		order: order,
	}
}

// Search - B+ daraxtda kalitni qidirish
func (tree *BPlusTree) Search(k int) bool {
	curr := tree.root
	for !curr.isLeaf {
		i := 0
		for i < len(curr.keys) && k >= curr.keys[i] {
			i++
		}
		curr = curr.children[i]
	}

	for _, key := range curr.keys {
		if key == k {
			return true
		}
	}
	return false
}

// Insert - B+ daraxtga element qo'shish
func (tree *BPlusTree) Insert(k int) {
	root := tree.root
	if len(root.keys) == tree.order-1 {
		newRoot := newBPNode(false)
		newRoot.children = append(newRoot.children, root)
		tree.splitChild(newRoot, 0, root)
		tree.root = newRoot
		tree.insertNonFull(newRoot, k)
	} else {
		tree.insertNonFull(root, k)
	}
}

func (tree *BPlusTree) insertNonFull(node *BPNode, k int) {
	if node.isLeaf {
		idx := 0
		for idx < len(node.keys) && node.keys[idx] < k {
			idx++
		}
		if idx < len(node.keys) && node.keys[idx] == k {
			return // Takroriy qiymat kiritilmaydi
		}
		node.keys = append(node.keys, 0)
		for j := len(node.keys) - 1; j > idx; j-- {
			node.keys[j] = node.keys[j-1]
		}
		node.keys[idx] = k
		return
	}

	idx := 0
	for idx < len(node.keys) && k >= node.keys[idx] {
		idx++
	}

	child := node.children[idx]
	if len(child.keys) == tree.order-1 {
		tree.splitChild(node, idx, child)
		if k >= node.keys[idx] {
			idx++
		}
	}
	tree.insertNonFull(node.children[idx], k)
}

func (tree *BPlusTree) splitChild(parent *BPNode, idx int, child *BPNode) {
	mid := len(child.keys) / 2
	promotedKey := child.keys[mid]

	newNode := newBPNode(child.isLeaf)

	if child.isLeaf {
		newNode.keys = append(newNode.keys, child.keys[mid:]...)
		child.keys = child.keys[:mid]

		newNode.next = child.next
		child.next = newNode
	} else {
		newNode.keys = append(newNode.keys, child.keys[mid+1:]...)
		newNode.children = append(newNode.children, child.children[mid+1:]...)

		child.keys = child.keys[:mid]
		child.children = child.children[:mid+1]
	}

	parent.children = append(parent.children, nil)
	for j := len(parent.children) - 1; j > idx+1; j-- {
		parent.children[j] = parent.children[j-1]
	}
	parent.children[idx+1] = newNode

	parent.keys = append(parent.keys, 0)
	for j := len(parent.keys) - 1; j > idx; j-- {
		parent.keys[j] = parent.keys[j-1]
	}
	parent.keys[idx] = promotedKey
}

// PrintLeaves - Barg tugunlar zanjirini chiqarish
func (tree *BPlusTree) PrintLeaves() {
	curr := tree.root
	for !curr.isLeaf {
		curr = curr.children[0]
	}

	fmt.Print("B+ daraxt barglari (bog'langan ro'yxat): ")
	for curr != nil {
		for _, k := range curr.keys {
			fmt.Printf("%d ", k)
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	tree := NewBPlusTree(4) // order = 4
	elements := []int{5, 15, 25, 35, 45, 55, 40, 30, 20}
	for _, e := range elements {
		tree.Insert(e)
	}

	tree.PrintLeaves()

	for _, k := range []int{45, 15, 99} {
		if tree.Search(k) {
			fmt.Printf("Kalit %d: topildi\n", k)
		} else {
			fmt.Printf("Kalit %d: topilmadi\n", k)
		}
	}
}