fork download
copy 
  1. /*
  2. B木(B-tree)は完全平衡木である。
  3. 大量のレコードを二次記憶装置に蓄えて、その上で探索を行う用途に適している。
  4.  
  5. B木は多分木(multiway tree)である。
  6. 次の3つの制約を持つ。
  7. (1) 内点の子供の数の最大はmである。mは3以上の正の定数とする。
  8. (2) 内点の子供の数の最小はm/2の切り上げた値である(仮にmが3ならば最小は2)。
  9.     例外として、根の子供の数の最小は2である。
  10. (3) 根から端点までの深さはどの端点についても同じである。
  11.  
  12. B木は端点(葉)と内点(葉以外の頂点)をまったく別の種類のものとして扱う。
  13. 内点はレコードを持たず、辺と辺の境目を示すキーの値だけを(最大でm-1個)持つ。
  14. 端点は二次記憶装置上のレコードの位置を持つ。
  15. (このプログラムでは単に構造体recordのポインタを持たせている)
  16.  
  17. B木の操作の計算量はいずれもO(log2(n))だが、これにかかる係数は、
  18. 内点における配列操作などでO(m)かかるために、AVL木などに比べて大きくなる。
  19. しかし主記憶上での操作に少々時間がかかろうと、二次記憶装置へのアクセス回数を
  20. 減らすことができるなら、それは問題ではない。
  21. */
  22. package main
  23.  
  24. import (
  25. 	f "fmt"
  26. )
  27.  
  28. // 何分木のB木にするか
  29. const (
  30. 	MaxChild = 6
  31. 	MinChild = 3
  32. )
  33.  
  34. // 木に格納するレコード。
  35. type record struct {
  36. 	key   int
  37. 	value string
  38. }
  39.  
  40. // 内点が持つ辺。
  41. type edge struct {
  42. 	ptr   *vertex // 内点から子への参照
  43. 	bound int     // 辺と辺の境界値
  44. }
  45.  
  46. /*
  47. B木の頂点。
  48. 内点はB木の制約により必ず複数の子を持つ。
  49. childは常にboundの昇順で整列していなければならない。
  50. 境界値child[i].boundに設定する値をbとすると、bは
  51. child[i-1]が持つ子の中で最大のkey < b <= child[i]が持つ子の中で最小のkey
  52. の範囲内で自由に決めて良い。この実装ではchild[i]が持つ子の中で最小のkeyにしている。
  53. */
  54. type vertex struct {
  55. 	tag   int     // 内点か端点か
  56. 	child []edge  // 内点の場合に持つ子への辺
  57. 	data  *record // 端点の場合にもつレコード。
  58. }
  59.  
  60. // vertex.tagに設定する値
  61. const (
  62. 	Internal = iota // 内点
  63. 	External        // 端点
  64. )
  65.  
  66. // 新しい内点を生成し、そのポインタを返す。
  67. func newIntVtx() *vertex {
  68. 	return &vertex{
  69. 		tag:   Internal,
  70. 		child: make([]edge, 0),
  71. 		data:  nil,
  72. 	}
  73. }
  74.  
  75. // データkey,valueを格納する新しい端点を生成し、そのポインタを返す。
  76. func newExtVtx(key int, value string) *vertex {
  77. 	return &vertex{
  78. 		tag:   External,
  79. 		child: nil,
  80. 		data:  &record{key: key, value: value},
  81. 	}
  82. }
  83.  
  84. // 内点tのフィールドchildに子cを挿入する。O(M)。
  85. func (t *vertex) insertChild(c *vertex) {
  86. 	var bound int
  87. 	if c.tag == External {
  88. 		bound = c.data.key
  89. 	} else {
  90. 		bound = c.child[0].bound
  91. 	}
  92. 	p := 0 // 子cを挿入する位置p
  93. 	for ; p < len(t.child) && t.child[p].bound < bound; p++ {
  94. 	}
  95. 	nc := make([]edge, 0, MaxChild)
  96. 	nc = append(nc, t.child[:p]...)
  97. 	nc = append(nc, edge{c, bound})
  98. 	t.child = append(nc, t.child[p:]...)
  99. }
  100.  
  101. // 内点tの子の中で、キーkeyを持つ端点につながる子の添字を返す。O(log2(M))。
  102. func (t *vertex) locateChild(key int) int {
  103. 	l := 1
  104. 	h := len(t.child) - 1
  105. 	for l <= h {
  106. 		m := (l + h) / 2
  107. 		if key < t.child[m].bound {
  108. 			h = m - 1
  109. 		} else {
  110. 			l = m + 1
  111. 		}
  112. 	}
  113. 	return h
  114. }
  115.  
  116. // 内点tのi番目の子の境界値を更新する。O(1)。
  117. func (t *vertex) updateBound(i int) {
  118. 	c := t.child[i].ptr
  119. 	if c.tag == External {
  120. 		t.child[i].bound = c.data.key
  121. 	} else {
  122. 		t.child[i].bound = c.child[0].bound
  123. 	}
  124. }
  125.  
  126. // 内点tのi番目の子を削除する。O(M)。
  127. func (t *vertex) removeChild(i int) {
  128. 	nc := make([]edge, 0, MaxChild)
  129. 	nc = append(nc, t.child[:i]...)
  130. 	t.child = append(nc, t.child[i+1:]...)
  131. }
  132.  
  133. // 木tの探索。キーがkeyに等しいレコードのポインタを返す。
  134. // そのようなレコードが見つからなかった場合はnilを返す。
  135. func search(t *vertex, key int) *record {
  136. 	if t == nil {
  137. 		return nil
  138. 	}
  139. 	// B木の探索は二分探索木と違って必ず端点まで降りる。
  140. 	for t.tag == Internal {
  141. 		i := t.locateChild(key)
  142. 		t = t.child[i].ptr
  143. 	}
  144. 	// 端点が目的のレコードを持っているとは限らない。
  145. 	if t.data.key != key {
  146. 		return nil
  147. 	}
  148. 	return t.data
  149. }
  150.  
  151. // 木tにデータkey,valueを挿入した木を返す。
  152. func insert(t *vertex, key int, value string) *vertex {
  153. 	if t == nil {
  154. 		// 最小のB木は端点1つから成る。
  155. 		return newExtVtx(key, value)
  156. 	}
  157. 	bro := insertAux(t, key, value)
  158. 	if bro == nil {
  159. 		return t
  160. 	}
  161. 	// 根tと兄弟になる頂点broが出来たときが、木の高さが増える唯一のケース。
  162. 	root := newIntVtx()
  163. 	root.insertChild(t)
  164. 	root.insertChild(bro)
  165. 	return root
  166. }
  167.  
  168. // 関数insertの補助関数。まず探索と同様に端点まで降りて、新しい端点を追加し、
  169. // それに伴う内点の調整を根方向に必要なだけ繰り返す。
  170. // 問題なく挿入が完了した場合、nilを返す。
  171. // 頂点tに子を追加する余裕が無かった場合、新しい頂点を作って返す。
  172. func insertAux(t *vertex, key int, value string) *vertex {
  173. 	if t.tag == External {
  174. 		if t.data.key == key {
  175. 			return nil // 二重登録の場合は何もしない
  176. 		}
  177. 		// 親に端点を追加したよと伝える
  178. 		return newExtVtx(key, value)
  179. 	}
  180. 	i := t.locateChild(key)
  181. 	newborn := insertAux(t.child[i].ptr, key, value)
  182. 	t.updateBound(i)
  183. 	if newborn != nil {
  184. 		t.insertChild(newborn)
  185. 		if MaxChild < len(t.child) {
  186. 			// 新しい内点nと子供達を分け合い、親にnが出来たよと伝える
  187. 			n := newIntVtx()
  188. 			n.child = t.child[MinChild:]
  189. 			t.child = t.child[:MinChild]
  190. 			return n
  191. 		}
  192. 	}
  193. 	return nil
  194. }
  195.  
  196. // 関数removeAuxが関数呼び出し元に返すメッセージ
  197. const (
  198. 	Succeeded = iota // 正常終了
  199. 	Removed          // この頂点を削除したので辺を破棄してください
  200. 	Shrunk           // この頂点の子の数が少なくなりました
  201. )
  202.  
  203. // 木tからキーがkeyに等しいレコードを持つ端点を削除して返す。
  204. func remove(t *vertex, key int) *vertex {
  205. 	if t == nil {
  206. 		return nil
  207. 	}
  208. 	switch removeAux(t, key) {
  209. 	case Removed:
  210. 		return nil
  211. 	case Shrunk:
  212. 		if len(t.child) < 2 {
  213. 			// 1個だけになった子を新たな根とする。木の高さが減る唯一のケース。
  214. 			return t.child[0].ptr
  215. 		}
  216. 	}
  217. 	return t
  218. }
  219.  
  220. // 関数removeの補助関数。まず探索と同様に端点まで降りて、端点を削除し、
  221. // それに伴う内点の調整を根方向に必要なだけ繰り返す。
  222. func removeAux(t *vertex, key int) int {
  223. 	if t.tag == External {
  224. 		if t.data.key == key {
  225. 			return Removed
  226. 		}
  227. 		return Succeeded // keyをもつレコードがなかったけどまあいい
  228. 	}
  229. 	ai := t.locateChild(key)
  230. 	a := t.child[ai].ptr
  231. 	switch removeAux(a, key) {
  232. 	case Removed:
  233. 		t.removeChild(ai)
  234. 		return Shrunk
  235. 	case Shrunk:
  236. 		if len(a.child) < MinChild {
  237. 			bi := next(ai) // aの兄弟bの添字
  238. 			needToRemoveB := reallotChild(a, t.child[bi].ptr)
  239. 			t.updateBound(ai)
  240. 			if needToRemoveB {
  241. 				t.removeChild(bi)
  242. 				return Shrunk
  243. 			}
  244. 			t.updateBound(bi)
  245. 		}
  246. 	}
  247. 	return Succeeded
  248. }
  249.  
  250. // 列の添字iの隣の添字を決める
  251. func next(i int) int {
  252. 	if i == 0 {
  253. 		return 1
  254. 	}
  255. 	return i - 1
  256. }
  257.  
  258. // 子供が足りない内点aに、内点bの子供を移して、a,b共に制約を満たすようにする。
  259. // 共に満たせるほど子供がいなかったら、aに全子供を持たせてtrueを返す。
  260. func reallotChild(a, b *vertex) bool {
  261. 	acl := len(a.child)
  262. 	bcl := len(b.child)
  263. 	astb := a.child[0].bound < b.child[0].bound
  264. 	if acl+bcl < MinChild*2 {
  265. 		if astb {
  266. 			a.child = append(a.child, b.child...)
  267. 		} else {
  268. 			a.child = append(b.child, a.child...)
  269. 		}
  270. 		return true // bはその役目を終えた
  271. 	}
  272. 	p := (acl + bcl) / 2
  273. 	if astb {
  274. 		p = bcl - p
  275. 		a.child = append(a.child, b.child[:p]...)
  276. 		b.child = b.child[p:]
  277. 	} else {
  278. 		nc := make([]edge, 0, MaxChild)
  279. 		nc = append(nc, b.child[p:]...)
  280. 		a.child = append(nc, a.child...)
  281. 		b.child = b.child[:p]
  282. 	}
  283. 	return false
  284. }
  285.  
  286.  
  287.  
  288. // 木tの各頂点を深さ毎に表示する。内点は {境界値リスト} 端点は [キー] の形で表す。
  289. func printTree(t *vertex) {
  290. 	if t == nil {
  291. 		f.Println(t)
  292. 		return
  293. 	}
  294. 	a := traversal(t, 0, [][]*vertex{})
  295. 	for depth, vs := range a {
  296. 		f.Printf("depth %v: ", depth)
  297. 		for _, v := range vs {
  298. 			if v.tag == Internal {
  299. 				printIntVtx(v)
  300. 			} else {
  301. 				f.Printf("[%v]", v.data.key)
  302. 			}
  303. 		}
  304. 		f.Println()
  305. 	}
  306. 	f.Println()
  307. }
  308.  
  309. // 内点vを表示する。
  310. func printIntVtx(v *vertex) {
  311. 	f.Print("{")
  312. 	for i := 0; i < len(v.child); i++ {
  313. 		f.Printf("%v", v.child[i].bound)
  314. 		if i < len(v.child)-1 {
  315. 			f.Print(" ")
  316. 		}
  317. 	}
  318. 	f.Print("}  ")
  319. }
  320.  
  321. // 木tの全頂点を深さ毎にまとめた二次元列を返す。例えばa[1][3]は深さ1の3番目の頂点。
  322. func traversal(t *vertex, depth int, a [][]*vertex) [][]*vertex {
  323. 	if len(a) == depth {
  324. 		a = append(a, []*vertex{})
  325. 	}
  326. 	a[depth] = append(a[depth], t)
  327. 	if t.tag == Internal {
  328. 		for _, c := range t.child {
  329. 			a = traversal(c.ptr, depth+1, a)
  330. 		}
  331. 	}
  332. 	return a
  333. }
  334.  
  335. func main() {
  336. 	var t *vertex
  337.  
  338. 	f.Println("/* 最小のB木は端点1つだけから成る */")
  339. 	t = insert(t, 1, "A")
  340. 	printTree(t)
  341.  
  342. 	f.Println("/* データが2件になると内点1つと端点2つになる */")
  343. 	t = insert(t, 2, "B")
  344. 	printTree(t)
  345.  
  346. 	f.Println("/* key=1のデータを削除すると端点1つに戻る */")
  347. 	t = remove(t, 1)
  348. 	printTree(t)
  349.  
  350. 	f.Println("/* 5件のデータ[1,3,4,5,6]を追加して */")
  351. 	for _, x := range []int{1, 3, 4, 5, 6} {
  352. 		t = insert(t, x, string(x+64))
  353. 	}
  354. 	printTree(t)
  355.  
  356. 	f.Println("/* key=7のデータを追加して内点の分割と木の高さの増加を観察する */")
  357. 	t = insert(t, 7, "G")
  358. 	printTree(t)
  359.  
  360. 	f.Println("/* 3件のデータ[2,4,6]を削除して変化を観察する */")
  361. 	for _, x := range []int{2, 4, 6} {
  362. 		t = remove(t, x)
  363. 		printTree(t)
  364. 	}
  365.  
  366. 	f.Println("/* 昇順ソート済のデータ24件を順に挿入すると */")
  367. 	t = nil
  368. 	for i := 1; i <= 24; i++ {
  369. 		t = insert(t, i, string(i+64))
  370. 	}
  371. 	printTree(t)
  372.  
  373. 	f.Println("/* 降順ソート済のデータ24件を順に挿入すると */")
  374. 	t = nil
  375. 	for i := 24; 1 <= i; i-- {
  376. 		t = insert(t, i, string(i+64))
  377. 	}
  378. 	printTree(t)
  379.  
  380. 	f.Println("/* てきとーに探索してみる */")
  381. 	f.Printf("0を探索: %v \n", search(t, 0))
  382. 	f.Printf("1を探索: %v \n", search(t, 1))
  383. 	f.Printf("5を探索: %v \n", search(t, 5))
  384. 	f.Printf("7を探索: %v \n", search(t, 7))
  385. 	f.Printf("17を探索: %v \n", search(t, 17))
  386. 	f.Printf("20を探索: %v \n", search(t, 20))
  387. 	f.Printf("24を探索: %v \n", search(t, 24))
  388. 	f.Printf("25を探索: %v \n", search(t, 25))
  389. }
