CS 234留学生代做、代写Python语言、Python程序设计调试、代做binary tree

日期：2019-07-28 11:03

CS 234 Spring 2019 — Assignment 4

Due date: July 30, 2019, at 5:00pm

Coverage: Modules 7, 8, and 9

This assignment consists of a programming component and a written component. Please read the course website

carefully to ensure that you submit each component correctly. This assignment contains 80 marks but it will be

marked out of 75 so it is possible to get over 100% on this assignment.

1 Programming Component

P1. (25 marks) In this question you will implement the Priority Queue ADT using a (min-)heap data structure.

PriorityQueue will store key-element pairs, where keys and elements can be of any type, as long as keys

are orderable (they do not need to be distinct). Submit your solution in the files priority queue.py and

binary tree.py. Working implementations that do not use the required data structure will NOT receive

correctness marks. Starting files are provided for your convenience.

PriorityQueue Interface

Pre-conditions: For lookup min and delete min, self is not empty.

Name Returns Mutates

PriorityQueue() An empty PriorityQueue.

is empty(self) True if self is empty, false otherwise.

add(self, key, element) A (key, element) pair is added to

self. See the interface for ADT

Pair.

delete min(self) The pair with minimum key in

self

Removes the pair with minimum

key from self.

lookup min(self) The pair with minimum key in

self.

Pair Interface

Name Returns Mutates

Pair(key, element) A new key-element Pair.

get key(self) Returns self’s key.

get element(self) Returns self’s element.

str(self) Returns a string representation of

self, e.g. ”(5, True)” if the key is

5, and the element is True

1

BinaryTree Interface For all functions that take node/node1/node2 as one of parameters, they represent a

valid node in self. For all operations, self is a complete Binary Tree.

Name Returns Mutates

BinaryTree() An empty Binary Tree

is empty(self) True if selfis empty, false otherwise

get root(self) The root node of self.

get key(self, node) The key of node in self.

get element(self, node) The element of node in self.

get parent(self, node) Returns the parent node of node,

if one exists, and False otherwise.

get left(self, node) Returns the left child node of node,

if one exists, and False otherwise.

get right(self, node) Returns the right child node of

node, if one exists, and False otherwise.

get last(self) Returns the location of the last leaf

in self.

previous leaf(self) Returns the location of what would

be the last leaf in self if the last

leaf was removed.

next leaf(self) Returns the location of the last leaf

in self if a new leaf was added.

swap node values(self, node1,

node2)

Swaps the key-element pairs stored

in node1 and node2 in self.

add last(self, key, element) Adds a key-element pair in self at

the next leaf position.

delete last(self) Deletes the last leaf in self.

traverse(self) Prints nodes in a level-order traversal.

Details for printing below.

When traversing a Binary Tree, the key-element pair will be printed on their own line as follows:

(key, element)

For example, this program:

tree = Binary_Tree()

tree.add_last(25, "hi")

tree.add_last(10, "hello")

tree.add_last(50, "heap")

tree.add_last(5, "cs234")

tree.traverse()

prints the following:

(25, hi)

(10, hello)

(50, heap)

(5, cs234)

2

P2. (15 marks) Storing sorted values in contiguous memory allows for constant time access of elements based on

their position in an array. You will implement an ADT Sorted Array that stores the inserted integers from

smallest to largest. Implement the following operations in sortedArray.py.

Sorted Array Interface

Your implementation of the sorted array ADT may store multiple instances of the same element. Order of

elements with the same value does not matter. Your implementation must use the built-in Python list to store

data, however, the only Python list operations you can use are accessing an index using square brackets, e.g.

A[i], and the length function. Any solution that uses other Python list functions will receive no marks.

You may assume that there is always space to insert a new element for testing purposes. You cannot assume

that an item is not present in the array before addition (we allow duplicates), nor can you assume an item is

present in the array before deleting it.

When performing interpolation search, use the formula b((search ? low)/(high ? low) length)c to determine

the next item to compare. When updating the low and high values from a search, set low to mid + 1 and high

to mid 1.

Name Returns Mutates

SortedArray(capacity) An empty Sorted Array that has

space for capacity elements.

is empty(self) True if self is empty, false otherwise.

