-
Notifications
You must be signed in to change notification settings - Fork 0
/
insert.go
67 lines (64 loc) · 1.5 KB
/
insert.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package main
func insert(val int, t *BTree) {
n := len(t.root.keys)
if n == 2*T-1 {
newRoot := NewNode()
newRoot.isLeaf = false
newRoot.children = append(newRoot.children, t.root)
t.root = newRoot
splitNode(t.root, 0)
insertNonFull(t.root, val)
} else {
insertNonFull(t.root, val)
}
}
func splitNode(x *node, index int) {
rightChild := NewNode()
leftChild := x.children[index]
n := len(x.keys)
rightChild.isLeaf = leftChild.isLeaf
for i := 0; i < T-1; i++ {
rightChild.keys = append(rightChild.keys, leftChild.keys[i+T])
}
leftChild.keys = leftChild.keys[:T]
if !leftChild.isLeaf {
for i := 0; i < T; i++ {
rightChild.children = append(rightChild.children, leftChild.children[i+T])
}
leftChild.children = leftChild.children[:T]
}
x.children = append(x.children, nil)
for i := n; i > index+1; i-- {
x.children[i] = x.children[i-1]
}
x.children[index+1] = rightChild
x.keys = append(x.keys, 0)
for i := n - 1; i > index; i-- {
x.keys[i] = x.keys[i-1]
}
x.keys[index] = leftChild.keys[T-1]
leftChild.keys = leftChild.keys[:T-1]
}
func insertNonFull(x *node, val int) {
i := len(x.keys) - 1 // last filled index
if x.isLeaf {
x.keys = append(x.keys, val) // just for maintaining indices
for i >= 0 && val < x.keys[i] {
x.keys[i+1] = x.keys[i]
i--
}
x.keys[i+1] = val
} else {
for i >= 0 && val < x.keys[i] {
i--
}
i++
if len(x.children) == (2*T - 1) {
splitNode(x, i)
if val > x.keys[i] {
i++
}
}
insertNonFull(x.children[i], val)
}
}