Trees

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root. Thus, tree is a (possibly non-linear) data structure made up of nodes or vertices and edges without having any cycle. The tree with no nodes is called the null or empty tree. A tree that is not empty consists of a root node and potentially many levels of additional nodes that form a hierarchy. The following diagrams illustrate the meaning of a tree:

800px-Directed_Graph_Edge.svg 105px-Graph_single_node.svg 450px-Directed_graph,_cyclic.svg Directed_graph_with_branching 248px-Directed_graph,_disjoint.svg
Each linear list is trivially a tree Not a tree: cycle A→A Not a tree: cycle B→C→E→D→B Not a tree: undirected cycle 1-2-4-3 Not a tree: 2 non-connected parts A→B and C→D→E

Tree terminologies:

clip_image004_thumb2

  • We will call every circle a node and each line an edge. Nodes “19”, “21”, “14” are below node “7” and are directly connected to it. This nodes we are called direct descendants (child nodes) of node “7”, and node “7” their parent. The same way “1”, “12” and “31” are children of “19” and “19” is their parent. Intuitively we can say that “21” is sibling of “19”, because they are both children of “7” (the reverse is also true – “19” is sibling of “21”).For “1”, “12”, “31”, “23” and “6” node “7” precedes them in the hierarchy, so he is their indirect parent – ancestor, ant they are called his descendants.
  • Root is called the node without parent. In our example this is node “7”.
  • Leaf is a node without child nodes. In our example – “1”, “12”, “31”, “21”, “23” and “6”.
  • Internal nodes are the nodes, which are not leaf or root (all nodes, which have parent and at least one child). Such nodes are “19” and “14.
  • External nodes are the nodes, which have no child nodes i.e. leaf nodes.
  • Depth of a node we will call the length of the path from the root to certain node. In our example “7” as root has depth zero, “19” has depth one and “23” – depth two.
  • Height of a tree is equal to the maximum level of any node in the tree. The height of the tree in our example is “2”.
  • Level of a node n is the number of edges on the path from the root node to n. In our example, the level of node “31” is two. By definition, the level of the root node is zero.
  • Degree of node we call the number of direct children of the given node. The degree of “19” and “7” is three, but the degree of “14” is two. The leaves have degree zero.
  • Branching factor is the maximum of the degrees of all nodes in the tree. In our example the maximum degree of the nodes is 3, so the branching factor is 3.

Types of Trees

  • Binary trees: binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child
  • K-ary Trees: A k-ary tree is a rooted tree in which each node has no more than k children. It is also sometimes known as a k-way tree, an N-ary tree, or an M-ary tree. A binary tree is the special case where k=2.
  • Red Black trees: A redblack tree is a binary search tree in which each node is colored red or black such that the root is black. The children of ared node are black. Every path from the root to a 0-node or a 1-node has the same number of black nodes.
  • AVL Tree: It is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property

Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

      • Trees reflect structural relationships in the data
      • Trees are used to represent hierarchies
      • Trees provide an efficient insertion and searching
      • Trees are very flexible data, allowing to move subtrees around with minimum effort