Guest User

Untitled

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