Deletion from a B+ Tree

package main

import "fmt"

type BPNode struct {
	isLeaf   bool
	keys     []int
	children []*BPNode
	next     *BPNode
}

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

type BPlusTree struct {
	root  *BPNode
	order int
}

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

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
		}
		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
}

func (tree *BPlusTree) Delete(k int) {
	tree.deleteInternal(tree.root, k)
	if len(tree.root.keys) == 0 && !tree.root.isLeaf {
		tree.root = tree.root.children[0]
	}
}

func (tree *BPlusTree) deleteInternal(node *BPNode, k int) {
	if node.isLeaf {
		for i, val := range node.keys {
			if val == k {
				node.keys = append(node.keys[:i], node.keys[i+1:]...)
				return
			}
		}
		return
	}

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

	tree.deleteInternal(node.children[idx], k)

	// Agar o'chirilgan kalit ichki tugunda indeks sifatida mavjud bo'lsa, uni yangilaymiz
	for i, val := range node.keys {
		if val == k {
			// Inorder successor ni topish (o'ng farzandning eng chap kaliti)
			succ := node.children[i+1]
			for !succ.isLeaf {
				succ = succ.children[0]
			}
			if len(succ.keys) > 0 {
				node.keys[i] = succ.keys[0]
			}
		}
	}
}

func (tree *BPlusTree) PrintLeaves() {
	curr := tree.root
	for !curr.isLeaf {
		curr = curr.children[0]
	}
	fmt.Print("Barglar: ")
	for curr != nil {
		for _, k := range curr.keys {
			fmt.Printf("%d ", k)
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	tree := NewBPlusTree(4)
	for _, val := range []int{5, 15, 25, 35, 45, 55} {
		tree.Insert(val)
	}

	fmt.Print("Boshlang'ich daraxt: ")
	tree.PrintLeaves()

	tree.Delete(25)
	fmt.Print("25 o'chirilgandan so'ng: ")
	tree.PrintLeaves()
}