Trees

Introduction

• Trees are structures that represent hierarchical data.
• They are formed of nodes connected together in parent-child relationships.
• There is a special node, called the root, which has no parent.
• Each child node may have its own children.

Example

Terminology

• Root:
  • The foor tis first node in the tree. In the above diagram 'Colors' is the root node.
• Internal / Branch node:
  • Any node which has children is called an internal or 'branch' node.
• Leaf:
  • Any node which doesn't have children.
  • The plural of leaf is 'leafs'.
• Child & Parent:
  • Any node that has child nodes becomes the parent to those nodes.
  • Leaf nodes are never parents.
  • In the above diagram, 'Blue' is a parent while 'Dark Blue' and 'Light Blue' are its children.
• Siblings:
  • If two children have the same parent then they are siblings.
• Descendant & Ancestor:
  • The descendant / ancestor relationship is similar to that of child and parent, except that the descendant doesn't need to be an immediate child of the ancestor.
  • 'Dark Blue' is a descendant of 'Colors'.
• Breadth:
  • The number of leaf nodes.
• Height:
  • The height of a tree is the length of the longest path between the root node and a leaf node.
  • In the example above, this would be 2.
• Size:
  • The total number of nodes in the tree.
• Degree:
  • The degree of a node is the number of children it has.
  • Leaf nodes have a degree of 0.
  • The degree of a tree is the largest degree of any of its nodes.
    • In the above image, the degree of the tree is 3.
• Level:
  • The distance from a node to the root.
    • The root is at level 0.
    • It's children are at level 1.
    • Their children are at level 2.
    • and so on.
  • The level can also be defined as a set of all nodes at the same level.
• Forest:
  • An ordered set of trees.

Rooted vs unrooted trees

• When we refer to a tree, we are referring to a rooted tree.
• However unrooted, (aka free) trees also exist.
  • the only constraint on an unrooted tree is that there exists a single unique path between any two nodes.

Ordered vs unordered trees

• Ordered trees:
  • The children of an ordered tree have a specific order.
  • In the above image:
    • The trees are not considered equal.
    • This is because the children of the 'a' node are in different orders.
  • If a tree is ordered then we can refer to a specific child by its index, e.g. the first child of 'a'.
  • Ordered trees are the default. When someone refers to a 'tree' assume they are referring to an ordered tree.
• Unordered (aka oriented) trees:
  • The children of an unordered tree do not have a specific order.
  • In the above image:
    • The trees are considered equal.
    • The order of the children is not important when determining equality.
  • It is not possible to refer to a child by index.

K-ary trees

• A k-ary tree (aka m-ary tree) is a tree in which each node has at most 'k' children.
• A binary tree is a k-ary tree with k = 2. Each node has at most two children:
• A ternary tree is a k-ary tree with k=3.
• K-ary trees differ are not proper trees:
  • K-ary trees can be completely empty, while trees must have at least one node.
  • K-ary trees can have empty nodes:
    • In the image above, the 'b' node has no left child. I.e. its first child is empty.

Code (Python)

# -*- coding: utf-8 -*-
class Node:
    def __init__(self, data):
        self.children = []
        self.data = data

    def addNode(self, node):
        node = node if isinstance(node, Node) else Node(node)
        self.children.append(node)
        node.parent = self
        return self # returns self so addNode() can be chained    

    def __str__(self, path = '', last = True):
        ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + self.data + '\n'
        for child in self.children:
            ret += child.__str__(path + ('   ' if last else '│  '), child == self.children[-1])
        return ret

Usage:

tree = \
    Node("Colors") \
        .addNode(Node("Blue")
            .addNode('Light Blue')
            .addNode("Dark Blue")) \
        .addNode(Node("Red")
            .addNode("Light Red")
            .addNode("Dark Red")) \
        .addNode(Node("Green")
            .addNode("Light Green")
            .addNode("Dark Green"))

print(tree)

Output:

Colors
  ├─ Blue
  │  ├─ Light Blue
  │  └─ Dark Blue
  ├─ Red
  │  ├─ Light Red
  │  └─ Dark Red
  └─ Green
     ├─ Light Green
     └─ Dark Green

Time Complexity

• Trees are often more efficient than simpler data structures such as arrays and lists.
• if an operation takes linear time on a list (such as searching) then it will usually take logarithmic time on a tree.
  • Assuming the tree is well organized.