Guest User

Untitled

a guest
Aug 22nd, 2019
61
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import "math"
  2.  
  3. type height int
  4.  
  5. // AVLNode of tree
  6. type AVLNode struct {
  7. key int
  8. h height
  9. left, right *AVLNode
  10. p *AVLNode
  11. }
  12.  
  13. // AVLTree is AVL tree
  14. type AVLTree struct {
  15. null *AVLNode
  16. root *AVLNode
  17. }
  18.  
  19. // CreateAVLTree create a tree
  20. func CreateAVLTree(A []int) AVLTree {
  21. r := AVLTree{
  22. null: &AVLNode{},
  23. }
  24. r.root = r.null
  25. for _, a := range A {
  26. r.Insert(&AVLNode{key: a})
  27. }
  28. return r
  29. }
  30.  
  31. // InOrder performs inorder walk
  32. func (r *AVLTree) InOrder(x *AVLNode) []int {
  33. var A []int
  34. if x != r.null {
  35. A = append(A, r.InOrder(x.left)...)
  36. A = append(A, x.key)
  37. A = append(A, r.InOrder(x.right)...)
  38. }
  39. return A
  40. }
  41.  
  42. // PreOrder performs preorder walk
  43. func (r *AVLTree) PreOrder(x *AVLNode) []int {
  44. var A []int
  45. if x != r.null {
  46. A = append(A, x.key)
  47. A = append(A, r.InOrder(x.left)...)
  48. A = append(A, r.InOrder(x.right)...)
  49. }
  50. return A
  51. }
  52.  
  53. // PostOrder performs postorder walk
  54. func (r *AVLTree) PostOrder(x *AVLNode) []int {
  55. var A []int
  56. if x != r.null {
  57. A = append(A, r.InOrder(x.left)...)
  58. A = append(A, r.InOrder(x.right)...)
  59. A = append(A, x.key)
  60. }
  61. return A
  62. }
  63.  
  64. // Search for a key
  65. func (r *AVLTree) Search(x *AVLNode, k int) *AVLNode {
  66. if x == r.null || k == x.key {
  67. return x
  68. } else if k < x.key {
  69. return r.Search(x.left, k)
  70. } else {
  71. return r.Search(x.right, k)
  72. }
  73. }
  74.  
  75. // QuickSearch for a key
  76. func (r *AVLTree) QuickSearch(x *AVLNode, k int) *AVLNode {
  77. for x != r.null && k != x.key {
  78. if k < x.key {
  79. x = x.left
  80. } else {
  81. x = x.right
  82. }
  83. }
  84. return x
  85. }
  86.  
  87. // Min minimum AVLNode
  88. func (r *AVLTree) Min(x *AVLNode) *AVLNode {
  89. for x.left != r.null {
  90. x = x.left
  91. }
  92. return x
  93. }
  94.  
  95. // Max maximum AVLNode
  96. func (r *AVLTree) Max(x *AVLNode) *AVLNode {
  97. for x.right != r.null {
  98. x = x.right
  99. }
  100. return x
  101. }
  102.  
  103. // Successor previous AVLNode
  104. func (r *AVLTree) Successor(x *AVLNode) *AVLNode {
  105. if x.right != r.null {
  106. return r.Min(x.right)
  107. }
  108. y := x.p
  109. for y != r.null && x == y.right {
  110. x, y = y, y.p
  111. }
  112. return y
  113. }
  114.  
  115. // Preccessor post AVLNode
  116. func (r *AVLTree) Preccessor(x *AVLNode) *AVLNode {
  117. if x.left != r.null {
  118. return r.Max(x.left)
  119. }
  120. y := x.p
  121. for y != r.null && x == y.left {
  122. x, y = y, y.p
  123. }
  124. return y
  125. }
  126.  
  127. func (r *AVLTree) leftRotate(x *AVLNode) {
  128. y := x.right
  129. x.right = y.left
  130. if y.left != r.null {
  131. y.left.p = x
  132. }
  133. y.p = x.p
  134. if x.p == r.null {
  135. r.root = y
  136. } else if x == x.p.left {
  137. x.p.left = y
  138. } else {
  139. x.p.right = y
  140. }
  141. y.left = x
  142. x.p = y
  143. x.h = max(x.left.h, x.right.h) + 1
  144. y.h = max(y.left.h, y.right.h) + 1
  145. }
  146.  
  147. func (r *AVLTree) rightRotate(x *AVLNode) {
  148. y := x.left
  149. x.left = y.right
  150. if y.right != r.null {
  151. y.left.p = x
  152. }
  153. y.p = x.p
  154. if x.p == r.null {
  155. r.root = y
  156. } else if x == x.p.left {
  157. x.p.left = y
  158. } else {
  159. x.p.right = y
  160. }
  161. y.right = x
  162. x.p = y
  163. x.h = max(x.left.h, x.right.h) + 1
  164. y.h = max(y.left.h, y.right.h) + 1
  165. }
  166.  
  167. func max(T ...height) height {
  168. max := height(0)
  169. for _, t := range T {
  170. if t > max {
  171. max = t
  172. }
  173. }
  174. return max
  175. }
  176.  
  177. func (r *AVLTree) balance(z *AVLNode) {
  178. for z != r.null {
  179. if z.left.h > z.right.h+1 {
  180. if z.left.right.h > z.left.left.h {
  181. r.leftRotate(z.left)
  182. }
  183. r.rightRotate(z)
  184. z = z.p
  185. } else if z.right.h > z.left.h+1 {
  186. if z.right.left.h > z.right.right.h {
  187. r.rightRotate(z.right)
  188. }
  189. r.leftRotate(z)
  190. z = z.p
  191. } else {
  192. z.h = max(z.left.h, z.right.h) + 1
  193. }
  194. z = z.p
  195. }
  196. }
  197.  
  198. // Insert a AVLNode
  199. func (r *AVLTree) Insert(z *AVLNode) {
  200. y, x := r.null, r.root
  201. for x != r.null {
  202. y = x
  203. if z.key < x.key {
  204. x = x.left
  205. } else {
  206. x = x.right
  207. }
  208. }
  209. z.p = y
  210. if y == r.null {
  211. r.root = z
  212. } else if z.key < y.key {
  213. y.left = z
  214. } else {
  215. y.right = z
  216. }
  217. z.left = r.null
  218. z.right = r.null
  219. z.h = 1
  220. r.balance(z.p)
  221. }
  222.  
  223. func (r *AVLTree) transplant(u, v *AVLNode) {
  224. if u.p == r.null {
  225. r.root = v
  226. } else if u == u.p.left {
  227. u.p.left = v
  228. } else {
  229. u.p.right = v
  230. }
  231. v.p = u.p
  232. }
  233.  
  234. // Delete a AVLNode
  235. func (r *AVLTree) Delete(z *AVLNode) {
  236. y, x := z, z
  237. if z.left == r.null {
  238. x = z.right
  239. r.transplant(z, z.right)
  240. } else if z.right == r.null {
  241. x = z.left
  242. r.transplant(z, z.left)
  243. } else {
  244. y = r.Min(z.right)
  245. x := y.right
  246. if y.p == z {
  247. x.p = y
  248. } else {
  249. r.transplant(y, y.right)
  250. y.right = z.right
  251. y.right.p = y
  252. }
  253. r.transplant(z, y)
  254. y.left = z.left
  255. y.left.p = y
  256. }
  257. r.balance(x.p)
  258. }
  259.  
  260. func (r *AVLTree) isBalance(n *AVLNode) bool {
  261. if n == r.null {
  262. return true
  263. }
  264. if math.Abs(float64(n.left.h-n.right.h)) >= 2 {
  265. return false
  266. }
  267. return r.isBalance(n.left) && r.isBalance(n.right)
  268. }
RAW Paste Data