rebalance rebalances a node after insertion.
(node *treeNode)
| 309 | |
| 310 | // rebalance rebalances a node after insertion. |
| 311 | func (t *IntervalTree) rebalance(node *treeNode) *treeNode { |
| 312 | updateHeight(node) |
| 313 | updateMaxEnd(node) |
| 314 | |
| 315 | balance := balanceFactor(node) |
| 316 | |
| 317 | // Left-heavy |
| 318 | if balance > 1 { |
| 319 | if balanceFactor(node.left) < 0 { |
| 320 | // Left-Right case |
| 321 | node.left = t.rotateLeft(node.left) |
| 322 | } |
| 323 | // Left-Left case |
| 324 | return t.rotateRight(node) |
| 325 | } |
| 326 | |
| 327 | // Right-heavy |
| 328 | if balance < -1 { |
| 329 | if balanceFactor(node.right) > 0 { |
| 330 | // Right-Left case |
| 331 | node.right = t.rotateRight(node.right) |
| 332 | } |
| 333 | // Right-Right case |
| 334 | return t.rotateLeft(node) |
| 335 | } |
| 336 | |
| 337 | return node |
| 338 | } |
| 339 | |
| 340 | // max returns the maximum of two int64 values. |
| 341 | func maxInt(a, b int64) int64 { |
no test coverage detected