Key Assignment Draft: Include session changesThe first two Individual Projects used linked lists for...

Question

Key Assignment Draft: Include session changesThe first two Individual Projects used linked lists for stacks, queues, and hashing implementations. With this task, searching performance with linked lists will be addressed.	Part 1: Your tasks for this assignment are the following:	Discuss the use of a binary tree when searching for keys in an array.	Discuss the use of a binary tree when searching for keys in a linked list.	Part 2: Complete the following program:	Describe a linked list structure to support binary searching.	Create pseudo code to describe a binary search with this linked list variation.it will be inserted into section 4: searching1 IT265 – 2003B Data Structures using Java document shell Demetricus Dixon 8/26/20 Contents Abstract	2 Section 1: Lists, Stacks, and Queues	3 Section 1.1: Stacks	3 Section 1.2: Queues	5 Section 2: Heaps and Trees	7 Section 3: Sorting Algorithms	10 PART 1.	10 PART 2.	11 Section 4: Searching	12 Section 5: Recursion  TBD	13 Conclusion	14 References	15 Abstract Section 1: Lists, Stacks, and Queues Let the linked list node be represented by the ‘Node’. Each ‘Node’ has a data item ‘Data’ of data type T and a ‘NextRef’ attribute pointing to the next node in the linked list. class  Node{ 	T Data;		// The data item of a node. 	Node NextRef;	// link to the next Node in the list } We will implement stacks and queues using linked lists. The sub-sections below has the details of the implementations. Section 1.1: Stacks   Assume a ‘Head’ Node exists with the NextRef attribute pointing to the first node in the stack or being null if the stack is empty. Given below is the pseudo code for the following 3 stack methods : push(item), pop( ) and display( ). Note that in the Java style pseudocodes given below, the top of the stack is the Node pointed to by ‘head’.  void push(T item)  {     // create a new 'Node' called newnode    // with item as the 'Data' and null as its 'NextRef'    Node newnode = new Node(item, null);        if(head==null)  	// stack is empty      head = newnode;	// set the newnode as the ‘head’    else  // stack is not empty    {      // push to the top of the stack      newnode.nextRef = head;		      head = newnode;	// the newnode is the new head    }  }  T pop()	// Note that the return type is T - the data type of ‘Data’  {    if(head==null)  // stack is empty      return null;       // stack non-empty. Return the 'Data' of the head    // and set the head to head.nextRef    T topData = head.Data;    head = head.nextRef;    return topData;  }  void display()	// The display function prints the stack from top to bottom  {    if(head==null)  // stack is empty    {      print("empty stack!");      return;    }    // Set a pointer 'curr' to the head    Node curr = head;    while(curr!=null)    {      print(curr.Data);   // print curr's data      curr = curr.nextRef;  // advance curr to the next Node    }  } Section 1.2: Queues Assume ‘front’ and ‘rear’ nodes exist with the ‘NextRef’ attributes pointing to the first and last nodes of the queue or being null if the queue is empty. This section describes the  Java style pseudo codes for the following 3 queue methods: enqueue(item) dequeue( ) display( ) void enqueue(T item)	// T is the datatype of the item  {     // create a new 'Node' called ‘newnode’    // with item as the 'Data' and null as its 'NextRef'    Node newnode = new Node(item, null);        if(front==null)  		// queue is empty. front = rear = null    {   front = newnode;		// set the newnode as the ‘front’   rear = newnode;		// set the newnode as the ‘rear’    }    else  // queue is not empty    {      rear.nextRef = newnode;	// enqueue to the rear of the queue	      rear = newnode;		// the newnode is the new rear    }  }  T dequeue()		// Note that the return type is T - the data type of ‘Data’  {    if(front==null)  	// queue is empty      return null;       // queue non-empty. Return the 'Data' of the head    // and set the front to front.nextRef    T frontData = front.Data;    front = front.nextRef;    return frontData;  } void display()	// The display function prints the queue front to rear  {    if(front==null)  // queue is empty    {      print("empty queue!");      return;    }    // Set a pointer 'curr' to the head    Node curr = front;    while(curr!=null)    {      print(curr.Data);   	// print curr's data      curr = curr.nextRef;  	// advance curr to the next Node    }  } Section 2: Heaps and Trees Assume that the hashtable is a simple array of size 8, with indices 0..7. Numeric keys are mapped by a hash function that gives the mod(8,n) value for any key n, yielding the hashtable index for that key. For instance, the hashtable index for 100 is (100 mod 8) = 4. A Hashtable entry is null unless a key exists with that index as its hashed index; if so, the Hashtable entry points to the first node of a linked list of keys with that hash index. The last node on this linked list has a null reference for the next referenced node. Like in the previous section, assume the occurrence of a linked list node is represented by the object “Node” and its “Data” and “NextRef” attributes. class  Node{ 	int Data;		// The data item of a node. 	Node NextRef;	// link to the next Node in the list } First, let us look at the structure of our hashtable. The hashtable is an array of size 8, each element of which is a ‘Node’, initialized to null. Node array[8];  // The hashtable of size 8. // Initially, the hashtable is empty. for(int i=0;i

Neha · Accepted Answer

Using binary tree for searching in array
The binary tree allows to Store the elements of arrays in a binary format and then we can perform their searching over it. The first step is to create a tree from the given list of arrays. The parent node of the tree will be present at the index I in the area and then the left child update mode will be present at the index (2*i +1) and the right child will be present at the index (2*i +2)  of the array.   This concept is very useful to insert the child into left and right nodes by selecting the parent move. the first element of the array will be inserted as the root node in the tree which will have level zero and then the array will be traversed. Every node present in the tree will have left and right child. 
As we know the left child of the parents will be smaller than 8 and the right child will be greater than the payment mode. While searching for a key if it does not match with the root node and it is less than the root node value then we will go for the left side of the tree and the whole right side elements will be ignore which will decrease the number of elements.

Key Assignment Draft: Include session changes The first two Individual Projects used linked lists for stacks, queues, and hashing implementations. With this task, searching performance with linked...

Answer To: Key Assignment Draft: Include session changes The first two Individual Projects used linked lists...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment