Lecture 16-17-18

Binary Trees

Binary Search Trees�Search in BST

Binary Tree

Binary Tree Traversal

Possible?

Give a tree with at least 3 nodes (all nodes must have different keys) such that both its in-order read and its pre-order read are the same, or prove that there is no such tree.

​

Binary search trees

Binary SEARCH tree

• A binary search tree (BST) is a binary-tree based data structure that offers O(log n) average-case time costs for:
• Add(element)
• Find(element)
• Remove(element)
• findLargest/removeLargest(element)

​

BST

• Binary Search Tree is a node-based binary tree data structure which has the following properties:
• The left subtree of a node contains only nodes with keys smaller than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.

Reminders

• Mic
• If main with magic numbers and lost points, let me know (PA04)

CompareTo

compareTo, simplified

• Allows us to compare Objects: Students, Cars, Apples, Animals…
• In order to use this method, one needs to let Java know how to compare:
• https://docs.oracle.com/javase/9/docs/api/java/lang/Comparable.html#compareTo-T-

​

• If the values are the same then 0 is returned.
• If one value is less than the argument then the negative integer is returned.
• If one value is greater than the argument then the positive integer is returned.

​

Example

public class Test {

​

public static void main(String args[]) {

Integer x = 5;

System.out.println(x.compareTo(3)); # 1

System.out.println(x.compareTo(5)); # 0

System.out.println(x.compareTo(8)); # -1

}

}

​

Example

public class Student {

int age;

int compareTo(Student st) {

if this.age == st.age return 0;

if this.age > st.age return 1;

If this.age < st.age return -1;

...

}

​

}

​

public static void main(String args[]) {

Student st1 = new Student(19);

Student st2 = new Student(22);

SOS(st1.compareTo(st2)); # -1

​

BST implementation

Insert

Do we need recursion for the third one?

​

A: Yes

B: No

​

Duplicate keys

• Allow them and be consistent with the rule

​

• Node is a linked (Array) list. All duplicates are linked.

​

How to delete an element from a BST

Lazy deletion

Complexity

Complexity

What is the output?

A: 10, 5, 3, 7, 15, 18

​

B: 3, 5, 7, 10, 15, 18

�C: 3, 7, 5, 18, 15, 10

�D: 3, 5, 7, 15, 10, 18

�E: Something else

Iterators

What is the time complexity?

for (int i = 0; i< linkedlist.size(); i++) {

elem = linkedlist.getElem( i ) ;

print(elem);

}

​

A: O(1)

B: O(n)

C: O(n log n)

D: O(n^2)

E: Something else

Iterators in Java, performance benefits

• An “iterator” object helps us to avoid this wasted computation.
• An iterator is a “helper object” with which the user can iterate across all elements in a data structure.
• The iterator will “remember” where it left off.
• Even very different data structures --e.g., graphs and lists -- can both support iterators.
• Python has them as well

​

​

Iterator interface

In Java, the Iterator interface contains three (well, four now) method signatures:

• boolean hasNext();
• E next();
• void remove();

Java documentation

Iterator for a Linked List

import java.util.*;

class IteratorExample {

public static void main(String [] args) {

// Create an linked list

LinkedList <Integer> intList = new LinkedList <>();

for (int i=10; i<20; i++)

intList.add(i);

​

import java.util.*;

class IteratorExample {

public static void main(String [] args) {

// Create an linked list

LinkedList <Integer> intList = new LinkedList <>();

for (int i=10; i<20; i++)

intList.add(i);

​

//To start, we need to obtain an Iterator from a Collection; this is done by calling the iterator() method.

// we’ll obtain Iterator instance from a list:

​

Iterator itr = intList.iterator(); // created the iterator object

​

​

import java.util.*;

class IteratorExample {

public static void main(String [] args) {

// Create an linked list

LinkedList <Integer> intList = new LinkedList <>();

for (int i=10; i<20; i++)

intList.add(i);

Iterator itr = intList.iterator(); // created the iterator object

while(itr.hasNext()) {

Object element = itr.next();

System.out.print(element + " ");

}

System.out.println();

​

​

• boolean hasNext();
• E next();
• void remove();

import java.util.*;

class IteratorExample {

public static void main(String [] args) {

// Create an linked list

LinkedList <Integer> intList = new LinkedList <>();

for (int i=10; i<20; i++)

intList.add(i);

Iterator itr = intList.iterator(); //created the iterator object

while(itr.hasNext()) {

Object element = itr.next();

System.out.print(element + " ");

}

System.out.println();

​

​

10 11 12 13 14 15 16 17 18 19

​

​

import java.util.*;

class IteratorExample {

public static void main(String [] args) {

// Create an linked list

LinkedList <Integer> intList = new LinkedList <>();

for (int i=10; i<20; i++)

intList.add(i);

Iterator itr = intList.iterator(); // created the iterator object

while(itr.hasNext()) {

Object element = itr.next();

System.out.print(element + " ");

}

System.out.println();

​

​

10 11 12 13 14 15 16 17 18 19

​

​

https://docs.oracle.com/javase/8/docs/api/java/util/ListIterator.html

Iterators for other data structures

• When you develop your own data structure, you want a user to be able to iterate over it.
• When the data structure is linear (lists, arrays, sets) then it is clear what the next element is.
• But if you have a tree? Or a graph?

Iterable

interface

Iterable interface

Interface Iterator

• In Java, the Iterator interface contains three method signatures:

boolean hasNext();

E next();

void remove();

• The ListIterator interface adds a few more methods.

boolean hasPrevious();

E previous();

•…

​

In HW6

public class BSTree<T extends Comparable<? super T>> implements Iterable

​

Example: how to create an iterator

To implement an iterable data structure, we need to:

1. Implement Iterable interface along with its methods in the said Data Structure

​

​

Example: how to create an iterator

To implement an iterable data structure, we need to:

1. Implement Iterable interface along with its methods in the said Data Structure
2. Create an Iterator class which implements Iterator interface and corresponding methods.
1. boolean hasNext();
2. E next();
3. void remove();

​

import java.util.*;

​

public class A implements Iterable{

​

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!

}

Iterator: every second item in ArrayList

​

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

• boolean hasNext();
• E next();
• void remove();

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

​

public boolean hasNext() {

}

• boolean hasNext();
• E next();
• void remove();

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

​

public boolean hasNext() {

if (arr.size() == 0)

return false;

}

• boolean hasNext();
• E next();
• void remove();

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

​

public boolean hasNext() {

if (arr.size() == 0)

return false;

if (cursor==arr.size()-1)

return true;

if (cursor <= arr.size()-2) // needs to be tested

return true;

else

return false;

}

• boolean hasNext();
• E next();
• void remove();

import java.util.*;

public class A implements Iterable{

ArrayList arr = new ArrayList();

public Iterator iterator() {

return new ArrayList_It(); # another object!}

# inner class

class ArrayList_It implements Iterator{

​

int cursor;

​

public ArrayList_It() {

cursor = 0;

}

​

public Object next() {

int to_return = (Integer) arr.get(cursor);

cursor = cursor + 2;

return to_return;

}

• boolean hasNext();
• E next();
• void remove();