• Non-Linear data structure
  • Hierarchical structure to increase search speed
Tree structure Definitions
  • Forest: A set of trees which are not connected to each other
  • Tree: Nodes connected to each other in a hierarchical structure
  • Sub-tree: A section of the tree below a certain node
  • Nodes: Elements of the tree
  • Edge: Lines connecting nodes - total edges in the tree equal the number of nodes minus 1 (removes the parent because it does not have a parent)
  • Root node: The starting node and the only node without a parent
  • Leaf node: Any node which does not have any children
collapse
Node relation Definitions
  • Parent Node: The node directly above the current node
  • Grand Parent Node: the node directly above the parent node
  • Ancestor node: Any predecessor of the current node
  • Child node: A node directly below the current node
  • Grand Child node: A node directly below a child node
  • Siblings: Two or more node which have the same parent
  • Descendent Node: Any node connect in the tree below the current node
collapse
Tree Definitions
  • Level: The amount of hops from the root node ie number of edges eg root = level 0, child of root = level 1, grand child of root = level 2
  • Height: Number of levels eg level 0,1,2 means there is a height of 3
  • Path: A sequence of nodes where each node is a child of the previous. Any node can only have one path to it. eg root, child 1, grand-child 1
  • Path length: The number of edges in a path
  • Degree: The number of direct children eg the degree of the root node is 4 if it has 4 children (regardless of decendent nodes)
collapse
Types of Trees

A tree where each node has a maximum of two child nodes.

collapse
Strictly Binary Tree

A Tree where each node has either 0 children or 2 children.

With n leaf nodes the tree has:

  • n-1 binary nodes
  • 2n-1 total nodes

Example: 4 leaf nodes means there are (4-1) 3 binary nodes and (2n-1) 7 nodes in total.

collapse
Extended Binary Tree

A Tree where each node has given special nodes if they do not have exactly two children.

  • Internal nodes: The real nodes
  • External nodes: The added special nodes
  • Internal path length: Sum of the path lengths of all internal nodes.
  • External path length: Sum of the path lengths of all external nodes.

external path length = internal path length + 2 x totalNodes

E = I + 2n

collapse
Full Binary Tree

A tree where each level has its maximum number of nodes.

collapse
Complete Binary Tree

A tree where each level has its maximum number of nodes except possibly the last level.

collapse
Binary Search Tree

A tree where each left subtree contains smaller values and each right subtree contains larger values.

collapse

Check out these links for more info:

My Tree Code