item in self True if item is storted in self,

false otherwise.

access(self, index) Returns the value stored at index.

add(self, item) Stores one instance of item in

self.

delete(self, item) Removes one instance of item in

self.

linear search(self, item) A pair; its key is an index where

item may be stored, and its element

is the number of items

checked using a linear search.

binary search(self, item) A pair; its key is an index where

item may be stored, and its element

is the number of items

checked using a binary search.

interpolation search(self, item) A pair; its key is an index where

item may be stored, and its element

is the number of items

checked using an interpolation

search.

2 Written Component

W1. (10 marks)

Suppose the Binary Node N was just added to an AVL Tree. The tree must be modified to ensure that the tree

is still an AVL. Write the pseudocode for each of the following steps of modifying an AVL after an insert. You

do not need to insert N into into the Tree, nor justify the running time. However, you will be marked based

on whether your operations meet the required running times.

(a) (5 marks) Write the pseudocode for the function find pivot(Tree, N), where N is a Binary Node that

was inserted into Tree. The function returns the pivot node in Tree, or False, if no rotation is required

3

after adding N into Tree. This function also updates the heights of all nodes up to and including the

pivot, if one exists. If no rotation is required, update the heights of all nodes that need to be updated.

This operation’s running time should be Θ(log n).

(b) (5 marks) Write the pseudocode for the function rebalance(Tree, N), where N is the Binary Node that

was just inserted into Tree. The function updates the heights of all affected nodes and rebalances the tree

T ree if necessary.

You must determine which rotation case must be performed to correctly pivot the nodes to make a balanced

AVL. You can call algorithms from class using the methods rotation case i(Tree, P), where P is the

pivot node and i represents the rotation cases described in class. This operation’s running time should be

Θ(log n).

W2. (5 marks) This problem will concern operations on the following AVL tree T:

(a) (1 marks) Show that T is an AVL tree by writing in the balance at each node.

(b) (2 marks) Show the process of inserting key 29 into T. Specifically, draw the tree, with balance factors,

immediately before a rotation needs to be performed. Identify the pivot node and the rotation case . Then

draw the final tree, with balance factors at each node.

(c) (2 marks) Show a similar process of deleting key 49 from the original tree T above.

W3. (5 marks) Insert 1, 2, 3, . . . 9 into an initially empty 2-3 tree. Only draw the tree after every height change and

the tree after inserting 9; the first tree you should draw is the tree on one node containing the single key 1.

W4. (10 marks)

(a) (5 marks) Let the array A contain the following keys: [3, 1, 4, 1, 17, 26, 6, 5, 9, 5, 98, 2, 6, 10]. Show the

array after each Bubble-Down call during the Heapify operation (there will be 7 such arrays). Specifically,

use the algorithm that processes the array from right to left (applying Bubble-Down procedure for each

index in the array that corresponds to an internal node of the heap), until the entire array forms a

(min-)heap, using the procedure showed in class and in slides.

(b) (5 marks) If we modify the Heapify operation to fix up the heap from left to right (rather than right to

left), while still applying the Bubble-Down procedure at each step (i.e. for each internal node of the heap),

would the resulting array produce a heap? If not, give an example of an array A (or a corresponding

binary tree) that would not generate a heap after applying this version of Heapify.

W5. (5 marks) Consider a self-organizing heuristic which alternates between Move-To-Front and Transpose. Precisely,

to organize the list after the i’th access, the accessed item is moved to front if i is odd and is swapped

with its previous item if i is even. For example, for a sequence initially ordered as [A,B,C,D], if D is searched

first and C is search second, the algorithm proceeds by moving D to the front and then swapping C with B,

resulting in [D,A,C,B].

Consider a sequence of n keys, k1, k2, . . . , kn, where n is an odd integer. Describe the sequence of n searches

that results in the maximum cost and compute the cost of performing these n searches.

W6. (5 marks) Assume that we have a hash table of size N = 5, we use the hash function f(x) = x mod 5, and

we use separate chaining for collision resolution. Demonstrate the insertion of the keys 0, 1, 2, . . . , 12 into the

(initially empty) hash table (in that order). You just need to draw the state of the hash table after all insertions

are done.

4