Definition of a Balanced Tree

by

The constraint is generally applied recursively to every subtree. That is, the tree is only balanced if:

  1. The left and right subtrees’ heights differ by at most one, AND
  2. The left subtree is balanced, AND
  3. The right subtree is balanced

According to this, the next tree is balanced:

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G

The next one is not balanced because the subtrees of C differ by 2 in their height:

     A
   /   \
  B     C   <-- difference = 2
 /     /
D     E  
     /  
    G

That said, the specific constraint of the first point depends on the type of tree. The one listed above is the typical for AVL trees.

Red-black trees, for instance, impose a softer constraint.

More Related Contents:

  1. With ‘ N ‘ no of nodes, how many different Binary and Binary Search Trees possible?
  2. Tail recursive function to find depth of a tree in Ocaml
  3. What are the options for storing hierarchical data in a relational database?
  4. Build tree array from flat array in javascript
  5. Parsing an arithmetic expression and building a tree from it in Java
  6. Build a tree from a flat array in PHP
  7. How can I implement a tree in Python?
  8. How to search JSON tree with jQuery
  9. Using self.xxxx as a default parameter – Python
  10. What is the difference between tree depth and height?
  11. Turn database result into array
  12. How to convert to D3’s JSON format?
  13. PHP / MySQL build tree menu
  14. Get all child, grandchild etc nodes under parent using php with mysql query results
  15. Why can’t I return a concrete subtype of A if a generic subtype of A is declared as return parameter?
  16. Can the pointer in a struct pointer method be reassigned to another instance?
  17. Tree implementation in Java (root, parents and children)
  18. Angularjs: ng-options group by
  19. Hashing a Tree Structure
  20. reconstructing a tree from its preorder and postorder lists
  21. PHP – How to build tree structure list?
  22. Construct a tree structure from list of string paths
  23. Why DFS and not BFS for finding cycle in graphs
  24. How to render a tree in Twig
  25. How to create a collapsing tree table in html/css/js?
  26. The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?
  27. Saving nltk drawn parse tree to image file
  28. Print the biggest K elements in a given heap in O(K*log(K))?
  29. Does C have any tools for doing string addition?
  30. D3 Tree Layout Separation Between Nodes using NodeSize

Leave a Comment