日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

這是B-Tree合集的第二部分。在這一部分會實現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)和Search。

創(chuàng)新互聯(lián)專注于網(wǎng)站建設(shè)|網(wǎng)站建設(shè)維護|優(yōu)化|托管以及網(wǎng)絡(luò)推廣，積累了大量的網(wǎng)站設(shè)計與制作經(jīng)驗，為許多企業(yè)提供了網(wǎng)站定制設(shè)計服務(wù)，案例作品覆蓋公路鉆孔機等行業(yè)。能根據(jù)企業(yè)所處的行業(yè)與銷售的產(chǎn)品，結(jié)合品牌形象的塑造，量身建設(shè)品質(zhì)網(wǎng)站。

基本數(shù)據(jù)結(jié)構(gòu)

根據(jù)Part1介紹的B-Tree的屬性，我們可以建立node和tree兩個基本的數(shù)據(jù)結(jié)構(gòu)

type BTreeNode struct {
  keys []int        // An array of keys
  t    int          // Minimum degree
  c    []*BTreeNode // An array of child pointers
  n    int          // Current number of keys
  leaf bool         // Is true when node is leaf. Otherwise false
}

type BTree struct {
  root *BTreeNode // Pointer to root node
  t    int        // Minimum degree
}

// Constructor for BTreeNode
func NewBTreeNode(t int, leaf bool) *BTreeNode {
  return &BTreeNode{
    keys: make([]int, t<<1-1),
    t:    t,
    c:    make([]*BTreeNode, t<<1),
    leaf: leaf,
  }
}

// Constructor (Initializes tree as empty)
func NewBTree(t int) *BTree {
  return &BTree{
    t: t,
  }
}

Search

比如要在下面這個B樹中找120

那么從Part1可知，我們都會從root出發(fā)，所以有下面3步即可找到120

可見，可以用下面的偽代碼來描述Search方法

對于紅框里面的，意思是找第一個大于等于k的鍵index，但是偽代碼用了順序查找的方法，即O(N)。從Part1可知，node中的元素是從小到大排列的，所以我們可以用二分的方式優(yōu)化。

// find the index of the first key which is greater or equal to k
func findGE(s []int, left, right, k int) int {
  if left <= right {
    mid := left + (right-left)>>1

    if k == s[mid] {
      return mid
    } else if k > s[mid] {
      return findGE(s, mid+1, right, k)
    } else {
      return findGE(s, left, mid-1, k)
    }
  }

  return left
}

下面是Search的代碼

func (n *BTreeNode) search(k int) *BTreeNode {
  i := findGE(n.keys, 0, n.n-1, k)

  if n.keys[i] == k {
    return n
  }
  if n.leaf {
    return nil
  }
  return n.c[i].search(k)
}

func (t *BTree) Search(k int) *BTreeNode {
  if t.root != nil {
    return t.root.search(k)
  }

  return nil
}

在下次的Part3中，將實現(xiàn)B-Tree的Insert。

新聞標(biāo)題：我們一起再聊聊B-Tree的Golang實現(xiàn)
轉(zhuǎn)載注明：http://www.5511xx.com/article/dpgoihp.html