fork download
copy 
  1. /*
  2. 二分探索木が極端に片寄った形になったら、もっと性能の良い形、即ち左右の
  3. バランスの取れた形に直す。このような木を平衡木(balanced tree)と呼ぶ。
  4.  
  5. 木の作り直しはレコード(頂点)の挿入や削除の際に行われる。
  6. その計算量がO(n)を超えるようならば、列の二分探索で十分であり、
  7. 平衡木を採用する意味がない。
  8. 従って、作り直しの計算量はO(log2(n))以下に抑えたい。
  9. この観点から、常に完全二分木を保つのは望ましくない。ほどほどで良い。
  10.  
  11. 片寄り方に限度を設けるため、次の制約を持つ二分探索木を、AVL-treeと呼ぶ。
  12. 制約：どの頂点においても、その左部分木の高さと右部分木の高さの差が
  13. +1,0,-1のいずれかでなければならない。
  14. */
  15. package main
  16.  
  17. import (
  18. 	"fmt"
  19. )
  20.  
  21. // AVL木(の頂点)。
  22. // 同じ木の中でkeyは一意であること。
  23. // 平衡係数の初期値は0。左部分木の方が高いほど+1、右部分木の方が高いほど-1する。
  24. // 平衡係数が2以上または-2以下の頂点が出来たとき木を再構成する。
  25. type btree struct {
  26. 	key     int
  27. 	value   string
  28. 	left    *btree
  29. 	right   *btree
  30. 	balance int // 平衡係数
  31. }
  32.  
  33. // 探索。木tの中でキーがkeyと一致する頂点のvalueを返す。
  34. // そのような頂点が見つからなかった場合は空文字列を返す。
  35. func search(t *btree, key int) string {
  36. 	switch {
  37. 	case t == nil:
  38. 		return ""
  39. 	case t.key < key:
  40. 		return search(t.right, key)
  41. 	case key < t.key:
  42. 		return search(t.left, key)
  43. 	}
  44. 	return t.value
  45. }
  46.  
  47. // 木tの適切な位置に新しい頂点を挿入した木を返す。
  48. // valueに空文字列は使わないこと
  49. func insert(t *btree, key int, value string) *btree {
  50. 	t, _ = insertAux(t, key, value)
  51. 	return t
  52. }
  53.  
  54. // 木tの適切な位置に新しい頂点を挿入した木を返す。
  55. // また、木の高さが増えたかどうかのフラグも返す。
  56. func insertAux(t *btree, key int, value string) (*btree, bool) {
  57. 	var gu bool // 木の高さが増えたらtrue
  58. 	switch {
  59. 	case t == nil:
  60. 		t = &btree{key: key, value: value, balance: 0}
  61. 		gu = true
  62. 	case key < t.key:
  63. 		t.left, gu = insertAux(t.left, key, value)
  64. 		if gu {
  65. 			t.balance++
  66. 			if t.balance < 2 {
  67. 				gu = !(t.balance == 0) // 平衡になったということは、高さが増えてないということ
  68. 			} else if 0 < t.left.balance {
  69. 				t, gu = leftSingleRotation(t), false
  70. 			} else {
  71. 				t, gu = leftDoubleRotation(t), false
  72. 			}
  73. 		}
  74. 	case t.key < key:
  75. 		t.right, gu = insertAux(t.right, key, value)
  76. 		if gu {
  77. 			t.balance--
  78. 			if -2 < t.balance {
  79. 				gu = !(t.balance == 0)
  80. 			} else if t.right.balance < 0 {
  81. 				t, gu = rightSingleRotation(t), false
  82. 			} else {
  83. 				t, gu = rightDoubleRotation(t), false
  84. 			}
  85. 		}
  86. 	}
  87. 	return t, gu
  88. }
  89.  
  90. // 木tからkeyを持つ頂点を削除した木を返す。
  91. func remove(t *btree, key int) *btree {
  92. 	t, _ = removeAux(t, key)
  93. 	return t
  94. }
  95.  
  96. // 木tからkeyを持つ頂点を削除した木を返す。
  97. // また、木の高さが減ったかどうかのフラグも返す。
  98. func removeAux(t *btree, key int) (*btree, bool) {
  99. 	var su bool // 木の高さが減ったらtrue
  100. 	switch {
  101. 	case t == nil:
  102. 		su = false
  103. 	case key < t.key:
  104. 		t.left, su = removeAux(t.left, key)
  105. 		if su {
  106. 			t.balance--
  107. 			if -2 < t.balance {
  108. 				su = (t.balance == 0) // 平衡になったということは、高さが減ったということ
  109. 			} else if t.right.balance < 0 {
  110. 				t, su = rightSingleRotation(t), true
  111. 			} else {
  112. 				t, su = rightDoubleRotation(t), true
  113. 			}
  114. 		}
  115. 	case t.key < key:
  116. 		t.right, su = removeAux(t.right, key)
  117. 		if su {
  118. 			t.balance++
  119. 			if t.balance < 2 {
  120. 				su = (t.balance == 0)
  121. 			} else if 0 < t.left.balance {
  122. 				t, su = leftSingleRotation(t), true
  123. 			} else {
  124. 				t, su = leftDoubleRotation(t), true
  125. 			}
  126. 		}
  127. 	default:
  128. 		t, su = removeRoot(t), true
  129. 	}
  130. 	return t, su
  131. }
  132.  
  133. // 根tが表す木からtを削除して返す。
  134. func removeRoot(t *btree) *btree {
  135. 	// 左子が無いなら右子を持ちあげるだけ
  136. 	if t.left == nil {
  137. 		return t.right
  138. 	}
  139. 	// 左子の右子がないということは、左子はtの次に大きい頂点である
  140. 	if t.left.right == nil {
  141. 		l := t.left
  142. 		l.right = t.right
  143. 		l.recalcBalance()
  144. 		return l
  145. 	}
  146. 	// まずtの次の次に大きい頂点pを探しだして
  147. 	var p *btree
  148. 	for p = t.left; p.right.right != nil; p = p.right {
  149. 	}
  150. 	// tの次に大きい頂点sを新しい根とする
  151. 	s := p.right
  152. 	p.right = s.left
  153. 	p.recalcBalance()
  154. 	s.left = t.left
  155. 	s.right = t.right
  156. 	s.recalcBalance()
  157. 	return s
  158. }
  159.  
  160. // 頂点tが左に、かつその左部分木が左に片寄っている場合、
  161. // 一重回転してt.leftを根にする。
  162. func leftSingleRotation(t *btree) *btree {
  163. 	l := t.left
  164. 	t.left = l.right
  165. 	l.right = t
  166. 	t.recalcBalance()
  167. 	l.recalcBalance()
  168. 	return l
  169. }
  170.  
  171. // 頂点tが左に、かつその左部分木が右に片寄っている場合、
  172. // 二重回転してt.leftの子を根にする。
  173. func leftDoubleRotation(t *btree) *btree {
  174. 	l := t.left
  175. 	lr := l.right
  176. 	if lr.right != nil {
  177. 		l.right = nil
  178. 	} else {
  179. 		l.right = lr.left
  180. 	}
  181. 	lr.left = l
  182. 	l.recalcBalance()
  183. 	t.left = lr
  184. 	return leftSingleRotation(t)
  185. }
  186.  
  187. // 頂点tが右に、かつその右部分木が右に片寄っている場合、
  188. // 一重回転してt.rightを根にする。
  189. func rightSingleRotation(t *btree) *btree {
  190. 	r := t.right
  191. 	t.right = r.left
  192. 	r.left = t
  193. 	t.recalcBalance()
  194. 	r.recalcBalance()
  195. 	return r
  196. }
  197.  
  198. // 頂点tが右に、かつその右部分木が左に片寄っている場合、
  199. // 二重回転してt.rightの子を根にする。
  200. func rightDoubleRotation(t *btree) *btree {
  201. 	r := t.right
  202. 	rr := r.left
  203. 	if rr.left != nil {
  204. 		r.left = nil
  205. 	} else {
  206. 		r.left = rr.right
  207. 	}
  208. 	rr.right = r
  209. 	r.recalcBalance()
  210. 	t.right = rr
  211. 	return rightSingleRotation(t)
  212. }
  213.  
  214. // 平衡係数を再計算する。
  215. func (t *btree) recalcBalance() {
  216. 	switch {
  217. 	case t.left == nil && t.right == nil:
  218. 		t.balance = 0
  219. 	case t.right == nil:
  220. 		t.balance = 1
  221. 	case t.left == nil:
  222. 		t.balance = -1
  223. 	default:
  224. 		lgc := t.left.left != nil || t.left.right != nil   // 左の孫を持つならtrue
  225. 		rgc := t.right.left != nil || t.right.right != nil // 右の孫を持つならtrue
  226. 		switch {
  227. 		case lgc && !rgc:
  228. 			t.balance = 1
  229. 		case !lgc && rgc:
  230. 			t.balance = -1
  231. 		default:
  232. 			t.balance = 0
  233. 		}
  234. 	}
  235. }
  236.  
  237.  
  238.  
  239. // 頂点のkey兼valueとしたい0個以上の整数を受け取り、tを生成して返す
  240. func buildTree(keys []int) *btree {
  241. 	var t *btree
  242. 	for _, k := range keys {
  243. 		t = insert(t, k, fmt.Sprint(k))
  244. 	}
  245. 	return t
  246. }
  247.  
  248. // 木tの各頂点の値と平行係数を表示する
  249. func pt(t *btree) {
  250. 	dq := make([]*btree, 0, 100) // 同じ深さの節を保持するキュー
  251. 	bf := make([]*btree, 0, 100) // dqに追加予定の節を一時保存するキュー
  252. 	bf = append(bf, t)
  253. 	// 同じ深さの節を全て表示したら、次の深さの節の処理に移ることの繰り返し
  254. 	var e *btree
  255. 	for allIsNil(bf) == false {
  256. 		dq = append(dq, bf...)
  257. 		bf = bf[len(bf):]
  258. 		for 0 < len(dq) {
  259. 			e, dq = dq[0], dq[1:]
  260. 			if e != nil {
  261. 				fmt.Printf("[%v:%v] ", e.value, e.balance)
  262. 				bf = append(bf, e.left)
  263. 				bf = append(bf, e.right)
  264. 			} else {
  265. 				fmt.Printf("[_:_] ")
  266. 				bf = append(bf, nil)
  267. 				bf = append(bf, nil)
  268. 			}
  269. 		}
  270. 		fmt.Println()
  271. 	}
  272. 	fmt.Println()
  273. }
  274.  
  275. // xsの全要素がnilであるときtrueを返す
  276. func allIsNil(xs []*btree) bool {
  277. 	res := true
  278. 	for _, x := range xs {
  279. 		res = (res && x == nil)
  280. 	}
  281. 	return res
  282. }
  283.  
  284. func main() {
  285. 	var t *btree
  286.  
  287. 	t = buildTree([]int{50, 30, 70, 20, 40, 60, 80, 25, 55, 65, 75, 85, 90})
  288. 	pt(t)
  289. 	fmt.Println("---- キー20を削除して構造の変化を見てみる")
  290. 	t = remove(t, 20)
  291. 	pt(t)
  292. }
  293.  
Success #stdin #stdout 0s 420608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[50:-1] 
[30:1] [70:-1] 
[20:-1] [40:0] [60:0] [80:-1] 
[_:_] [25:0] [_:_] [_:_] [55:0] [65:0] [75:0] [85:-1] 
[_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [_:_] [90:0] 

---- キー20を削除して構造の変化を見てみる
[70:0] 
[50:0] [80:-1] 
[30:0] [60:0] [75:0] [85:-1] 
[25:0] [40:0] [55:0] [65:0] [_:_] [_:_] [_:_] [90:0]
https://ideone.com/dPZn2r
AVL木
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!