fork download
  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
stdin
Standard input is empty
stdout
[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]