SHARE
TWEET

Untitled

a guest Aug 22nd, 2019 60 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
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