TreesTrees1111111Cpt S 223. School of EECS, WSUOverview Tree data structureBinary search treesBinary search trees Support O(log2N) operationsBalanced treesBalanced trees STL set and map classes B-trees for accessing secondary storage Applications222222ppCpt S 223. School of EECS, WSUTreesG is parent of N and child of AM is child of F and grandchild of AA is an ancestor of PP is a descendant of AGenericTree:3333Cpt S 223. School of EECS, WSUDefinitions A tree T is a set of nodes that form a directed acyclic graph (DAG) such that:Ehtt htdd bEach non-empty tree has a rootnode and zero or more sub-trees T1, …, Tk Each sub-tree is a treeRecursive definition An internal node is connected to its children by a directed edge Each node in a tree has only one parent Except the root, which has no parent4444Cpt S 223. School of EECS, WSUDefinitions Nodes with at least one child is an internal node Nodes with no children are leaves“Nodes”= Either a leaf or an internal nodeNodes = Either a leaf or an internal node Nodes with the same parent are siblings A path from node n1to nkis a sequence of nodes n1, n2, …, nkhth tith tff1≤ iksuch 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 descendants555 Nodes ni,…,nk-1are proper ancestors of ni5Cpt S 223. School of EECS, WSUDefinitions: node relationshipsB,C,D,E,F,G are siblingsB,C,H,I,P,Q,K,L,M,N are leavesK,L,M are siblingsThe path from A to Q is AEJQ (with length 3)The path from A to Q is A –E –J –Q (with length 3)A,E,J are proper ancestors of Q E,J,Q, I,P are proper descendants of A6666Cpt S 223. School of EECS, WSUDefinitions: Depth, Height The depth of a node niis the length of the 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 leafTheheightof a node nis the length of theCan there be more than one?The heightof a node niis the length of the longestpath under ni’s subtreeAll leaves have a height of 0All leaves have a height of 0 height of tree = height of root = depth of tree7of treeCpt S 223. School of EECS, WSUTreesHeight of each node?e g height(E)=2 height(L)=0Height of each node?Height of tree?Depth of each node?Depth of tree?e.g., height(E)=2, height(L)=0= 3 (height of longest path from root)e.g., depth(E)=1, depth(L)=28888e.g., depth(E) 1, depth(L) 2= 3 (length of the path to the deepest node)Cpt S 223. School of EECS, WSUImplementation of Trees Solution 1: Vector of childrenStruct TreeNodeDirect access to children[i]{Object element;vector<TreeNode> children;}but…Need to know max allowedchildreninadvance Solution 2: List of children}children in advance & more spaceStruct TreeNode{Object element;Number of childrencan be dynamically determined but….i9999list<TreeNode> children;}Cpt S 223. School of EECS, WSUmore time to access childrenAlso called “First-child, next-sibling” Implementation of Trees Solution 3: Left-child, right-siblingStruct TreeNodeGuarantees 2 pointers per node{Object element;TreeNode *firstChild;TreeNode *nextSibling;Guarantees 2 pointers per node(independent of #children)But…TreeNode *nextSibling;}Access time proportional to #children10101010Cpt S 223. School of EECS, WSUBinary Trees (aka. 2-way trees) A binary tree is a tree where each node hasno morethan two children.has no morethan two children.struct BinaryTreeNode{Object element;Object element;BinaryTreeNode *leftChild;BinaryTreeNode *rightChild;} If a node is missing one or both children, then that child pointer is NULL11111111Cpt S 223. School of EECS, WSUExample: Expression Trees Store expressions in a binary tree Leaves of tree are operands (e.g., constants, variables)Oth i t l d bi tOther internal nodes are unary or binary operators Used by compilers to parse and evaluate expressions Arithmetic, logic, etc.ec,ogc,ec E.g., (a + b * c)+((d * e + f) * g)12121212Cpt S 223. School of EECS, WSUExample: Expression Trees Evaluate expressionRecursively evaluate left and right subtreesRecursively evaluate left and right subtrees Apply operator at root node to results from subtreessubtrees Traversals (recursive definitions)Postorder:left rightrootPost-order: left, right, root Pre-order: root, left, rightInorder:leftrootright131313In-order: left, root, right13Cpt S 223. School of EECS, WSUTraversals for tree rooted under an arbitrary “node” Pre-order: node -left -right Post-order: left - right - nodeIn-order:left-node-right14141414Inorder:left node rightCpt S 223. School of EECS, WSUTraversals 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*g15151515Inorder:a + b c + d e + f gCpt S 223. School of EECS, WSUExample: 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Create a BinaryTreeNode with operator as the element Pop top two items off stack Insert these items as left and right child of new node161616 Push pointer to node on the stack16Cpt S 223. School of EECS, WSUExample: Expression Trees E.g., a b + c d e + * *(1)(3)toptopab(1)(3)+edcstackab(2)abtop(4)topb()+()+dc+17171717ababedCpt S 223. School of EECS, WSUExample: Expression Trees E.g., a b + c d e + * *ttop(5)top*(6)top*ab+dc+*ab+c+*edabed18181818Cpt S 223. School of EECS, WSUBinary 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 n19191919Which one is a BST and which one is not?Cpt S 223. School of EECS, WSUSearching in BSTsCti(T)Contains (T, x){if (T == NULL)then return NULLif (T->element == x)then return Tif (x < T->element)then return Contains (T>leftChild x)then return Contains (T->leftChild, x)else return Contains (T->rightChild, x)}20202020Typically assume no duplicate elements.If duplicates, then store counts in nodes, or each node has a list of objects.Cpt S 223. School of EECS, WSUSearching in BSTs Time to search using a BST with N nodes is