Koofers

Lecture Notes for CMSC 132 - OBJECT-ORIENTED PROG II with Padua-Perez at Maryland (UMD)

Notes Information

Material Type:Class Note
Professor:Padua-Perez
Class:CMSC 132 - OBJECT-ORIENTED PROG II
Subject:Computer Science
University:University of Maryland
Term:--
Keywords:
  • On the Left
  • On the Right
  • Binary Search
  • Polymorphic
  • Sorted Order
  • Observation
  • Largest Value
  • Design-Build
  • Principles of Design
  • Binary Search Tree
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

Sample Document Text

1 Binary Search Trees CMSC 132 Department of Computer Science University of Maryland, College Park 2 Overview Binary Search Tree Search Properties Construction Insertion Deletion Polymorphic BST Polymorphic, recursive linked list 3 Binary Search Tree (BST) Key property Value at node Smaller values in left subtree Larger values in right subtree Example X > Y X < Z Y X Z 4 Binary Search Trees Examples Binary search trees Non-binary search tree 5 10 30 2 25 45 5 10 45 2 25 30 5 10 30 2 25 45 5 Iterative Search of BST Node Find( Node n, Value key) { while (n != null) { if (n.data == key) // Found it return n; if (n.data > key) // In left subtree n = n.left; else // In right subtree n = n.right; } return null; } Find( root, keyValue ); 6 Recursive Search of Binary Tree Node Find( Node n, Value key) { if (n == null) // Not found return( n ); else if (n.data == key) // Found it return( n ); else if (n.data > key) // In left subtree return Fin...

Related Documents

Binary Search Notes
Following Values Notes
Problem Description Exam
Problem Description Exam
Cmsc 132 Quiz Quiz
Unauthorized Exam
Unauthorized Exam
Load Factor Exam
Unauthorized Exam
Problem Description Exam
Implementation Notes
Following Values Exam
Following Values Exam
Provided That Notes
Provided That Notes
Abstraction Notes
155, "/var/app/current/tmp/"