代码
package B_tree
import (
"fmt"
"math/rand"
)
type btree_node struct {
num int
key []int
child []*btree_node
parent *btree_node
}
type btree struct {
order int
max int
min int
sidx int
root *btree_node
first *btree_node
}
func new_btree(order int) *btree {
newBtree := new(btree)
newBtree.order = order
newBtree.max = order - 1
if order%2 == 0 {
newBtree.min = (order - 1) / 2
} else {
newBtree.min = order / 2
}
newBtree.sidx = order / 2
return newBtree
}
func new_node(tree *btree) *btree_node {
node := new(btree_node)
node.key = make([]int, tree.max+1)
node.child = make([]*btree_node, tree.order+1)
return node
}
func find_insert_index(node *btree_node, key int) (int, interface{}) {
for i := 0; i < node.num; i++ {
if node.key[i] == key {
return i, "find key in node"
} else if node.key[i] > key {
return i, nil
}
}
return node.num, nil
}
func find_child_index(node *btree_node, child *btree_node) int {
for i := 0; i < node.num+1; i++ {
if node.child[i] == child {
return i
}
}
return 0
}
func insert_key(node *btree_node, key int, index int) {
if node.num != 0 {
for i := node.num - 1; i >= index; i-- {
node.key[i+1] = node.key[i]
}
}
node.key[index] = key
node.num++
}
func insert_child(node *btree_node, child *btree_node, index int) {
for i := node.num - 1; i >= index; i-- {
node.child[i+1] = node.child[i]
}
node.child[index] = child
}
func cut_node(node1 *btree_node, index int, node2 *btree_node) {
j := 0
i := index
end := node1.num
for i < end {
node2.child[j] = node1.child[i]
if node2.child[j] != nil {
node2.child[j].parent = node2
}
node2.key[j] = node1.key[i]
node1.child[i] = nil
node1.key[i] = 0
i++
j++
node1.num--
node2.num++
}
node2.child[j] = node1.child[i]
if node2.child[j] != nil {
node2.child[j].parent = node2
}
node1.child[i] = nil
}
func find_node_index(node *btree_node, key int) (*btree_node, int) {
for node != nil {
index, is_find := find_insert_index(node, key)
if is_find != nil {
return node, index
}
node = node.child[index]
}
return node, 0
}
func delete_node_index(node *btree_node, index int) (*btree_node, int) {
leftChild := node.child[index]
rightChild := node.child[index+1]
tmpNode := node
tmpIndex := index
if leftChild != nil {
if leftChild.num >= rightChild.num {
for tmpNode.child[tmpIndex] != nil {
num := tmpNode.child[tmpIndex].num
tmpNode = tmpNode.child[tmpIndex]
tmpIndex = num
}
tmpIndex--
} else {
tmpIndex := index + 1
for tmpNode.child[tmpIndex] != nil {
tmpNode = tmpNode.child[tmpIndex]
tmpIndex = 0
}
}
}
node.key[index] = tmpNode.key[tmpIndex]
return tmpNode, tmpIndex
}
func find_brother(tree *btree, node *btree_node) (*btree_node, int, int, int) {
num := node.parent.num
index := 0
for i := 0; i <= num; i++ {
if node.parent.child[i] == node {
index = i
break
}
}
var brother *btree_node
var parent_index int
var brother_index int
if index == 0 {
brother = node.parent.child[1]
parent_index = 0
brother_index = 0
} else if index == num {
brother = node.parent.child[num-1]
parent_index = num - 1
brother_index = brother.num - 1
} else {
brother1 := node.parent.child[index-1]
brother2 := node.parent.child[index+1]
if brother1.num > brother2.num {
brother = brother1
parent_index = index - 1
brother_index = brother.num - 1
} else {
brother = brother2
parent_index = index
brother_index = 0
}
}
return brother, brother_index, parent_index, index
}
func merge(tree *btree, node1 *btree_node, node2 *btree_node, parentIndex int) {
i := node1.num
j := 0
for j < node2.num {
node1.key[i] = node2.key[j]
node1.child[i] = node2.child[j]
i++
j--
node1.num++
}
i = parentIndex
for i < node1.parent.num-1 {
node1.parent.key[i] = node1.parent.key[i+1]
node1.parent.child[i+1] = node1.parent.child[i+2]
}
node1.parent.num--
if node1.parent.num <= tree.min {
node := node1.parent
brother, _, parent_index, node_index := find_brother(tree, node)
if parent_index < node_index {
brother.key[brother.num] = brother.parent.key[parent_index]
merge(tree, brother, node, parent_index)
} else {
node.key[node.num] = node.parent.key[parent_index]
merge(tree, node, brother, parent_index)
}
}
}
func check_is_min(tree *btree, node *btree_node, index int) {
if node.num > tree.min {
node.key[index] = 0
node.num--
} else {
brother, brother_index, parent_index, node_index := find_brother(tree, node)
if brother.num > tree.min {
node.key[index] = node.parent.key[parent_index]
node.parent.key[parent_index] = brother.key[brother_index]
node, index = delete_node_index(brother, brother_index)
check_is_min(tree, node, index)
} else {
node.key[index] = node.parent.key[parent_index]
if parent_index < node_index {
merge(tree, brother, node, parent_index)
} else {
merge(tree, node, brother, parent_index)
}
}
}
}
func delete(tree *btree, key int) {
node := tree.root
index := 0
node, index = find_node_index(node, key)
if node == nil {
fmt.Println("can not find the key ", key)
return
}
fmt.Println("find the key ", key, index)
if node == tree.root {
node.key[index] = 0
node.num--
return
}
node, index = delete_node_index(node, index)
check_is_min(tree, node, index)
}
func insert(tree *btree, key int) {
node := tree.root
for node != nil {
// fmt.Println(key)
index, error_msg := find_insert_index(node, key)
// fmt.Println(index)
if error_msg != nil {
fmt.Println(index, error_msg)
return
}
if node.child[index] == nil {
insert_key(node, key, index)
for node.num > tree.max {
// fmt.Println(node)
if node.parent == nil {
new_root_node := new_node(tree)
node.parent = new_root_node
tree.root = new_root_node
new_root_node.child[0] = node
}
child_index := find_child_index(node.parent, node)
select_key := node.key[tree.sidx]
new_right_node := new_node(tree)
cut_node(node, tree.sidx+1, new_right_node)
new_right_node.parent = node.parent
insert_key(node.parent, select_key, child_index)
node.key[tree.sidx] = 0
node.num--
insert_child(node.parent, new_right_node, child_index+1)
node = node.parent
}
return
} else {
node = node.child[index]
}
}
}
func printAll(tree *btree) {
fmt.Println(tree.root)
for i, v1 := range tree.root.child {
if v1 != nil {
fmt.Println(i, v1)
for i, v2 := range v1.child {
if v2 != nil {
fmt.Println(i, v2)
}
}
}
}
}
func Do() {
new_btree := new_btree(10)
new_node := new_node(new_btree)
new_btree.root = new_node
new_btree.first = new_node
printAll(new_btree)
for i := 0; i < 1000; i++ {
key := rand.Intn(10000000)
// fmt.Println(key)
insert(new_btree, key)
// printAll(new_btree)
}
printAll(new_btree)
fmt.Println(new_btree.first)
delete(new_btree, 1000)
delete(new_btree, 7649444)
delete(new_btree, 7866383)
printAll(new_btree)
}
