데이터 구조 알고리즘 회고 - B-tree

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