The best way to calculate the height in a binary search tree balancing an AVL-tree

Question

I m looking for the best way to calculate a nodes balance in an AVL-tree  I thought I had it working  but after some heavy inserting updating I can see that it s not working correct  at all     This is kind of a two-part question  the first part would be how to calculate the height of a sub-tree  I know the definition  The height of a node is the length of the longest downward path to a leaf from that node   and I understand it  but I fail at implementing it  And to confuse me further this quote can be found on wikipedia on tree-heights  Conventionally  the value -1 corresponds to a subtree with no nodes  whereas zero corresponds to a subtree with one node    And the second part is getting the balance factor of a sub-tree in an AVL tree  I ve got no problem understanding the concept   get the height of your L and R sub-trees and subtract R from L   And this is defined as something like this  BALANCE   NODE L  HEIGHT  - NODE R  HEIGT   Reading on wikipedia says this on the first few lines describing insertions into an AVL tree   If the balance factor becomes -1  0  or 1 then the tree is still in AVL form  and no rotations are necessary    It then goes on  saying this  If the balance factor becomes 2 or -2 then the tree rooted at this node is unbalanced  and a tree rotation is needed  At most a single or double rotation will be needed to balance the tree   - which I have no trouble grasping    But  yes  there s always a but    Here s where it gets confusing  the text states  If the balance factor of R is 1  it means the insertion occurred on the  external  right side of that node and a left rotation is needed   But from m understanding the text said  as I quoted  that if the balance factor was within  -1  1  then there was no need for balancing    I feel I m so close to grasping the concept  I ve gotten the tree rotations down  implemented a normal binary search tree  and on the brink of grasping AVL-trees but just seem to be missing that essential epiphany   Edit  Code examples are preferred over academic formulas as I ve always had an easier time grasping something in code  but any help is greatly appreciated   Edit  I wish I could mark all answers as  accepted   but for me NIck s answer was the first that made me go  aha

User · Answer

This BFS-like solution is pretty straightforward  Simply jumps levels one-by-one   def getHeight self root  method  links        c node   root     cur lvl nodes    root      nxt lvl nodes          height     links   -1   nodes   0  method       while cur lvl nodes or nxt lvl nodes           for c node in cur lvl nodes              for n node in filter lambda x  x is not None   c node left  c node right                    nxt lvl nodes append n node           cur lvl nodes   nxt lvl nodes         nxt lvl nodes              height    1      return height

User · Answer

