TreesOverviewTreesDefinitionsDefinitionsDefinitionsDefinitionsTreesImplementation of TreesImplementation of TreesBinary TreesExample: Expression TreesExample: Expression TreesTraversalsExample: Expression TreesExample: Expression TreesExample: Expression TreesBinary Search TreesSearching in BSTsSearching in BSTsSearching in BSTsSearching in BSTsPrinting BSTsInserting into BSTsInserting into BSTsRemoving from BSTsRemoving from BSTsRemoving from BSTsImplementation of BSTSlide Number 30Slide Number 31Slide Number 32Slide Number 33Slide Number 34Slide Number 35Slide Number 36BST AnalysisBST Average-Case AnalysisRandomly Generated 500-node BST (insert only)Previous BST after 5002 Random Insert/Remove PairsBST Average-Case AnalysisBalanced BSTsAVL TreesAVL TreesMaintaining Balance ConditionAVL RemoveAVL InsertAVL InsertAVL InsertAVL InsertAVL InsertAVL InsertAVL InsertAVL InsertAVL InsertAVL Tree ImplementationAVL Tree ImplementationSlide Number 58Slide Number 59Slide Number 60Splay TreeSplay TreeSplay TreeSplaying: Zig-zagSplaying: Zig-zigSplay TreeSplay Tree: RemoveBalanced BSTsTop 10 Largest DatabasesUse a BST?IdeaBigger IdeaExampleB-treeB-treeB-tree: Choosing LB-tree: InsertionB-tree: InsertionB-tree: InsertionB-tree: DeletionB-tree: DeletionB-tree: DeletionB-treesC++ STL Sets and MapsSTL set ClassSet InsertionSidebar: STL pair ClassSet InsertionSet DeletionSet SearchSTL map ClassSTL map ClassSTL map ClassExampleExample (cont.)Implementation of set and mapSummary: Trees111111TreesCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State University22222Overview Tree data structure Binary search trees Support O(log2N) operations Balanced trees B-trees for accessing secondary storage STL set and map classes Applications33Trees3GenericTree:G is parent of N and child of AM is child of F and grandchild of A44Definitions 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 parent455Definitions 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 ancestors566Definitions6B,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 A77Definitions 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 longest path 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 depth788Trees8Height of each node?Height of tree?Depth of each node?Depth of tree?99Implementation 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;}1010Implementation of Trees Solution 3: First-child, next-sibling10Struct TreeNode{Object element;TreeNode *firstChild;TreeNode *nextSibling;}1111Binary 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;}1212Example: 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)121313Example: Expression Trees Evaluate expression Recursively evaluate left and right subtrees Apply operator at root node to results from subtrees Post-order traversal: left, right, root Traversals Pre-order traversal: root, left, right In-order traversal: root, left, right131414Traversals14 Pre-order: Post-order: In-order:1515Example: 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 stack151616 E.g., a b + c d e + * *Example: Expression Trees16ab(1)ab(2)+ab(3)+edctoptoptopab(4)+edctop+1717 E.g., a b + c d e + * *Example: Expression Trees17ab(5)+edctop+*ab(6)+edctop+**1818Binary Search Trees Complexity of searching for an item in a binary tree containing N nodes is O(?) Binary search tree (BST) For any node n, items in left subtree of n ≤ item in node n ≤ items in right subtree of n18BST?BST?1919Searching in BSTs19Contains (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.2020Searching in BSTs Complexity of searching a BST with N nodes is O(?) Complexity of searching a BST of height h is O(h) h = f(N) ?201234681234682121Searching in BSTs Finding the minimum element Smallest element in left subtree Complexity ?21findMin (T){if (T == NULL)then return NULLif (T->leftChild == NULL)then return Telse return findMin (T->leftChild)}2222Searching in BSTs Finding the maximum element Largest element in right subtree Complexity ?22findMax (T){if (T == NULL)then return NULLif (T->rightChild ==