Tree Data Structure Tree Data Structure Details

2 Objectives Overview  Trees  Concept  Examples and Applications  Definition  Terminology  Types of Trees  General Trees  Representation and Traversal  Binary Tree  Types and Representations

3 Tree - Introduction  Trees are very flexible, versatile and powerful non-linear data structure  It can be used to represent data items possessing hierarchical relationship  A tree can be theoretically defined as a finite set of one or more data items (or nodes) such that  There is a special node called the root of the tree  Remaining nodes (or data item) are partitioned into number of subsets each of which is itself a tree, are called subtree  A tree is a set of related interconnected nodes in a hierarchical structure

4 Tree - Introduction  Some data is not linear (it has more structure!)  Family trees  Organizational charts  Linked lists etc don’t store this structure information.  Linear implementations are sometimes inefficient or otherwise sub-optimal for our purposes  Trees offer an alternative  Representation  Implementation strategy  Set of algorithms

5 Tree Examples  Where have you seen a tree structure before?  Examples of trees:  Directory tree  Family tree  Company organization chart  Table of contents etc.

6 Tree Example – Tic Tac Toe X X X X O X X O X O X O X O X

8 Tree Example – Taxonomy Tree

9 Tree Example – Decision Tree  tool that uses a tree-like graph or model of decisions and their possible consequences  including chance event outcomes, resource costs, and utility  It is one way to display an algorithm.

10 What is a Tree Useful for?  Artificial Intelligence – planning, navigating, games  Representing things:  Simple file systems  Class inheritance and composition  Classification, e.g. taxonomy (the is-a relationship again!)  HTML pages  Parse trees for language  3D graphics

11 Tree - Definition  A tree is a finite set of one or more nodes such that:  There is a specially designated node called the root.  The remaining nodes are partitioned into n>=0 disjoint sets T1, ..., Tn, where each of these sets is a tree.  We call T1, ..., Tn the subtrees of the root r  Each of whose roots are connected by a directed edge from r  A tree is a collection of N nodes, one of which is the root and N-1 edges

12 Tree – Basic Terminology  Each data item within a tree is called a 'node’  The highest data item in the tree is called the 'root' or root node  First node in hierarchical arrangement of data  Below the root lie a number of other 'nodes'. The root is the 'parent' of the nodes immediately linked to it and these are the 'children' of the parent node  Leaf node has no children

13 Tree – Basic Terminology  If nodes share a common parent, then they are 'sibling' nodes, just like a family.  The link joining one node to another is called the 'branch'.  This tree structure is a general tree  Leaves: nodes with no children (also known as external nodes)  Internal Nodes: nodes with children The ancestors of a node are all the nodes along the path from the root to the node

14 Tree – Basic Terminology  ‘A’ is root node  Each data item in a tree is known as node  It specifies the data information and links to other data items  Degree of a node is the number of sub-trees of a node in a given tree  In the example  Degree of node A is 3  Degree of node B is 2  Degree of node C is 2  Degree of node D is 3  Degree of node J is 4

15 Tree – Basic Terminology  Degree of a tree is the maximum degree of node in a given tree  Degree of node J is 4  All other nodes have less or equal degree  So degree of the tree is 4  A node with degree zero (0) is called terminal node or a leaf  Nodes M,N,I,O etc are leaf nodes  Any node whose degree is not zero is called a non-terminal node

16 Tree – Basic Terminology  Levels of a Tree  The tree is structured in different levels  The entire tree is leveled in such a way that the root node is always of level 0  Its immediate children are at level 1 and their immediate children are at level 2 and so on up to the terminal nodes  If a node is at level n then its children will be at level n+1

17 Tree – Basic Terminology  Depth of a Tree is the maximum level of any node in a given tree  The number of levels from root to the leaves is called depth of a tree. Depth of tree is 4  The term height is also used to denote the depth of a tree  Height (of node): length of the longest path from a node to a leaf.  All leaves have a height of 0  The height of root is equal to the depth of the tree

18 Tree – Basic Terminology  A vertex (or node) is a simple object that can have a name and can carry other associated information  An edge is a connection between two vertices  A path in a tree is a list of distinct vertices in which successive vertices are connected by edges in the tree  The defining property of a tree is that there is precisely one path connecting any two nodes

19 Tree – Basic Terminology  Example: {a, b, d, i } is path Path

20 Path in a Tree  A path from node n1 to nk is defined as a sequence of nodes n1, n2, …, nk such that ni is the parent of ni+1 for 1<= i <= k.  The length of this path is the number of edges on the path namely k-1.  The length of the path from a node to itself is 0.  There is exactly one path from from the root to each node.

21 What is a Tree?  Models the parent/child relationship between different elements  Each child only has one parent  From mathematics:  “a directed acyclic graph”  At most one path from any one node to any other node  Different kinds of trees exist.  Trees can be used for different purposes.  In what order to we visit elements in a tree?

22 How Many Types of Trees are there?  Far too many:  General tree  Binary Tree  Red-Black Tree  AVL Tree  Partially Ordered Tree  B+ Trees  … and so on  Different types are used for different things  To improve speed  To improve the use of available memory  To suit particular problems

24 Representation of Trees  List Representation  ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )  The root comes first, followed by a list of sub-trees data link 1 link 2 ... link n How many link fields are needed in such a representation?