Give BinaryTree lt T  Comparator gt   Node a subtreeHeight data member  initialized to 0 in its constructor  and update automatically every time with     template  lt typename T  typename Comparator gt  inline void BinaryTree lt T  Comparator gt   Node  setLeft  std  shared ptr lt Node gt  amp  node        const std  size t formerLeftSubtreeSize   left   left- gt subtreeSize   0      left   node      if  node            node- gt parent   this- gt shared from this            subtreeSize            node- gt depthFromRoot   depthFromRoot   1          const std  size t h   node- gt subtreeHeight          if  right              subtreeHeight   std  max  right- gt subtreeHeight  h    1          else             subtreeHeight   h   1            else           subtreeSize -  formerLeftSubtreeSize          subtreeHeight   right   right- gt subtreeHeight   1   0           template  lt typename T  typename Comparator gt  inline void BinaryTree lt T  Comparator gt   Node  setRight  std  shared ptr lt Node gt  amp  node        const std  size t formerRightSubtreeSize   right   right- gt subtreeSize   0      right   node      if  node            node- gt parent   this- gt shared from this            subtreeSize            node- gt depthFromRoot   depthFromRoot   1          const std  size t h   node- gt subtreeHeight          if  left              subtreeHeight   std  max  left- gt subtreeHeight  h    1          else             subtreeHeight   h   1            else           subtreeSize -  formerRightSubtreeSize          subtreeHeight   left   left- gt subtreeHeight   1   0            Note that data members subtreeSize and depthFromRoot are also updated  These functions are called when inserting a node  all tested   e g   template  lt typename T  typename Comparator gt  inline std  shared ptr lt typename BinaryTree lt T  Comparator gt   Node gt  BinaryTree lt T  Comparator gt   Node  insert  BinaryTree amp  tree  const T amp  t  std  shared ptr lt Node gt  amp  node        if   node            std  shared ptr lt Node gt  newNode   std  make shared lt Node gt  tree  t           node   newNode          return newNode            if  getComparator   t  node- gt value             std  shared ptr lt Node gt  newLeft   insert tree  t  node- gt left           node- gt setLeft newLeft             else           std  shared ptr lt Node gt  newRight   insert tree  t  node- gt right           node- gt setRight newRight             return node      If removing a node  use a different version of removeLeft and removeRight by replacing subtreeSize    with subtreeSize--    Algorithms for rotateLeft and rotateRight can be adapted without much problem either   The following was tested and passed   template  lt typename T  typename Comparator gt  void BinaryTree lt T  Comparator gt   rotateLeft  std  shared ptr lt Node gt  amp  node        The root of the rotation is  node   and its right child is the pivot of the rotation   The pivot will rotate counter-clockwise and become the new parent of  node       std  shared ptr lt Node gt  pivot   node- gt right      pivot- gt subtreeSize   node- gt subtreeSize      pivot- gt depthFromRoot--      node- gt subtreeSize--      Since  pivot  will no longer be in the subtree rooted at  node       const std  size t a   pivot- gt left   pivot- gt left- gt subtreeHeight   1   0      Need to establish node- gt heightOfSubtree before pivot- gt heightOfSubtree is established  since pivot- gt heightOfSubtree depends on it      node- gt subtreeHeight   node- gt left   std  max a  node- gt left- gt subtreeHeight   1    std  max lt std  size t gt  a 1       if  pivot- gt right            node- gt subtreeSize -  pivot- gt right- gt subtreeSize      The subtree rooted at  node  loses the subtree rooted at pivot- gt right          pivot- gt subtreeHeight   std  max  pivot- gt right- gt subtreeHeight  node- gt subtreeHeight    1            else         pivot- gt subtreeHeight   node- gt subtreeHeight   1      node- gt depthFromRoot        decreaseDepthFromRoot pivot- gt right       Recursive call for the entire subtree rooted at pivot- gt right      increaseDepthFromRoot node- gt left       Recursive call for the entire subtree rooted at node- gt left      pivot- gt parent   node- gt parent      if  pivot- gt parent        pivot s new parent will be its former grandparent  which is not nullptr  so the grandparent must be updated with a new left or right child  depending on whether  node  was its left or right child           if  pivot- gt parent- gt left    node              pivot- gt parent- gt left   pivot          else             pivot- gt parent- gt right   pivot            node- gt setRightSimple pivot- gt left       Since pivot- gt left- gt value is less than pivot- gt value but greater than node- gt value   We use the NoSizeAdjustment version because the  subtreeSize  values of  node  and  pivot  are correct already      pivot- gt setLeftSimple node       if  node    root            root   pivot          root- gt parent   nullptr             where  inline void decreaseDepthFromRoot  std  shared ptr lt Node gt  amp  node   adjustDepthFromRoot node  -1    inline void increaseDepthFromRoot  std  shared ptr lt Node gt  amp  node   adjustDepthFromRoot node  1     template  lt typename T  typename Comparator gt  inline void BinaryTree lt T  Comparator gt   adjustDepthFromRoot  std  shared ptr lt Node gt  amp  node  int adjustment        if   node          return      node- gt depthFromRoot    adjustment      adjustDepthFromRoot  node- gt left  adjustment       adjustDepthFromRoot  node- gt right  adjustment       Here is the entire code   http   ideone com d6arrv

User · Answer

Height is easily implemented by recursion  take the maximum of the height of the subtrees plus one  The  balance factor of R  refers to the right subtree of the tree which is out of balance  I suppose

User · Answer

Well  you can compute the height of a tree with the following recursive function   int height struct tree  t        if  t    NULL          return 0      else         return max height t- gt left   height t- gt right     1      with an appropriate definition of max   and struct tree   You should take the time to figure out why this corresponds to the definition based on path-length that you quote   This function uses zero as the height of the empty tree   However  for something like an AVL tree  I don t think you actually compute the height each time you need it   Instead  each tree node is augmented with a extra field that remembers the height of the subtree rooted at that node   This field has to be kept up-to-date as the tree is modified by insertions and deletions   I suspect that  if you compute the height each time instead of caching it within the tree like suggested above  that the AVL tree shape will be correct  but it won t have the expected logarithmic performance

