1111111Trees222222OverviewTree data structureBinary search treesSupport O(log2N) operationsBalanced treesSTL set and map classesB-trees for accessing secondary storageApplications333Trees3GenericTree:G is parent of N and child of AM is child of F and grandchild of AA is an ancestor of P444DefinitionsA tree T is a set of nodesEach non-empty tree has a root node and zero or more sub-trees T1, …, TkEach sub-tree is a treeThe root of a tree is connected to the root of each subtree by a directed edgeIf node n1connects to sub-tree rooted at n2, thenn1is the parent of n2n2is a child of n1Each node in a tree has only one parentExcept the root, which has no parent4Recursive definitionCan a tree have a cycle? “DAG”555DefinitionsNodes with no children are leavesNodes with the same parent are siblingsA path from nodes n1to nkis a sequence of nodes n1, n2, …, nksuch that niis the parent of ni+1for 1 ≤ i < kThe length of a path is the number of edges on the path (i.e., k-1)Each node has a path of length 0 to itselfThere is exactly one path from the root to each node in a treeNodes ni,…,nkare descendants of niand ancestors of nkNodes ni+1,…, nkare proper descendantsNodes ni,…,nk-1are proper ancestors5666Definitions6B,C,H,I,P,Q,K,L,M,N are leavesB,C,D,E,F,G are siblingsK,L,M are siblingsThe path from A to Q is A – E – J – QA,E,J are proper ancestors of Q E,J,Q (and I,P) are proper descendants of A777DefinitionsThe depth of a node niis the length of the unique path from the root to niThe root node has a depth of 0The depth of a tree is the depth of its deepest leafThe height of a node niis the length of the longestpath from nito a leafAll leaves have a height of 0The height of a tree is the height of its root nodeThe height of a tree equals its depth7Can there bemore than one?888Trees8Height of each node?Height of tree?Depth of each node?Depth of tree?999Implementation of TreesSolution 1: Vector of childrenSolution 2: List of children9Struct TreeNode{Object element;vector<TreeNode> children;}Struct TreeNode{Object element;list<TreeNode> children;}101010Implementation of TreesSolution 3: First-child, next-sibling10Struct TreeNode{Object element;TreeNode *firstChild;TreeNode *nextSibling;}111111Binary TreesA binary tree is a tree where each node has no more than two children.If a node is missing one or both children, then that child pointer is NULL11struct BinaryTreeNode{Object element;BinaryTreeNode *leftChild;BinaryTreeNode *rightChild;}121212Example: Expression TreesStore expressions in a binary treeLeaves of tree are operands (e.g., constants, variables)Other internal nodes are unary or binary operatorsUsed by compilers to parse and evaluate expressionsArithmetic, logic, etc.E.g., (a + b * c)+((d * e + f) * g)12131313Example: Expression TreesEvaluate expressionRecursively evaluate left and right subtreesApply operator at root node to results from subtreesTraversalsPost-order: left, right, rootPre-order: root, left, rightIn-order: left, root, right13141414Traversals for tree rooted under an arbitrary “node”14Pre-order: node - left - rightPost-order: left - right - nodeIn-order: left - node - right151515Traversals15Pre-order: + + a * b c * + * d e f gPost-order: a b c * + d e * f + g * +In-order: a + b * c + d * e + f * g161616Example: Expression TreesConstructing an expression tree from postfix notationUse a stack of pointers to treesRead postfix expression left to rightIf operand, then push on stackIf operator, then:Create a BinaryTreeNode with operator as the elementPop top two items off stackInsert these items as left and right child of new nodePush pointer to node on the stack16171717E.g., a b + c d e + * *Example: Expression Trees17ab(1)ab(2)+ab(3)+edctoptoptopab(4)+edctop+181818E.g., a b + c d e + * *Example: Expression Trees18ab(5)+edctop+*ab(6)+edctop+**191919Binary Search Trees“Binary search tree (BST)”For any node n, items in left subtree of n ≤ item in node n ≤ items in right subtree of n19Which one is a BST and which one is not?202020Searching in BSTs20Contains (T, x){if (T == NULL)then return NULLif (T->element == x)then return Tif (x < T->element)then return Contains (T->leftChild, x)else return Contains (T->rightChild, x)}Typically assume no duplicate elements.If duplicates, then store counts in nodes, or each node has a list of objects.212121Searching in BSTsComplexity of searching a BST with N nodes is O(?)Complexity of searching a BST of height h is O(h)h = O(N) 21123468123468222222Searching in BSTsFinding the minimum elementSmallest element in left subtreeComplexity ?22findMin (T){if (T == NULL)then return NULLif (T->leftChild == NULL)then return Telse return findMin (T->leftChild)}232323Searching in BSTsFinding the maximum elementLargest element in right subtreeComplexity ?23findMax (T){if (T == NULL)then return NULLif (T->rightChild == NULL)then return Telse return findMax (T->rightChild)}242424Printing BSTsIn-order traversal ==> sortedComplexity?24PrintTree (T){if (T == NULL)then returnPrintTree (T->leftChild)cout << T->elementPrintTree (T->rightChild)}1 2 3 4 6 8252525Inserting into BSTsE.g., insert 525262626Inserting into BSTs“Search” for element until reach end of tree; insert new element there26Insert (x, T){if (T == NULL)then T = new Node(x)elseif (x < T->element)then if (T->leftChild == NULL)then T->leftChild = new Node(x)else Insert (x, T->leftChild)else if (T->rightChild == NULL)then (T->rightChild = new Node(x)else Insert (x, T->rightChild)}Complexity?272727Removing from BSTsThere are two cases for removalCase 1: Node to remove has 0 or 1 childAction: Just remove it and make appropriate adjustments to retain BST structureE.g., remove 427282828Removing from BSTsCase 2: Node to remove has 2 childrenAction:Replace node element with successorRemove successor (case 1)E.g., remove 228292929Removing from BSTs29Remove (x, T){if (T == NULL)then returnif (x == T->element)then if ((T->left == NULL) && (T->right != NULL))then T = T->right // implied delete (case 1)else if ((T->right == NULL) && (T->left != NULL))then T = T->left // implied delete (case 1)else {successor = findMin (T->right) // Case 2T->element = successor->elementRemove (T->element, T->right)}else if (x <