日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

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

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

根據(jù)Part1介紹的B-Tree的屬性，我們可以建立node和tree兩個(gè)基本的數(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

比如要在下面這個(gè)B樹中找120

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

可見，可以用下面的偽代碼來(lái)描述Search方法

對(duì)于紅框里面的，意思是找第一個(gè)大于等于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中，將實(shí)現(xiàn)B-Tree的Insert。

當(dāng)前文章：我們一起再聊聊B-Tree的Golang實(shí)現(xiàn)
網(wǎng)站鏈接：http://www.dlmjj.cn/article/dpgoihp.html