User · Answer

Here s where it gets confusing  the text states  If the balance factor of R is 1  it    means the insertion occurred on the  external  right side of that node and a left    rotation is needed   But from m understanding the text said  as I quoted  that if the    balance factor was within  -1  1  then there was no need for balancing     Okay  epiphany time   Consider what a rotation does   Let s think about a left rotation    P   parent  O   ourself  the element we re rotating   RC   right child  LC   left child  of the right child  not of ourself    P              10                        O               15                             RC               20                           LC               18               P              10                           RC              20                        O              15                         LC              18   basically  what happens is    1  our right child moves into our position  2  we become the left child of our right child  3  our right child s left child becomes our right   Now  the big thing you have to notice here - this left rotation HAS NOT CHANGED THE DEPTH OF THE TREE   We re no more balanced for having done it   But - and here s the magic in AVL - if we rotated the right child to the right FIRST  what we d have is this      P        O            LC                RC   And NOW if we rotate O left  what we get is this      P           LC             O   RC   Magic   we ve managed to get rid of a level of the tree - we ve made the tree balanced   Balancing the tree means getting rid of excess depth  and packing the upper levels more completely - which is exactly what we ve just done   That whole stuff about single double rotations is simply that you have to have your subtree looking like this    P        O            LC                RC   before you rotate - and you may have to do a right rotate to get into that state   But if you re already in that state  you only need to do the left rotate

User · Answer

Part 1 - height   As starblue says  height is just recursive  In pseudo-code   height node    max height node L   height node R     1   Now height could be defined in two ways  It could be the number of nodes in the path from the root to that node  or it could be the number of links  According to the page you referenced  the most common definition is for the number of links  In which case the complete pseudo code would be   height node       if node    null          return -1    else          return max height node L   height node R     1   If you wanted the number of nodes the code would be   height node       if node    null          return 0    else          return max height node L   height node R     1   Either way  the rebalancing algorithm I think should work the same   However  your tree will be much more efficient  O ln n    if you store and update height information in the tree  rather than calculating it each time   O n     Part 2 - balancing   When it says  If the balance factor of R is 1   it is talking about the balance factor of the right branch  when the balance factor at the top is 2  It is telling you how to choose whether to do a single rotation or a double rotation  In  python like  Pseudo-code   if balance factor top    2     right is imbalanced      if balance factor R    1                do a left rotation      else if balance factor R    -1            do a double rotation else     must be -2  left is imbalanced      if balance factor L    1                do a left rotation      else if balance factor L    -1            do a double rotation   I hope this makes sense

User · Answer

You do not need to calculate tree depths on the fly   You can maintain them as you perform operations   Furthermore  you don t actually in fact have to maintain track of depths  you can simply keep track of the difference between the left and right tree depths   http   www eternallyconfuzzled com tuts datastructures jsw tut avl aspx  Just keeping track of the balance factor  difference between left and right subtrees  is I found easier from a programming POV  except that sorting out the balance factor after a rotation is a PITA

User · Answer

Here s where it gets confusing  the text states  If the balance factor of R is 1  it means the insertion occurred on the  external  right side of that node and a left rotation is needed   But from m understanding the text said  as I quoted  that if the balance factor was within  -1  1  then there was no need for balancing    R is the right-hand child of the current node N   If balance N     2  then you need a rotation of some sort  But which rotation to use  Well  it depends on balance R   if balance R     1 then you need a left-rotation on N  but if balance R    -1 then you will need a double-rotation of some sort

User · Answer

Here s an alternate way of finding height  Add an additional attribute to your node called height   class Node   data value    data is a custom data type node right  node left  int height      Now  we ll do a simple breadth-first traversal of the tree  and keep updating the height value for each node   int height  Node root    Queue lt Node gt  q   Queue lt Node gt     Node lastnode    reset height root height   0   q Enqueue root   while q Count  gt  0       lastnode   q Dequeue       if  lastnode left    null         lastnode left height   lastnode height   1         q Enqueue lastnode left            if  lastnode right    null         lastnode right height   lastnode height   1        q Enqueue lastnode right          return lastnode height    this will return a 0-based height  so just a root has a height of 0     Cheers

[algorithm] The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

Examples related to algorithm

Examples related to data-structures

Examples related to binary-tree

Examples related to avl-tree

Examples related to tree-balancing