Binary Search Introduction to Trees

Binary Search Introduction to Trees Last time: recursion In the last lecture, we learned about recursion & divide-and-conquer Apply these techniques to storing data so that it is Ordered Easy to find Hash tables and list-type structures dont do both Split the problem into smaller parts Solve each of the smaller parts separately: easier to code & understand! Lists & arrays: ordered, but lookup is slow Hash tables: lookup is fast, but not ordered We want a structure that can do both! CMPS 12B, UC Santa Cruz

Binary searching & introduction to trees 2 Quickly finding a particular item Problem: in a class of n students, who has the mth best grade? Use a hash table? Use a (sorted) linked list? Easy to add and lookup new students Table has no order: very difficult to answer this question without sorting it first Easy to find: count m links from the start Difficult to insert: must search along the list to find the correct insertion point Use an array? Same kinds of advantages and disadvantages as linked list CMPS 12B, UC Santa Cruz Binary searching & introduction to trees

3 What if we only have the value? Rather than find the mth best grade, find the student whose grade is 77 Cant just count m items any more! Must scan the list / array until we find the correct student A better way: play 20 questions! Guess a random number between 1 and 1 million in only 20 guesses! How can we do this? How does this apply to searching? CMPS 12B, UC Santa Cruz Binary searching & introduction to trees 4 20 Questions

Take a sorted array of values While (item not found) Guess the item in the middle of the array See if the desired item is above or below the guess Narrow down the search area by half This works in log2(N) tries on an array with N values Much faster than simply scanning CMPS 12B, UC Santa Cruz Binary searching & introduction to trees 5 Binary search

int bsearch (int values[], int findThis) { int range = values.length; int base = 0; int mid; Problem split in half at each step while (range > 1) { Main difference: ignore the half range = (range+1)/2; mid = base+range; where the value isnt if (findThis > values[mid]) { Recursion doesnt usually save base = mid; } else if (findThis==values[mid]){ time break; Easier to program, though } Binary search saves time! } Rule out half of the remaining if (values[mid]==findThis) { return (mid); values at each step } else { Like recursion where we ignore return (-1); half of the problem each time we } } recurse 20 questions is called binary search Similar to recursion

CMPS 12B, UC Santa Cruz Binary searching & introduction to trees 6 Binary search is great, but Binary search works well with arrays Binary search doesnt work well with linked lists Easy to find element n in constant time Difficult to insert things into the middle of the array Cant find element n in constant time: long lists => long time to find elements Easy to insert and delete things in the middle Modify linked lists to make searching easier? Keep references into the middle of the list (1/4, 1/2, 3/4, or similar)? Good idea, but doesnt scale that well

Must recreate shortcuts when things are inserted or deleted Create a new structure that uses links but is still easy to do binary search on? CMPS 12B, UC Santa Cruz Binary searching & introduction to trees 7 Solution: trees A tree is a linked data structure where nodes may have more than one next Terms next of a node is its child prev of a node is its parent Base of the tree is the root Nodes along path to root are ancestors Nodes below this one are descendants

Nodes with no children are leaf nodes Binary tree: tree in which each node has at most two children CMPS 12B, UC Santa Cruz root A B C parent leaf D E child Class BTNode { Object item; BTNode left; BTNode right; BTNode parent; } Binary searching & introduction to trees 8 Why use trees? Advantages of linked lists

Advantages of arrays Easy to do binary search Easy to keep sorted Advantages of hash tables Insert or delete anywhere with ease Grow to any size Lookup can be done quickly if the tree is sorted Disadvantages? Overhead: three references per node in the tree Its easy to have trees grow the wrong way CMPS 12B, UC Santa Cruz Binary searching & introduction to trees 9

Recently Viewed Presentations

  • Immobilized Enzymes Reactors - BioJuncture

    Immobilized Enzymes Reactors - BioJuncture

    The mobile phase contains all required cosubstrates and activators required for the enzymatic reaction, but does not contain the analyte substrate. A typical packed-bed system may use a 25-cm long reactor with a 5-mm inner-diameter, packed with the carrier-enzyme solid...
  • Title

    Title

    Improved Cook Stoves. Business Model: aggregating demand and incentivize sales promotion. e.g., Viet Nam Women's Union linked to producers of approved stoves, receive training and incentives to sell stoves. First sale campaign: 3days sales of 300 and 80 achieved in...
  • Mike Lloyd Strategic Marketing Manager Education Group Microsoft

    Mike Lloyd Strategic Marketing Manager Education Group Microsoft

    We're working on Web Parts with key vendors including Questionmark, Blackboard, Distinction, and for integration with WebCT, . Later this summer we will launch SSN Educa, a community for sharing code, best practices and commercial availability of custom product integrations.
  • How will we do this?

    How will we do this?

    Define more by the creative process and its wider applications, not simply limiting to careers and the products of engineering . Most recently published a report that attempts understand how engineering is perceived by schools. Drawing on two research studies:
  • The First Year - University of Winnipeg

    The First Year - University of Winnipeg

    The First Year Projected enrolment - first draft Agenda Factors influencing retention Who stays What happens when they leave Reason for Going to University (%) Why this Particular U (% very important reason) % at first Choice Retention Factors Ability/Program...
  • Disease Informatics: Phytates driving from the back-end to

    Disease Informatics: Phytates driving from the back-end to

    Intervention to amend the DiCC so that the events leading to viral diseases are bypassed or does not occur (even after exposure to the viruses) are the solutions to the diseases. DiCC: Disease Causal Chain Prof. Linda Fried Boyd CM,...
  • Informal consultation on Strengthening Medicines Regulation ...

    Informal consultation on Strengthening Medicines Regulation ...

    Réaliser le consensus au sein des Etats membres d'une même CER Valider la proposition par l'engagement des représentants de chaque ANRP Confirmer l'engagement politique des pays à un haut niveau Etablir les mécanismes financiers nécessaires aux mouvements des fonds Les...
  • Fruit & Vegetabl eProduction Fruit & Production Vegetable

    Fruit & Vegetabl eProduction Fruit & Production Vegetable

    • A cool season crop is a crop that grows best during the cool temperatures of fall and spring. Cool season crops prefer temperature between 50°F and 70°F. They are very tolerant of cold weather and can usually stand a...