1// SPDX-License-Identifier: ISC
2// Copyright (c) 2014-2020 Bitmark Inc.
3// Use of this source code is governed by an ISC
4// license that can be found in the LICENSE file.
5
6package avl
7
8// delete: tree balancer
9func balanceLeft(pp **Node) bool {
10	h := true
11	p := *pp
12	// h; left branch has shrunk
13	if -1 == p.balance {
14		p.balance = 0
15	} else if 0 == p.balance {
16		p.balance = 1
17		h = false
18	} else { // balance = 1, rebalance
19		p1 := p.right
20		if p1.balance >= 0 {
21			// single RR rotation
22			p.right = p1.left
23			p1.left = p
24			if 0 == p1.balance {
25				p.balance = 1
26				p1.balance = -1
27				h = false
28			} else {
29				p.balance = 0
30				p1.balance = 0
31			}
32
33			nn := 1 + p.leftNodes + p1.leftNodes
34			p.rightNodes = p1.leftNodes
35			p1.leftNodes = nn
36
37			p1.up = p.up
38			p.up = p1
39			if nil != p.right {
40				p.right.up = p
41			}
42
43			*pp = p1
44		} else {
45			// double RL rotation
46			p2 := p1.left
47			p1.left = p2.right
48			p2.right = p1
49			p.right = p2.left
50			p2.left = p
51			if +1 == p2.balance {
52				p.balance = -1
53			} else {
54				p.balance = 0
55			}
56			if -1 == p2.balance {
57				p1.balance = 1
58			} else {
59				p1.balance = 0
60			}
61			p2.balance = 0
62
63			nl := 1 + p.leftNodes + p2.leftNodes
64			nr := 1 + p2.rightNodes + p1.rightNodes
65
66			p.rightNodes = p2.leftNodes
67			p1.leftNodes = p2.rightNodes
68
69			p2.leftNodes = nl
70			p2.rightNodes = nr
71
72			p2.up = p.up
73			if nil != p.right {
74				p.right.up = p
75			}
76			if nil != p1.left {
77				p1.left.up = p1
78			}
79			p.up = p2
80			p1.up = p2
81
82			*pp = p2
83		}
84	}
85	return h
86}
87
88// delete: tree balancer
89func balanceRight(pp **Node) bool {
90	h := true
91	p := *pp
92	// h; right branch has shrunk
93	if 1 == p.balance {
94		p.balance = 0
95	} else if 0 == p.balance {
96		p.balance = -1
97		h = false
98	} else { // balance = -1, rebalance
99		p1 := p.left
100		if p1.balance <= 0 {
101			// single LL rotation
102			p.left = p1.right
103			p1.right = p
104			if 0 == p1.balance {
105				p.balance = -1
106				p1.balance = 1
107				h = false
108			} else {
109				p.balance = 0
110				p1.balance = 0
111			}
112
113			nn := 1 + p1.rightNodes + p.rightNodes
114			p.leftNodes = p1.rightNodes
115			p1.rightNodes = nn
116
117			p1.up = p.up
118			p.up = p1
119			if nil != p.left {
120				p.left.up = p
121			}
122
123			*pp = p1
124		} else {
125			// double LR rotation
126			p2 := p1.right
127			p1.right = p2.left
128			p2.left = p1
129			p.left = p2.right
130			p2.right = p
131			if -1 == p2.balance {
132				p.balance = 1
133			} else {
134				p.balance = 0
135			}
136			if +1 == p2.balance {
137				p1.balance = -1
138			} else {
139				p1.balance = 0
140			}
141			p2.balance = 0
142
143			nl := 1 + p1.leftNodes + p2.leftNodes
144			nr := 1 + p2.rightNodes + p.rightNodes
145
146			p1.rightNodes = p2.leftNodes
147			p.leftNodes = p2.rightNodes
148
149			p2.leftNodes = nl
150			p2.rightNodes = nr
151
152			p2.up = p.up
153			if nil != p.left {
154				p.left.up = p
155			}
156			if nil != p1.right {
157				p1.right.up = p1
158			}
159			p.up = p2
160			p1.up = p2
161
162			*pp = p2
163		}
164	}
165	return h
166}
167
168// delete: rearrange deleted node
169func del(qq **Node, rr **Node) bool {
170	h := false
171	if nil != (*rr).right {
172		h = del(qq, &(*rr).right)
173		(*rr).rightNodes -= 1
174		if h {
175			h = balanceRight(rr)
176		}
177	} else {
178		q := *qq
179		r := *rr
180		rl := r.left
181		if nil != rl {
182			rl.up = r.up
183		}
184
185		if r != q.left {
186			r.left = q.left
187			r.leftNodes = q.leftNodes - 1
188		}
189		r.right = q.right
190		r.up = q.up
191		r.balance = q.balance
192		r.rightNodes = q.rightNodes
193
194		if nil != r.right {
195			r.right.up = r
196		}
197		if nil != r.left {
198			r.left.up = r
199		}
200
201		*qq = r
202		*rr = rl
203
204		h = true
205	}
206	return h
207}
208
209// Delete - removes a specific item from the tree
210func (tree *Tree) Delete(key Item) interface{} {
211	value, removed, _ := delete(key, &tree.root)
212	if removed {
213		tree.count -= 1
214	}
215	return value
216}
217
218// internal delete routine
219func delete(key Item, pp **Node) (interface{}, bool, bool) {
220	h := false
221	if nil == *pp { // key not in tree
222		return nil, false, h
223	}
224	value := interface{}(nil)
225	removed := false
226	switch (*pp).key.Compare(key) {
227	case +1: // (*pp).key > key
228		value, removed, h = delete(key, &(*pp).left)
229		if removed {
230			(*pp).leftNodes -= 1
231		}
232		if h {
233			h = balanceLeft(pp)
234		}
235	case -1: // (*pp).key < key
236		value, removed, h = delete(key, &(*pp).right)
237		if removed {
238			(*pp).rightNodes -= 1
239		}
240		if h {
241			h = balanceRight(pp)
242		}
243	default: // found: delete p
244		q := *pp
245		value = q.value // preserve the value part
246		if nil == q.right {
247			if nil != q.left {
248				q.left.up = q.up
249			}
250			*pp = q.left
251			h = true
252		} else if nil == q.left {
253			if nil != q.right {
254				q.right.up = q.up
255			}
256			*pp = q.right
257			h = true
258		} else {
259			h = del(pp, &q.left)
260			(*pp).left = q.left // p has changed, but q.left has left link value
261			if h {
262				h = balanceLeft(pp)
263			}
264		}
265		freeNode(q)    // return deleted node to pool
266		removed = true // indicate that an item was removed
267	}
268	return value, removed, h
269}
270