Skip to content

Instantly share code, notes, and snippets.

@mahmoud
Created March 15, 2013 08:09
Show Gist options
  • Save mahmoud/5168235 to your computer and use it in GitHub Desktop.
Save mahmoud/5168235 to your computer and use it in GitHub Desktop.
AVL rebalancing
def get_bal(left, right): return left - right
node = stack[i]
cbal = get_bal(node[1], node[2])
if abs(cbal) < 2: break
rel_side = cbal / (cbal % 2) #-1 or 1, left /right
side = ((1 + rel_side) / 2) + 1 # 1 or 2, left / right
child = node[side]
gcbal = get_bal(child[1], child[2])
if (rel_side * gcbal) > 0:
# right rotate right or left rotate left, see below
grandchild = child[other_side]
grandchild[side] = child
child[other_side] = child[other_side][side]
node[side] = child[other_side]
child = node[side]
if i == 0:
self.root = child
else:
parent = stack[i - 1]
if parent[1] is node:
parent[1] = child
elif parent[2] is node:
parent[2] = child
node[side] = child[other_side]
child[other_side] = node
node = parent if i > 0 else self.root
# update gc heights, c heights, self height # 7 total? maybe just 4.
node[side][other_side][side] = node[side] # RLR = R -OR- LRL = L
node[side][other_side] = node[side][other_side][side] # RL = RLR -OR- LR = LRL
node[side] = node[side][other_side] # R = RL -OR- L = LR
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment