Breadth-First Search in Binary Search Trees
Dive into the concepts of level-order traversal, also known as Breadth-First Search (BFS), in binary search trees (BSTs). Learn the challenges, techniques, and code implementation of BFS to enhance your understanding of data structures and algorithms.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12
2 Today s Topics 1. Wrap up traversals from Tuesday Level-order traversal Also known as Breadth-First Search (BFS) 2. Binary Search Trees (BSTs) Note: These are different from plain vanilla Binary Trees! They are a special kind of Binary Tree!
Level-order traversal AKA Breadth-first search
Level-order traversal Also commonly called Breadth-First Search or BFS As opposed to something like pre-order or post-order, which are Depth-First Search (DFS) algorithms
Level-order challenges How do we know where to go next? 1, 2, 3 but there is no edge from 2 to 3! While we re still at 1, we must remember to come back to 3 after we re done with 2 At 2, remember to come back to 4 and 5 after 3 At 8, remember to come back to 16 and 17 after 15 Etc
How to remember When we visit a node, add references (pointers) to its children to a queue To know which node to visit next, remove next element from the queue
Tracing the queue in BFS Which shows the state of the queue at the end of visiting node #10?( head of the queue, i.e. the next element that will be removed, is the leftmost) A. 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11 B. 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 C. 20, 21 D. 1, 2, 5 E. Other/none/more
BFS code BFS(node) { Queue<Bnode> q = new Queue<Bnode>(); q.add(node); while (!q.isEmpty()) { current = q.remove(); System.out.println(current.getData()); } } A. BFS(current.getLeftChild()); B. BFS(current.getRightChild()); C. q.add(current.getLeftChild()); D. q.add(current.getRighChild()); E. Other/none/more What goes here?
Reading quiz! 1. A total order must apply to data elements in a Binary Search Tree. A. TRUE B. FALSE
Reading quiz! 2. An inorder traversal of a binary search tree visits the tree s elements in sorted order. A. TRUE B. FALSE
Binary Search Tree (BST) RULE: For everynode: Everything in its left subtree is less than it Everything in its right subtree is greater than it
Binary Search Tree (BST) FACT: The in-order traversal method, when applied to a BST, gives sorted order FACT: Easy to find things: just recursively check if you should go left or right based on > or <
BST add() Create two BSTs by inserting the elements, one by one, in the order given below for the first letter of your last name: A-F: {18, 9, 34, 3, 22} G-L: {3, 18, 22, 9, 34} M-R: {22, 9, 34, 3, 18} S-Z: {34, 3, 9, 18, 22} EVERYBODY do this for a 2nd BST: {3, 9, 18, 22, 34}
What is the BEST CASE cost for doing find() in BST? A. O(1) B. O(log n) C. O(n) D. O(n log n) E. O(n2)
What is the WORST CASE cost for doing find() in BST? A. O(1) B. O(log n) C. O(n) D. O(n log n) E. O(n2)
What is the WORST CASE cost for doing find() in BST if the BST is complete? A. O(1) B. O(log n) C. O(n) D. O(n log n) E. O(n2)
BALANCE!!! The #1 issue to remember with BSTs is that they are great when balanced (O(log n) operations), and horrible when unbalanced (O(n) operations) Balance depends on order of insert of elements Over the years, people have devised many ways of making sure BSTs stay balanced no matter what order the elements are inserted
Red-Black trees One of the most famous (and most tricky) strategies for keeping a BST balanced Not guaranteed to be perfectly balanced, but close enough to keep O(log n) guarantee on operations
Red-Black trees In addition to the requirements imposed on a binary search trees, red black trees must meet these: A node is either red or black. The root is black. All leaves (null children) are black. Both children of every red node are black. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. (This is what guarantees close to balance)
Red-Black trees Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. (This is what guarantees close to balance)
Insert procedure must maintain the invariants (this gets tricky) Video: http://www.youtube.com/watch?v=vDHFF4wjWYU
Other BST balance strategies Red-Black tree AVL tree Treap (BST + heap in one tree!) Other fun types of BST: Splay tree Rather than only worrying about balance, Splay Tree dynamically readjusts based on how often a particular item is searched for Commonly-searched items move to the top, saving time B-Tree Like BST, but a node can have many children, not just 2
More practice: find() Practice finding each of these: 6, 25, 11
More practice: find() How do we know that 12 is NOT in the tree?
