Often a binary tree is represented in a particular implicit data structure packed into an array whereby the left and right children of t[x] are found at t[2x+1] and t[2x+2]. This is commonly done in implementations of heaps, for example.

Does this representation have a canonical name? I am somewhat fed up of referring to it as “a representation of a tree in an array like in a heap”.

  • 3
    $\begingroup$ I don't think there's an official name (hence this being a comment rather than an answer - I have no proof), but I tend to use "array-embedded [binary] tree", it's at least shorter and easier to work into a sentence. $\endgroup$ – Luke Mathieson May 1 '18 at 23:59
  • $\begingroup$ You’d think it would have one huh. Maybe we should coin one... $\endgroup$ – bacar May 2 '18 at 6:46
  • $\begingroup$ In any particular document, you can say once that you always implement trees in this way and then just say "tree". $\endgroup$ – David Richerby May 2 '18 at 12:42
  • 1
    $\begingroup$ Indeed, "array implementation of [complete] binary trees" seems to be acceptable, as witnessed by a google search. If you want to have fun, just call it an "Ahnentafel", or "Eytzinger's method", after the person who described this method for numbering in (geneological) trees around 1590. $\endgroup$ – Hendrik Jan May 2 '18 at 13:00
  • $\begingroup$ "In effect, an ahnentafel is a method for storing a binary tree in an array" - the one used in heaps. Perfect! An Ahnentafel it is then :-) $\endgroup$ – bacar May 2 '18 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.