Golang 数据结构和法算B-树

• GitHub完整代码
• 代码实现

package tree

import (
	"data-structures-and-algorithms/contract"
	"data-structures-and-algorithms/queue"
	"fmt"
	"sort"
	"strings"
)

var (
	nilItems    = make([]interface{}, 16)
	nilChildren = make([]*btreeNode, 16)
)

// b-树节点
//   k0  k1  k2
// c0  c1  c2  c3
// 1. len(key) = len(children) - 1
// 2. ci <= ki < ci 1
// 3. 空 btreeNode 无数据信息，包含一个为 nil 的 lc。
type btreeNode struct {
	parent   *btreeNode
	items    []interface{}
	children []*btreeNode
}

// 新建空节点
func emptyBtreeNode(parent *btreeNode) *btreeNode {
	node := &btreeNode{parent: parent}
	node.children = append(node.children, nil)
	return node
}

// 在指定位置插入元素
func (n *btreeNode) insertItemAt(index int, item interface{}) {
	n.items = append(n.items, nil)
	if index < len(n.items) {
		copy(n.items[index 1:], n.items[index:])
	}
	n.items[index] = item
}

// 在指定位置移除元素
func (n *btreeNode) removeItemAt(index int) interface{} {
	item := n.items[index]
	copy(n.items[index:], n.items[index 1:])
	n.items[len(n.items)-1] = nil
	n.items = n.items[:len(n.items)-1]
	return item
}

// 在指定位置插入子节点指针
func (n *btreeNode) insertChildAt(index int, child *btreeNode) {
	n.children = append(n.children, nil)
	if index < len(n.children) {
		copy(n.children[index 1:], n.children[index:])
	}
	n.children[index] = child
}

// 在指定位置删除子节点指针
func (n *btreeNode) removeChildAt(index int) *btreeNode {
	child := n.children[index]
	copy(n.children[index:], n.children[index 1:])
	n.children[len(n.children)-1] = nil
	n.children = n.children[:len(n.children)-1]
	return child
}

// 截断slice中的元素
func (n *btreeNode) truncateItem(index int) {
	var toClear []interface{}
	n.items, toClear = n.items[:index], n.items[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilItems):]
	}
}

// 截断slice中子节点指针元素
func (n *btreeNode) truncateChild(index int) {
	var toClear []*btreeNode
	n.children, toClear = n.children[:index], n.children[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilChildren):]
	}
}

// 节点 n 在位置 index 处进行分裂
func (n *btreeNode) split(index int) (interface{}, *btreeNode) {
	item := n.items[index]
	node := &btreeNode{}
	node.items = append(node.items, n.items[index 1:]...)
	node.children = append(node.children, n.children[index 1:]...)
	n.truncateItem(index)
	n.truncateChild(index   1)
	if node.children[0] != nil {
		for _, child := range node.children {
			child.parent = node
		}
	}
	return item, node
}

// 当前节点为其父节点的第几个孩子
func (n *btreeNode) nth() int {
	var index int
	for size := len(n.parent.children); index < size; index   {
		if n.parent.children[index] == n {
			break
		}
	}
	return index
}

// 将节点 n 与其右兄弟以及父节点中 index 位置的元素进进行合并.
func (n *btreeNode) merge(index int, rs *btreeNode) *btreeNode {
	item := n.parent.removeItemAt(index)
	n.parent.removeChildAt(index   1)
	n.insertItemAt(len(n.items), item)
	n.items = append(n.items, rs.items...)
	n.children = append(n.children, rs.children...)
	rs.items = nil
	rs.children = nil
	return n
}

// 在树节点中寻找 item 所在位置：成功时返回 item[i] == key； 失败时 item[i-1] < key < item[i]
func (n *btreeNode) find(comparator contract.Comparator, item interface{}) (int, bool) {
	i := sort.Search(len(n.items), func(i int) bool {
		return comparator(item, n.items[i]) < 0
	})
	if i > 0 && comparator(item, n.items[i-1]) == 0 {
		return i - 1, true
	}
	return i, false
}

// Btree B-树
type Btree struct {
	hot           *btreeNode
	root          *btreeNode
	size          int
	order         int
	keyComparator contract.Comparator
}

// 算法：
// 1、x != nil 时，在 x 中查找 key 对于位置 i。
// 2.1、x.key[i] == key， return x。
// 2.2、x.key[i] != key， x = x.children[i]，执行 1。
func (t *Btree) searchAt(node *btreeNode, item interface{}) (*btreeNode, int) {
	t.hot = nil
	for node != nil {
		i, found := node.find(t.keyComparator, item)
		if found {
			return node, i
		}
		t.hot = node
		node = node.children[i]
	}
	return nil, 0
}

// solveOverflow 上溢修复
// 算法：
// 1、节点 x 是否上溢，未上溢则终止。
// 2、节点元素取中 item, 并分裂为两个节点 l, r。处理 l， r 中的 keys 和 children 以及子节点指针。
// 4、在x父节点(父节点不存在时则意味着在根节点溢出，新建根节点)适当位置插入 item，以及新的子节点指针并指向 r。
// 4、令 x 为 x父节点，执行算法 1。
func (t *Btree) solveOverflow(node *btreeNode) {
	if len(node.children) <= t.order {
		return
	}
	index := t.order >> 1
	item, newNode := node.split(index)
	p := node.parent
	if p == nil {
		p = emptyBtreeNode(nil)
		p.children[0] = node
		node.parent = p
		t.root = p
	}
	newNode.parent = p
	r, _ := p.find(t.keyComparator, item)
	p.insertItemAt(r, item)
	p.insertChildAt(r 1, newNode)
	t.solveOverflow(p)
}

