go语言学习笔记:B-tree

沈锋 · · 5545 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

这段时间对google出的go语言比较感兴趣。比较看中的原因:

  1. Robert Griesemer, Rob Pike, Ken Thompson。 Unix,UTF8,正则表达式等等有他诸多贡献。 Rob Pike:Unix,UTF8,Plan 9等,并且几十年的并发开发。Robert Griesemer: hotspot jvm。 他们都是计算机行业的牛人, 牛人出品,值得一试。
  2. go简单明了
  3. 通过go goroutine select channel来对解决并发问题。

用它写程序是一种学习方法,就试着写了一下B-tree,回忆一下大学的课程

package btree
import (
	"bytes"
	"fmt"
)
type Key int
type Node struct {
	Leaf     bool
	N        int
	Keys     []Key
	Children []*Node
}
func (x *Node) Search(k Key) (n *Node, idx int) {
	i := 0
	for i < x.N && x.Keys[i] < k {
		i += 1
	}
	if i < x.N && k == x.Keys[i] {
		n, idx = x, i
	} else if x.Leaf == false {
		n, idx = x.Children[i].Search(k)
	}
	return
}
func newNode(n, branch int, leaf bool) *Node {
	return &Node{
		Leaf:     leaf,
		N:        n,
		Keys:     make([]Key, branch*2-1),
		Children: make([]*Node, branch*2),
	}
}
func (parent *Node) Split(branch, idx int) { //  idx is Children's index
	full := parent.Children[idx]
	// make a new node, copy full's right most to it
	n := newNode(branch-1, branch, full.Leaf)
	for i := 0; i < branch-1; i++ {
		n.Keys[i] = full.Keys[i+branch]
		n.Children[i] = full.Children[i+branch]
	}
	n.Children[branch-1] = full.Children[2*branch-1] // copy last child
	full.N = branch - 1 // is half full now, copied to n(new one)
	// shift parent, add new key and children
	for i := parent.N; i > idx; i-- {
		parent.Children[i] = parent.Children[i-1]
		parent.Keys[i+1] = parent.Keys[i]
	}
	parent.Keys[idx] = full.Keys[branch-1]
	parent.Children[idx+1] = n
	parent.N += 1
}
func (tree *Btree) Insert(k Key) {
	root := tree.Root
	if root.N == 2*tree.branch-1 {
		s := newNode(0, tree.branch, false)
		tree.Root = s
		s.Children[0] = root
		s.Split(tree.branch, 0)
		s.InsertNonFull(tree.branch, k)
	} else {
		root.InsertNonFull(tree.branch, k)
	}
}
func (x *Node) InsertNonFull(branch int, k Key) {
	i := x.N
	if x.Leaf {
		for i > 0 && k < x.Keys[i-1] {
			x.Keys[i] = x.Keys[i-1]
			i -= 1
		}
		x.Keys[i] = k
		x.N += 1
	} else {
		for i > 0 && k < x.Keys[i-1] {
			i -= 1
		}
		c := x.Children[i]
		if c.N == 2*branch-1 {
			x.Split(branch, i)
			if k > x.Keys[i] {
				i += 1
			}
		}
		x.Children[i].InsertNonFull(branch, k)
	}
}
func space(n int) string {
	s := ""
	for i := 0; i < n; i++ {
		s += " "
	}
	return s
}
func (x *Node) String() string {
	return fmt.Sprintf("{n=%d, Leaf=%v, Keys=%v, Children=%v}\n",
		x.N, x.Leaf, x.Keys, x.Children)
}
func (tree *Btree) String() string {
	return tree.Root.String()
}
type Btree struct {
	Root   *Node
	branch int
}
func New(branch int) *Btree {
	return &Btree{Root: newNode(0, branch, true), branch: branch}
}
func (tree *Btree) Search(k Key) (n *Node, idx int) {
	return tree.Root.Search(k)
}

有疑问加站长微信联系(非本文作者)

本文来自:A programmer's site

感谢作者:沈锋

查看原文:go语言学习笔记:B-tree

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

5545 次点击  ∙  1 赞  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传