legend: w = node inspections;  slow = recompute heights;  fast = one pass with a sentinel
the AVL example            n=7    slow:yes w=18     fast:yes w=7    annotate w=18    
the non-AVL example        n=9    slow:no  w=9      fast:no  w=7    annotate w=27    
                           first fault: node 9: left height 2, right height 0, bf = -2
empty tree                 n=0    slow:yes w=0      fast:yes w=0    annotate w=0     
single node                n=1    slow:yes w=1      fast:yes w=1    annotate w=1     
perfect tree, n = 7        n=7    slow:yes w=17     fast:yes w=7    annotate w=17    
perfect tree, n = 15       n=15   slow:yes w=49     fast:yes w=15   annotate w=49    
perfect tree, n = 31       n=31   slow:yes w=129    fast:yes w=31   annotate w=129   
perfect tree, n = 63       n=63   slow:yes w=321    fast:yes w=63   annotate w=321   
perfect tree, n = 127      n=127  slow:yes w=769    fast:yes w=127  annotate w=769   
chain, n = 8               n=8    slow:no  w=8      fast:no  w=8    annotate w=36    
                           first fault: node 6: left height -1, right height 1, bf = 2
chain, n = 16              n=16   slow:no  w=16     fast:no  w=16   annotate w=136   
                           first fault: node 14: left height -1, right height 1, bf = 2
chain, n = 32              n=32   slow:no  w=32     fast:no  w=32   annotate w=528   
                           first fault: node 30: left height -1, right height 1, bf = 2
chain, n = 64              n=64   slow:no  w=64     fast:no  w=64   annotate w=2080  
                           first fault: node 62: left height -1, right height 1, bf = 2
chain, n = 128             n=128  slow:no  w=128    fast:no  w=128  annotate w=8256  
                           first fault: node 126: left height -1, right height 1, bf = 2
