Data Structures and Algorithms Lec(5) Binary Tree T.Souad Alonazi What is a Tree? • A tree, is a finite set of nodes together with a finite set of directed edges that define parent-child relationships. Each directed edge connects a parent to its child. Example: A Nodes={A,B,C,D,E,f,G,H} Edges={(A,B),(A,E),(B,F),(B,G),(B,H), (E,C),(E,D)} E D B C F H G 2 What is a Tree? (contd.) • A tree satisfies the following properties: 1. 2. 3. 4. It has one designated node, called the root, that has no parent. Every node, except the root, has exactly one parent. A node may have zero or more children. There is a unique directed path from the root to each node. 5 5 3 3 2 4 tree 1 6 5 2 4 1 Not a tree 3 6 2 4 Not a tree 1 6 3 Tree Terminology (Contd.) • Degree: The number of subtrees of a node – Each of node D and B has degree 1. – Each of node A and E has degree 2. – Node C has degree 3. – Each of node F,G,H,I,J has degree 0. An Ordered Tree with size of 10 Siblings of A A B D H C E I F G J Siblings of E • • • • Leaf: A node with degree 0. Internal or interior node: a node with degree greater than 0. Siblings: Nodes that have the same parent. Size: The number of nodes in a tree. 4 Tree Terminology (Contd.) • Level (or depth) of a node v: The length of the path from the root to v. • Height of a node v: The length of the longest path from v to a leaf node. – The height of a tree is the height of its root mode. – By definition the height of an empty tree is -1. • The height of the tree is 4. Level 0 A • The height of node C is 3. B D H E F I Level 1 C G Level 2 Level 3 J k Level 4 5 Why Trees? • Trees are very important data structures in computing. • They are suitable for: – Hierarchical structure representation, e.g., • File directory. • Organizational structure of an institution. • Class inheritance tree. – Problem representation, e.g., • Expression tree. • Decision tree. – Efficient algorithmic solutions, e.g., • Search trees. 6 N-ary Trees • An N-ary tree is an ordered tree that is either: 1. Empty, or 2. It consists of a root node and at most N non-empty N-ary subtrees. It follows that the degree of each node in an N-ary tree is at most N. Example of N-ary trees: • • B 5 2 9 7 5 2-ary (binary) tree D C G D B J E F 3-ary (tertiary)tree A 7 Binary Trees • • A binary tree is an N-ary tree for which N = 2. Thus, a binary tree is either: 1. An empty tree, or 2. A tree consisting of a root node and at most two non-empty binary subtrees. Example: 5 2 9 7 5 8 Binary Trees (Contd.) • Example showing the growth of a complete binary tree: 9 Binary Trees Implementation left key right Example: A binary tree representing a + (b - c) * d + a * - b d c 10 Application of Binary Trees • Binary trees have many important uses. Two examples are: 1. Binary decision trees. • Internal nodes are conditions. Leaf nodes denote decisions. false Condition1 True decision1 Condition2 false True decision2 Condition3 false decision3 • True decision4 + Expression Trees a * - b d c 11 Binary Tree ADT It is an ordered tree with the following properties 1. Each node can have at most two subtrees 2. Each subtree is identified as being either left subtree or the right subtree of its parent 3. It may be empty Note: Property 1 says that each node can have maximum two children The order between the children of a node is specified by labeling its children as left child and right child Why binary Trees? Binary trees naturally arise in many different applications 1. Expression Tree - A central data structure in compiler design - Interior nodes contain operators and the leaf nodes have operands - An expression is evaluated by applying the operator at root to the values obtained by recursively evaluating the left and right subtrees - The following tree corresponds the expression: (a+((b-c)*d) + * a b d c Why binary Trees? 2. Huffman Coding Tree - Its is used in a simple but effective data compression algorithm - In this tree, each symbol is stored at a leaf node - To generate the code of a symbol traverse the tree from the root to the leaf node that contains the symbol such that each left link corresponds to 0 and each right link corresponds to 1 - The following tree encodes the symbols a, b, c, d 0 1 a 1 0 0 b d 1 c The code of a is 0, and that of b is 100 Recursive definition of Binary Tree A binary tree is - empty OR - a node, called the root node, together with two binary trees, which are disjoint from each other and the root node. These are called left and right subtrees of the root Types of Binary Tree Full - Every node has exactly two children in all levels, except the last level. Nodes in last level have 0 children Complete - Full up to second last level and last level is filled from left to right Other - not full or complete Full, Complete or Other? B I J K not binary A C H L M T S D G F E O N R Q P Full, Complete or other? A B I K D H L M T S G F O N R P Full, Complete or other? A B G H I K D L T F O N M S R P Full, Complete or other? A B T L S G H I K D M F O N R P Full, Complete or other? A B T L S G H I K D M N O F R P Full, Complete or Other? A T L S G H I K D B M N O P F Q R Full, Complete or other? A G H I K D B L M O N T P S F Q R Full, Complete or Other? A G H I K D B L M N O P F Q R Binary Tree Traversal Process To process a node means to perform some simple operation like printing the contents of the node or updating the contents of the node Traversal To traverse a finite collection of objects means to process each object in the collection exactly once Examples 1. List traversal – to process each element of list exactly once 2. Tree traversal – to process each node of tree exactly once Traversal Of Binary Tree There are three methods for the traversal of a binary tree 1. Preorder Traversal Each node is processed before any node in either of its subtrees 2. Inorder Traversal Each node is processed after all nodes in its left subtree and before any node in its right subtree 3. Postorder Traversal Each node is processed after all nodes in both of its subtrees Preorder Traversals Visit the root Visit Left subtree Visit Right subtree .1 .2 .3 1 A B 2 G 12 H 8 3I K 4 11 D 5 L T 6 F 13 O 14 N 10 M 9 S7 R 15 P 16 Algorithm TraversePreorder(n) Process node n if n is an internal node then TraversePreorder( n -> leftChild) TraversePreorder( n -> rightChild) Inorder Traversals Visit Left subtree Visit the root Visit Right subtree .1 .2 .3 10 1A 6B 1 G 11 8 H 2I 1 K 1 12 D 4 L T 3 16 F 14 O N9 M 7 5 S R 13 P 15 Algorithm TraverseInorder(n) if n is an internal node then TraverseInorder( n -> leftChild) Process node n if n is an internal node then TraverseInorder( n -> rightChild) Postorder Traversals Visit Left subtree Visit Right subtree Visit the root .1 .2 .3 A 16 B 9 G 10 H 8 2 5I K 1 D 15 L 2 34 T 2 14 F O 13 N 7 M 6 S 3 R 11 P 12 Algorithm TraversePostorder(n) if n is an internal node then TraversePostorder( n -> leftChild) TraversePostorder( n -> rightChild) Process node n Specification of Binary Tree ADT Elements: Any data type Structure: A binary tree either is empty OR a node, called the root node, together with two binary trees, which are disjoint from each other and the root node. These are called left and right subtrees of the root Operations: 1/Creating a Node: struct TreeNode { int value; TreeNode *left; TreeNode *right; }; 2/insert(int num);delete(int num); 3/Node *search(int num); 4/preorderWalk( Node *root ); 5/inorderWalk( Node *root ); 6/postorderWalk Height and the number of nodes in a Binary Tree If the height of a binary tree is h then the maximum number of nodes in the tree is 2h -1 If the number of nodes in a complete binary tree is n, then 2h - 1 = n 2h = n + 1 h = log(n+1) O(logn) Binary Search Trees(BST) 6 < 2 1 9 > 4 = Binary Search Trees 8 36 Binary Search Tree • A binary search tree is a binary tree storing keys (or key-value entries) at its internal nodes and satisfying the following property: – Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v. We have key(u) key(v) key(w) 6 2 1 • External nodes do not store items 37 Binary Search Trees 9 4 8 Search • To search for a key k, we trace a downward path starting at the root • The next node visited depends on the outcome of the comparison of k with the key of the current node • If we reach a leaf, the key is not found and we return nukk • Example: find(4): Algorithm TreeSearch(k, v) if T.isExternal (v) return v if k < key(v) return TreeSearch(k, T.left(v)) else if k = key(v) return v else { k > key(v) } return TreeSearch(k, T.right(v)) < 2 – Call TreeSearch(4,root) 1 O(Log2 N) 38 Binary Search Trees 6 9 > 4 = 8 Insertion 6 < • To perform operation inser(k, o), we search for key k (using TreeSearch) • Assume k is not already in the tree, and let let w be the leaf reached by the search • We insert k at node w and expand w into an internal node • Example: insert 5 2 9 > 1 4 8 > w 6 2 1 9 4 8 w O(Log2 N) 39 5 Binary Search Trees Deletion To perform operation remove(k), we search for key k Assume key k is in the tree, and let let v be the node storing k If node v has a leaf child w, we remove v and w from the tree with operation removeExternal(w), which removes w and its parent Example: remove 4 2 • 9 > 4 v 1 8 w 5 • 6 2 • 1 40 6 < • Binary Search Trees 9 5 8 Deletion (cont.) • We consider the case where the key k to be removed is stored at a node v whose children are both internal – we find the internal node w that follows v in an inorder traversal – we copy key(w) into node v – we remove node w and its left child z (which must be a leaf) by means of operation removeExternal(z) • Example: remove 3 v 3 2 8 6 w Binary Search Trees 9 5 z 1 v 5 2 8 6 O(Log2 N) 41 1 9 Summary: Trees Data Structures Tree Nodes Each node can have 0 or more children A node can have at most one parent Binary tree Tree with 0–2 children per node Tree Binary Tree Trees Terminology Root no parent Leaf no child Interior non-leaf Height distance from root to leaf Root node Interior nodes Leaf nodes Height A binary tree is a non-linear linked list where each node may point to two other nodes. Binary trees are excellent data structures for searching large amounts of information. They are commonly used in database applications to organize key values that index database records.

© Copyright 2018