Is there an established vocabulary for discussing subsets of nodes selected from a tree?

StackOverflow https://stackoverflow.com/questions/5397491

  •  28-10-2019
  •  | 
  •  

Question

When writing algorithms to deal with subsets of nodes from a tree, it's necessary to identify characteristics of those nodes. For example, a particular subset may be a forest, and the algorithm could gain huge performance benefits by identifying the roots of each subtree in the forest.

I'd like to know if there is an established vocabulary for discussing nodes within the subsets. It would be very nice to say "Find the 'Subset Roots'" instead of "Find the nodes which have no ancestors in the same subset."

               (1)
            /       \
        (*2*)        (3)
       /  |  \        |  \
    (4) (*5*) (*6*)  (7)  (*8*)
          |                 |
         (9)               (10)
          |
        (*11*)

For the subset (2, 5, 6, 8, 11), these are the useful groupings I can identify, with names or explanations underneath. I've dealt with algorithms for which it would be useful to have names for each of the following:

  • (2, 5, 6, 8, 11)
    • nodes which are in the subset
    • "Subset" or "Selections" sounds reasonable here.
  • (2, 8)
    • nodes which have no ancestors in the same subset
    • "Subset Root Nodes"?
  • (2 (5 (11), 6)), (8)
    • trees in the subset
    • "Subset Forest"?
  • (6, 8, 11)
    • nodes which have no descendants in the subset
    • "Subset Leaf Nodes"?
  • (2, 5)
    • nodes which are internal in the subset
    • "Subset Internal Nodes"?

The "Subset ..." terms are straw-man proposals intended to provoke discussion in the event that there are not well-established terms for these things.

Was it helpful?

Solution

Wikipedia's article on tree data structures includes many vocabulary terms dealing with trees. I'm not sure if it can be considered definitive.

The article on tree structure also includes additional nomenclature.

There's also an article on tree set theory.

OTHER TIPS

I don't believe there is an "According to Hoyle" hierarchy vocabulary but this information for the Xpath specs from WC3 is a great start. I commonly refer to root or primary as the top level then secondary and tertiary. After that I refer to them by branch and depth (e.g. level 4 in the hierarchy, also in the X branch).

The tree contains nodes. There are seven types of node:

root nodes

element nodes

text nodes

attribute nodes

namespace nodes

processing instruction nodes

comment nodes

http://www.w3.org/TR/xpath/#data-model

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top