Deletion from a B-tree

package main

import "fmt"

type BTreeNode struct {
	keys     []int
	children []*BTreeNode
	leaf     bool
	t        int
}

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

func (n *BTreeNode) findKey(k int) int {
	idx := 0
	for idx < len(n.keys) && n.keys[idx] < k {
		idx++
	}
	return idx
}

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

func (n *BTreeNode) remove(k int) {
	idx := n.findKey(k)

	if idx < len(n.keys) && n.keys[idx] == k {
		if n.leaf {
			n.removeFromLeaf(idx)
		} else {
			n.removeFromNonLeaf(idx)
		}
	} else {
		if n.leaf {
			fmt.Printf("Kalit %d daraxtda mavjud emas\n", k)
			return
		}

		flag := (idx == len(n.keys))

		if len(n.children[idx].keys) < n.t {
			n.fill(idx)
		}

		if flag && idx > len(n.keys) {
			n.children[idx-1].remove(k)
		} else {
			n.children[idx].remove(k)
		}
	}
}

func (n *BTreeNode) removeFromLeaf(idx int) {
	n.keys = append(n.keys[:idx], n.keys[idx+1:]...)
}

func (n *BTreeNode) removeFromNonLeaf(idx int) {
	k := n.keys[idx]

	if len(n.children[idx].keys) >= n.t {
		pred := n.getPredecessor(idx)
		n.keys[idx] = pred
		n.children[idx].remove(pred)
	} else if len(n.children[idx+1].keys) >= n.t {
		succ := n.getSuccessor(idx)
		n.keys[idx] = succ
		n.children[idx+1].remove(succ)
	} else {
		n.merge(idx)
		n.children[idx].remove(k)
	}
}

func (n *BTreeNode) getPredecessor(idx int) int {
	cur := n.children[idx]
	for !cur.leaf {
		cur = cur.children[len(cur.children)-1]
	}
	return cur.keys[len(cur.keys)-1]
}

func (n *BTreeNode) getSuccessor(idx int) int {
	cur := n.children[idx+1]
	for !cur.leaf {
		cur = cur.children[0]
	}
	return cur.keys[0]
}

func (n *BTreeNode) fill(idx int) {
	if idx != 0 && len(n.children[idx-1].keys) >= n.t {
		n.borrowFromPrev(idx)
	} else if idx != len(n.keys) && len(n.children[idx+1].keys) >= n.t {
		n.borrowFromNext(idx)
	} else {
		if idx != len(n.keys) {
			n.merge(idx)
		} else {
			n.merge(idx - 1)
		}
	}
}

func (n *BTreeNode) borrowFromPrev(idx int) {
	child := n.children[idx]
	sibling := n.children[idx-1]

	child.keys = append([]int{n.keys[idx-1]}, child.keys...)

	if !child.leaf {
		child.children = append([]*BTreeNode{sibling.children[len(sibling.children)-1]}, child.children...)
		sibling.children = sibling.children[:len(sibling.children)-1]
	}

	n.keys[idx-1] = sibling.keys[len(sibling.keys)-1]
	sibling.keys = sibling.keys[:len(sibling.keys)-1]
}

func (n *BTreeNode) borrowFromNext(idx int) {
	child := n.children[idx]
	sibling := n.children[idx+1]

	child.keys = append(child.keys, n.keys[idx])

	if !child.leaf {
		child.children = append(child.children, sibling.children[0])
		sibling.children = sibling.children[1:]
	}

	n.keys[idx] = sibling.keys[0]
	sibling.keys = sibling.keys[1:]
}

func (n *BTreeNode) merge(idx int) {
	child := n.children[idx]
	sibling := n.children[idx+1]

	child.keys = append(child.keys, n.keys[idx])
	child.keys = append(child.keys, sibling.keys...)

	if !child.leaf {
		child.children = append(child.children, sibling.children...)
	}

	n.keys = append(n.keys[:idx], n.keys[idx+1:]...)
	n.children = append(n.children[:idx+1], n.children[idx+2:]...)
}

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

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
	}

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

func (n *BTreeNode) insertNonFull(k int) {
	i := len(n.keys) - 1
	if n.leaf {
		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 {
		for i >= 0 && n.keys[i] > k {
			i--
		}
		i++
		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)
	}
}

func (n *BTreeNode) splitChild(i int, y *BTreeNode) {
	t := n.t
	z := newBTreeNode(t, y.leaf)

	medianKey := y.keys[t-1]
	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]

	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

	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 (tree *BTree) Delete(k int) {
	if tree.root == nil {
		fmt.Println("Daraxt bo'sh")
		return
	}

	tree.root.remove(k)

	if len(tree.root.keys) == 0 {
		if tree.root.leaf {
			tree.root = nil
		} else {
			tree.root = tree.root.children[0]
		}
	}
}

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()

	t.Delete(20)

	fmt.Print("20 o'chirilgandan so'ng: ")
	t.Traverse()
	fmt.Println()
}