Computer science
·Binary Tree
Data Associations look like a tree
A node orientation that has A Parent/Root and Left / Right relationship
· Describe the Node structure for Binary Tree
· Root / Root Node
Node that is the beginning of the tree
· Path/Edge
· Parent
A node that has nodes associated with it.
Left and Right Node
· Children
Nodes connected to a parent node
· Leaf
Online Resource 1 , 2 , 3
· Binary Search Tree
Tree Structure where the nodes are Sorted or Inserted in a particular relationship to the previous node.
Traverse ? Access all THE NODES
Inorder
Post Order
https://algorithmtutor.com/Data-Structures/Tree/Binary-Search-Trees/
· Right Child
HAs a greater value than the Parent or root Node
· Left Child
Has a lesser value than the Parent or root Node
· Difference between Binary Tree and Binary Search Tree
Binary Tree
Binary Search Tree
Binary Tree is a specialized form of tree which represents hierarchical data in a tree structure.
Binary Search Tree is a type of binary tree which keeps the keys in a sorted order for fast lookup.
Each node must have at the most two child nodes with each node being connected from exactly one other node by a directed edge.
The value of the nodes in the left subtree are less than or equal to the value of the root node, and the nodes to the right subtree have values greater than or equal to the value of the root node.
There is no relative order to how the nodes should be organized.
It follows a definitive order to how the nodes should be organized in a tree.
Its basically a hierarchical data structure that is a collection of elements called nodes.
Its a variant of the binary tree in which the nodes are arranged in a relative order.
It is used for fast and efficient lookup of data and information in a tree structure.
It is mainly used for insertion, deletion, and searching of elements.
· Why does the Binary Tree / Binary Search Tree implementation improve the Linked List?
? Binary search tree can cut in half each node, just like binary search
? Linked list are more like linear search where you have to traversal each element on by one
How is recursion utilized to traverse a Binary Search Tree?
? Recursion – function can call itself to repeat code block
? Similar to a loop
TIME COMPLEXITY ANALYSIS
Efficiency of the algorithm
Stack – LIFO
Queue – FIFO
Map or Tree
Doubly Linked List
Node
next*
previous*
WORST CASE
AVERAGE CASE
BEST CASE
Insert Head
O(n)
O(1) – Queue
Insert Tail
O(n)
O(1) – Stack / Queue
Delete Head
O(n)
O(1) – Queue
Delete Tail
O(n)
O(1) – Stack
Search
O(n)
O(1)
Linked List Traversal
O(n)
Trade – Off for the map
Bad ? Takes more Memory because need an over sized array to avoid collision |
We gain Search Speed ? In map we get almost O(1) for any element Structure
Hash Map
WORST CASE
AVERAGE CASE
BEST CASE
Insertion
O(n)
O(1) Hopefully
O(log n)
Deletion
O(n)
O(1) Hopefully
O(log n)
Search
O(n)
O(1) Hopefully
O(log n)
Linked List allows for Better Dynamic Allocation. No size Limit the linked lists. Ours can add and remove nodes to have constant alignment between data and its storage RAM.
Nodes are placed HEAP
Doubly List ? Linear Data Structure + No Indices
Binary Search Tree
Node
left* ? Nodes with lesses value are placed on the left
right* ? Nodes with greeted value are placed on the right
WORST CASE
AVERAGE CASE
BEST CASE
Insertion
O(n)
O(log n)
O(1)
Deletion
O(n)
O(log n)
O(1)
Search
O(n)
O(log n)
O(1)
MEMORY ALLOCATION ANALYSIS
Linked List (Doubly / Singly)
O(n)
Hash Map
O(n^2) or (n^3)
Binary Search Tree
O(n)
· Please compare the Trade-Offs Associated with implementing Binary Search Tree v Hash Map?
Analyze Legacy Code of Hash Map w/ Collisions resolved w/ Embedded Linked Lists
Slide2.PNG
Slide3.PNG
A
B
C
D
E
F
G
H
I
J
K
L
M
N
Applied Sciences
Architecture and Design
Biology
Business & Finance
Chemistry
Computer Science
Geography
Geology
Education
Engineering
English
Environmental science
Spanish
Government
History
Human Resource Management
Information Systems
Law
Literature
Mathematics
Nursing
Physics
Political Science
Psychology
Reading
Science
Social Science
Home
Blog
Archive
Essay
Reviews
Contact
google+twitterfacebook
Copyright © 2019 HomeworkMarket.comHOMEWORKMARKET.COM YOUR HOMEWORK ANSWERSHomeworkMarket
chat0
Home.Homework Answers.
Help.
Log in / Sign up
Computer science
profile
RiverFlowsInYou
TreeBinarySearchTreeMapvTree.docx
Home>Computer Science homework help>Computer science
· Binary Tree
Data Associations look like a tree
A node orientation that has A Parent/Root and Left / Right relationship
· Describe the Node structure for Binary Tree
· Root / Root Node
Node that is the beginning of the tree
· Path/Edge
· Parent
A node that has nodes associated with it.
Left and Right Node
· Children
Nodes connected to a parent node
· Leaf
Online Resource 1 , 2 , 3
· Binary Search Tree
Tree Structure where the nodes are Sorted or Inserted in a particular relationship to the previous node.
Traverse ? Access all THE NODES
Inorder
Post Order
https://algorithmtutor.com/Data-Structures/Tree/Binary-Search-Trees/
· Right Child
HAs a greater value than the Parent or root Node
· Left Child
Has a lesser value than the Parent or root Node
· Difference between Binary Tree and Binary Search Tree
Binary Tree
Binary Search Tree
Binary Tree is a specialized form of tree which represents hierarchical data in a tree structure.
Binary Search Tree is a type of binary tree which keeps the keys in a sorted order for fast lookup.
Each node must have at the most two child nodes with each node being connected from exactly one other node by a directed edge.
The value of the nodes in the left subtree are less than or equal to the value of the root node, and the nodes to the right subtree have values greater than or equal to the value of the root node.
There is no relative order to how the nodes should be organized.
It follows a definitive order to how the nodes should be organized in a tree.
Its basically a hierarchical data structure that is a collection of elements called nodes.
Its a variant of the binary tree in which the nodes are arranged in a relative order.
It is used for fast and efficient lookup of data and information in a tree structure.
It is mainly used for insertion, deletion, and searching of elements.
· Why does the Binary Tree / Binary Search Tree implementation improve the Linked List?
? Binary search tree can cut in half each node, just like binary search
? Linked list are more like linear search where you have to traversal each element on by one
How is recursion utilized to traverse a Binary Search Tree?
? Recursion – function can call itself to repeat code block
? Similar to a loop
TIME COMPLEXITY ANALYSIS
Efficiency of the algorithm
Stack – LIFO
Queue – FIFO
Map or Tree
Doubly Linked List
Node
next*
previous*
WORST CASE
AVERAGE CASE
BEST CASE
Insert Head
O(n)
O(1) – Queue
Insert Tail
O(n)
O(1) – Stack / Queue
Delete Head
O(n)
O(1) – Queue
Delete Tail
O(n)
O(1) – Stack
Search
O(n)
O(1)
Linked List Traversal
O(n)
Trade – Off for the map
Bad ? Takes more Memory because need an over sized array to avoid collision |
We gain Search Speed ? In map we get almost O(1) for any element Structure
Hash Map
WORST CASE
AVERAGE CASE
BEST CASE
Insertion
O(n)
O(1) Hopefully
O(log n)
Deletion
O(n)
O(1) Hopefully
O(log n)
Search
O(n)
O(1) Hopefully
O(log n)
Linked List allows for Better Dynamic Allocation. No size Limit the linked lists. Ours can add and remove nodes to have constant alignment between data and its storage RAM.
Nodes are placed HEAP
Doubly List ? Linear Data Structure + No Indices
Binary Search Tree
Node
left* ? Nodes with lesses value are placed on the left
right* ? Nodes with greeted value are placed on the right
WORST CASE
AVERAGE CASE
BEST CASE
Insertion
O(n)
O(log n)
O(1)
Deletion
O(n)
O(log n)
O(1)
Search
O(n)
O(log n)
O(1)
MEMORY ALLOCATION ANALYSIS
Linked List (Doubly / Singly)
O(n)
Hash Map
O(n^2) or (n^3)
Binary Search Tree
O(n)
· Please compare the Trade-Offs Associated with implementing Binary Search Tree v Hash Map?
Analyze Legacy Code of Hash Map w/ Collisions resolved w/ Embedded Linked Lists
Slide2.PNG
Slide3.PNG
A
B
C
D
E
F
G
H
I
J
K
L
M
N
Applied Sciences
Architecture and Design
Biology
Business & Finance
Chemistry
Computer Science
Geography
Geology
Education
Engineering
English
Environmental science
Spanish
Government
History
Human Resource Management
Information Systems
Law
Literature
Mathematics
Nursing
Physics
Political Science
Psychology
Reading
Science
Social Science
Home
Blog
Archive
Essay
Reviews
Contact
google+twitterfacebook
Copyright © 2019 HomeworkMarket.com
