Understanding Binary Search Trees and Tree Traversal Methods
Explore the world of binary search trees with a focus on defining trees, modifying them, and different ways to print their contents. Delve into the concept of tree traversal methods such as pre-order, in-order, and post-order. Additionally, discover insights into searching algorithms for arrays of numbers, including scenarios with sorted arrays. Join the lesson for a comprehensive understanding of these fundamental data structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Binary Search Trees Hitesh Boinpally Summer 2023
Agenda Review of Trees Binary Search Trees Modifying a Tree Lesson 10 - Summer 2023 2
Agenda Review of Trees Binary Search Trees Modifying a Tree Lesson 10 - Summer 2023 3
Trees Defined root Tree: Nodes linked together in some hierarchical fashion Binary Tree: A tree where each node has at most 2 children 1 2 3 Recursive Definition: A tree is either: 1. Empty 2. A node with data, and a left and right subtree 4 5 6 Lesson 10 - Summer 2023 4
Printing Trees root Want to print out the contents of the tree 48 Different ways to do so: 21 10 Pre-order 48 21 5 10 8 6 In-order 5 21 48 8 10 6 5 8 6 Post-order 5 21 8 6 10 48 Lesson 10 - Summer 2023 5
Agenda Review of Trees Binary Search Trees Modifying a Tree Lesson 10 - Summer 2023 6
Aside: Searching Given an array of numbers, check if a certain number is in it. How many elements do we have to go through in the worst case? Lesson 10 - Summer 2023 7
Aside: Searching Given an array of numbers, check if a certain number is in it. How many elements do we have to go through in the worst case? All of them if the element isn t in the list Lesson 10 - Summer 2023 8
Aside: Searching Given an array of numbers, check if a certain number is in it. How many elements do we have to go through in the worst case? All of them if the element isn t in the list What if the array was sorted? Lesson 10 - Summer 2023 9
Aside: Searching Given an array of numbers, check if a certain number is in it. How many elements do we have to go through in the worst case? All of them if the element isn t in the list What if the array was sorted? Find the element 27 -10 -6 5 18 27 48 301 Lesson 10 - Summer 2023 10
Binary Search Trees root We can apply these properties to trees to speed up our searching ability Think: TreeSets 18 Binary Search Tree (BST): A binary tree with the following property: For every non-empty node `root`: elements of root's left subtree contain data "less than" root's data elements of root's right subtree contain data "greater than" root s data root's left and right subtrees are also binary search trees -6 48 -10 5 27 301 Lesson 10 - Summer 2023 11
Agenda Review of Trees Binary Search Trees Modifying a Tree Lesson 10 - Summer 2023 12
Whats the output of this program? slido.com code: #su_cse123 Lesson 10 - Summer 2023 13
x = change(x) To modify a binary tree, need to change the overallRoot or a root s .left / .right Similar to the front or .next of a linked node For trees we utilize the x = change(x) pattern A few components: Pass in the original value of x Change the value somehow in the method change Return the updated value of x Re-assign the updated value to x Lesson 10 - Summer 2023 14