Success #stdin #stdout 0s 420672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
/* 最小のB木は端点1つだけから成る */
depth 0: [1]

/* データが2件になると内点1つと端点2つになる */
depth 0: {1 2}  
depth 1: [1][2]

/* key=1のデータを削除すると端点1つに戻る */
depth 0: [2]

/* 5件のデータ[1,3,4,5,6]を追加して */
depth 0: {1 2 3 4 5 6}  
depth 1: [1][2][3][4][5][6]

/* key=7のデータを追加して内点の分割と木の高さの増加を観察する */
depth 0: {1 4}  
depth 1: {1 2 3}  {4 5 6 7}  
depth 2: [1][2][3][4][5][6][7]

/* 3件のデータ[2,4,6]を削除して変化を観察する */
depth 0: {1 5}  
depth 1: {1 3 4}  {5 6 7}  
depth 2: [1][3][4][5][6][7]

depth 0: {1 3 5 6 7}  
depth 1: [1][3][5][6][7]

depth 0: {1 3 5 7}  
depth 1: [1][3][5][7]

/* 昇順ソート済のデータ24件を順に挿入すると */
depth 0: {1 10}  
depth 1: {1 4 7}  {10 13 16 19}  
depth 2: {1 2 3}  {4 5 6}  {7 8 9}  {10 11 12}  {13 14 15}  {16 17 18}  {19 20 21 22 23 24}  
depth 3: [1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22][23][24]

/* 降順ソート済のデータ24件を順に挿入すると */
depth 0: {1 5 9 13 17 21}  
depth 1: {1 2 3 4}  {5 6 7 8}  {9 10 11 12}  {13 14 15 16}  {17 18 19 20}  {21 22 23 24}  
depth 2: [1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22][23][24]

/* てきとーに探索してみる */
0を探索: <nil> 
1を探索: &{1 A} 
5を探索: &{5 E} 
7を探索: &{7 G} 
17を探索: &{17 Q} 
20を探索: &{20 T} 
24を探索: &{24 X} 
25を探索: <nil>
https://ideone.com/ZL2dLh
B木
language:
Go (go 1.12.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!