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