Note : Please complete the work before published it. And Use C++ programming lan

Question

Note : Please complete the work before published it. And Use C++ programming language. And there is no need to write the code Just explain the codes which is already given.

For example, what is Going on at 'A', B C D ..... so on.

::CIS 27 Spring 2017:: Assignment 22 Binary Search Tree Analysis

Define:

TIME COMPLEXITY ANALYSIS

Binary Search Tree

WORST CASE

AVERAGE CASE

BEST CASE

Binary Time Complexity Analysis - For Information Purposes

Number of Elements

Number of Comparisons

15

31

63

127

255

511

1023

1 million

4

5

6

7

8

9

19

20

MEMORY ALLOCATION ANALYSIS BINARY TREE

How much memory will a BINARY TREE occupy?

Which segment of RAM memory will a BINARY TREE be placed in?

LAB ASSIGNMENT

A

B

C

D

E

F

G

H

I

Binary Search Tree

WORST CASE

AVERAGE CASE

BEST CASE

E struct node int data; struct node left struct node right; El struct node NewNode (int data t struct node node ne (struct node) "new" is like malloc node data data node left NULL node right NULL return (node static int lookup( struct node node int target) t E 1. Base case empty tree in that case, the target is not found so return false if (node NULL) return (false); else 2. see if found here if target node data) return (true); else 3. otherwise recur down the correct subtree if node data) return (lookup( node- left target target else return (lookup( node right, target struct node insert (struct node node int data f 1. If the tree is empty return a new, single node if (node NULL) to return (NewNode data else 2. Otherwise recur down the tree if (data node data) node- left insert node- left, data else node-right insert( data return node return the unchanged) node pointer

Explanation / Answer

BST during a Search Operation

Worst Case : Since BST is not balanced tree it might happen the tree is skewed so Worst case time Complexity is O(n)
Best Case : Its O(1) found instantaneously
Average Case : Since BST is not balanced tree it might happen the tree is skewed so Average is sum of Best and Worst divided by 2, So Average case time Complexity is O(n)


============
A : Its a self referential structure conatining two left and right pointers and represnets the NODE structure of Binary Search Tree.

B : Its newNode method that created a NEWNODE by allocating memory of size as the structure and assigns value to the new node and make the left and right pointer as NULL and returns the newNode created.

C: We try to look up the data in Our created tree, We find that if tree is NULL means ou data does not exists. Look up begins in a way such that if the data is found in root passed we return true, Otherwise we check if the element is more than the node, If yes we move to the node right otherwise we move to its left

D : Insertion is done based on BST property i.e if the newNode element is more than the node we move to its right and insert , similarly is the newNode is less then the node encountered during insert we move to its left .This is done recursively until we reach the leaf node and insert it there.


E : Root node is created with value 2 , Its left child is 1 and right child is 3 and newNode is called 3 times

F: : SAME as E , Root node is created with value 2 , Its left child is 1 and right child is 3 and newNode is called 3 times

G :It also created the same tree as E and F but doe it using our insert method that follows BST property during insertion i.e 1 is left child of 2 and 3 is right child of root 2

H : Its find sout the number of elements in Tree. If root is null return 0 otherwise recurse . in left and right subtree and count the number of nodes

I : PRINTS the tree in INORDER manner i.e Left root right and sorted order is printed for BST

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.