• API
• FAQ
• Tools
• Archive
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.

Top