SHARE
TWEET

Untitled

a guest Aug 22nd, 2019 63 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top