25 A Tree Node  Every tree node:  object – useful information  children – pointers to its children nodes O O O O O

26 Left Child – Right Sibling A B C D E F G H I J K L M data left child right sibling

27 Tree ADT  Objects: any type of objects can be stored in a tree  Methods:  accessor methods  root() – return the root of the tree  parent(p) – return the parent of a node  children(p) – returns the children of a node  query methods  size() – returns the number of nodes in the tree  isEmpty() - returns true if the tree is empty  elements() – returns all elements  isRoot(p), isInternal(p), isExternal(p)

28 Tree Implementation typedef struct tnode { int key; struct tnode* lchild; struct tnode* sibling; } *ptnode;  Create a tree with three nodes (one root & two children)  Insert a new node (in tree with root R, as a new child at level L)  Delete a node (in tree with root R, the first child at level L)

29 Tree Traversal  Two main methods:  Preorder  Postorder  Recursive definition  PREorder:  visit the root  traverse in preorder the children (subtrees)  POSTorder  traverse in postorder the children (subtrees)  visit the root

30 Tree - Preorder Traversal  preorder traversal Algorithm preOrder(v) “visit” node v for each child w of v do recursively perform preOrder(w)

31 Prerder Implementation public void preorder(ptnode t) { ptnode ptr; display(t->key); for(ptr = t->lchild; NULL != ptr; ptr = ptr->sibling) { preorder(ptr); } }

32 Tree - Postorder Traversal  postorder traversal Algorithm postOrder(v) for each child w of v do recursively perform postOrder(w) “visit” node v  du (disk usage) command in Unix

33 Postorder Implementation public void postorder(ptnode t) { ptnode ptr; for(ptr = t->lchild; NULL != ptr; ptr = ptr->sibling) { postorder(ptr); } display(t->key); }

34 Binary Tree  A special class of trees:  max degree for each node is 2  Recursive definition:  A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.  Any tree can be transformed into binary tree.  by left child-right sibling representation

35 Binary Tree - Example J I M H L A B C D E F G K

36 Binary Tree  Tree size is limited by the depth of the tree  For binary tree, nodes at level k = n  For N-ary tree, nodes at level k = n k - 1  Size for Binary is: 1 + 2 + … + n = 2n – 1 and  Size for N-ary is (nk-1)/(n-1) where k is number of full levels.

37 Binary Tree  A binary tree is a tree in which no node can have more than 2 children  These children are described as “left child” and “right child” of the parent node  A binary tree T is defined as a finite set of elements called nodes such that  T is empty if T has no nodes called the null or empty tree  T contains a special node R, called root node of T  remaining nodes of T form an ordered pair of disjoined binary trees T1 and T2. They are called left and right sub tree of R

38 Binary Tree  ‘A’ is the root node of the tree  ‘B’ is left child of ‘A’ and ‘C’ is right child of ‘A’  ‘A’ is the father of ‘B’ and ‘C’  The nodes ‘B’ and ‘C’ are called brothers

39 Sample of Binary Trees A B A B A B C G E I D H F Complete Binary Tree Skewed Binary Tree E C D 1 2 3 4 5

40 Maximum Nodes in Binary Tress  The maximum number of nodes on level i of a binary tree is 2i-1, I >= 1.  The maximum number of nodes in a binary tree of depth k is 2k-1, k >= 1.  Prove by Induction 2 2 1 1 1 i i k k     

41 Relation between Number of Leaf Nodes and Nodes of Degree 2 For any nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes of degree 2, then n0=n2+1 proof: Let n and B denote the total number of nodes & branches in T. Let n0, n1, n2 represent the nodes with no children, single child, and two children respectively. n= n0+n1+n2, B+1=n, B=n1+2n2 ==> n1+2n2+1= n, n1+2n2+1= n0+n1+n2 ==> n0=n2+1

42 Full Binary Tree and Complete BT A full binary tree of depth k is a binary tree of depth k having 2k -1 nodes, k >=0. A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k A B C G E I D H F A B C G E K D J F I H O N M L Complete binary tree Full binary tree of depth 4

43 Binary Tree Representation If a complete binary tree with n nodes (depth = log n + 1) is represented sequentially, then for any node with index i, 1<=i<=n, we have: parent(i) is at i/2 if i!=1. If i=1, i is at the root and has no parent. leftChild(i) is at 2i if 2i<=n. If 2i>n, then i has no left child. rightChild(i) is at 2i+1 if 2i +1 <=n. If 2i +1 >n, then i has no right child.

44 Sequential Representation A B -- C -- -- -- D -- . E [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B E C D [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C D E F G H I A B C G E I D H F (1) waste space (2) insertion/deletion problem

45 Linked Representation typedef struct tnode *ptnode; typedef struct tnode { int data; ptnode left, right; }; data left right data left right

46 Summary  Trees  Concept  Examples and Applications  Definition  Terminology  Types of Trees  General Trees  Representation and Traversal  Binary Tree  Types and Representations

Tree Data Structure Tree Data Structure Details

More Related Content

What's hot

Similar to Tree Data Structure Tree Data Structure Details

Recently uploaded

In this document

Tree Data Structure Tree Data Structure Details