package edu.princeton.cs.algs4.growingtree.demos; /** * Utility functions for AVL Tree Operators * @author Josh Israel */ import edu.princeton.cs.algs4.growingtree.framework.NodeProperties; import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode; public class AVLOperator
{ /* This is the "balance factor" -- the maximum allowed height difference * between siblings. Setting it to larger values, increases the worst-case * depth of the tree, but reduces the amount of rebalancing that happens. */ private int B; public AVLOperator() { this(1); } public AVLOperator(int balFactor) { B = balFactor; } protected static
int height(IAlgorithmNode
n) { if (n == null) return NodeProperties.NULL_HEIGHT; else return n.getNodeProperties().getHeight(); } protected IAlgorithmNode
bal(IAlgorithmNode
t) { IAlgorithmNode
l = t.getLeft(); IAlgorithmNode
r = t.getRight(); int hl = height(l); int hr = height(r); if (hl > hr + B) { if (height(l.getLeft()) >= height(l.getRight())) { t.rotateRight(); return l; } else { IAlgorithmNode
lr = l.getRight(); l.rotateLeft(); t.rotateRight(); return lr; } } else if (hr > hl + B) { if (height(r.getRight()) >= height(r.getLeft())) { t.rotateLeft(); return r; } else { IAlgorithmNode
rl = r.getLeft(); r.rotateRight(); t.rotateLeft(); return rl; } } else { return t; } } }