// solveUnderflow 下溢修复
// 算法（左顾右盼 合并）：
// 1、节点 x 是否下溢，未下溢则终止。
// 2、x 为树根，倘若作为树根的节点已不含关键码，却有（唯一的）非空孩子，则这个节点可被跳过,并因不再有用而被销毁,整树高度降低一层。
// 3、x左兄弟存在且元素充足，从左兄弟转借一个元素。
// 4、x右兄弟存在且元素充足，从右兄弟转借一个元素。
// 5、合并x与左或右兄弟。
func (t *Btree) solveUnderflow(node *btreeNode) {
	if (t.order 1)>>1 <= len(node.children) {
		return
	}
	p := node.parent
	if p == nil {
		if len(node.items) == 0 && node.children[0] != nil {
			t.root = node.children[0]
			t.root.parent = nil
			node.children[0] = nil
		}
		return
	}
	index := node.nth()
	if index < len(p.children)-1 && (t.order 1)>>1 < len(p.children[index 1].children) { // 从右孩子借
		rs := p.children[index 1]
		node.insertItemAt(len(node.items), p.items[index])
		p.items[index] = rs.removeItemAt(0)
		child := rs.removeChildAt(0)
		node.insertChildAt(len(node.children), child)
		if child != nil {
			child.parent = node
		}
		return
	} else if index > 0 && (t.order 1)>>1 < len(p.children[index-1].children) { // 从左孩子借
		ls := p.children[index-1]
		node.insertItemAt(0, p.items[index-1])
		p.items[index-1] = ls.removeItemAt(len(ls.items) - 1)
		child := ls.removeChildAt(len(ls.children) - 1)
		node.insertChildAt(0, child)
		if child != nil {
			child.parent = node
		}
		return
	} else if index < len(p.children)-1 { // 与右孩子合并
		node.merge(index, p.children[index 1])
	} else { // 与左孩子合并
		p.children[index-1].merge(index-1, node)
	}
	t.solveUnderflow(p)
}

// NewBtree 初始化空B-树
func NewBtree(order int, cmps ...contract.Comparator) *Btree {
	cmp := contract.DefaultComparator
	if len(cmps) > 0 {
		cmp = cmps[0]
	}
	return &Btree{order: order, keyComparator: cmp}
}

// Size 元素个数
func (t *Btree) Size() int {
	return t.size
}

// Height 树高
func (t *Btree) Height() (height int) {
	if t.root == nil {
		return -1
	}
	x := t.root
	for ; x != nil && x.children[0] != nil; height   {
		x = x.children[0]
	}
	return
}

// Empty 判空
func (t *Btree) Empty() bool {
	return t.size <= 0
}

// Order 当前阶数
func (t *Btree) Order() int {
	return t.order
}

// Clear 清空B-树
func (t *Btree) Clear() int {
	size := t.size
	t.hot = nil
	t.root = nil
	t.size = 0
	return size
}

// Search 元素查找
func (t *Btree) Search(item interface{}) interface{} {
	node, i := t.searchAt(t.root, item)
	if node == nil {
		return nil
	}
	return node.items[i]
}

// Insert 元素新增：
// 算法：
// 1、找到元素 x 对于节点，存在则返回。
// 2、令最后访问节点为 x， 在 x 中查找元素适合的插入位置 i， 并将其插入。
// 4、x上溢修复。
func (t *Btree) Insert(item interface{}) {
	if t.Empty() {
		t.size  
		t.root = emptyBtreeNode(nil)
		t.root.insertItemAt(0, item)
		t.root.insertChildAt(1, nil)
		return
	}
	node, i := t.searchAt(t.root, item)
	if node != nil {
		node.items[i] = item
		return
	}
	t.size  
	node = t.hot
	i, _ = node.find(t.keyComparator, item)
	node.insertItemAt(i, item)
	node.insertChildAt(i 1, nil)
	t.solveOverflow(node)
}

// Remove 元素删除：
// 算法：
// 1、找到元素 x 对于节点。
// 2、若节点 x 不为叶节点，则交换 x 与其后继节点。
// 3、在x中删除对于元素。
// 4、在x下溢修复。
func (t *Btree) Remove(item interface{}) {
	node, i := t.searchAt(t.root, item)
	if node == nil {
		return
	}
	t.size--
	if node.children[0] != nil {
		suc := node.children[i 1]
		for suc.children[0] != nil {
			suc = suc.children[0]
		}
		node.items[i], suc.items[0] = suc.items[0], node.items[i]
		node, i = suc, 0
	}
	node.removeItemAt(i)
	node.removeChildAt(i   1)
	t.solveUnderflow(node)
}

// 层序遍历打印当前树中节点信息
func (t *Btree) levelInfo() string {
	var info []string
	if t.Empty() {
		return "[]"
	}
	que := queue.New()
	que.Push(t.root)
	for !que.Empty() {
		var tmp string
		size := que.Size()
		for ; size > 0; size-- {
			node := que.Pop().(*btreeNode)
			tmp  = fmt.Sprintf("%v ", node.items)
			if node.children[0] != nil {
				for _, child := range node.children {
					que.Push(child)
				}
			}
		}
		tmp = strings.TrimRight(tmp, " ")
		info = append(info, tmp)
	}
	return "["   strings.Join(info, "\n")   "]"
}

这篇好文章是转载于：学新通技术网