·
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. |
It’s basically a hierarchical data structure that is a collection of elements called nodes. |
It’s 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(1) – Stack / Queue |
|||||||||||||
Delete “Head” |
||||||||||||||
Delete “Tail” |
O(1) – Stack |
|||||||||||||
Search |
O(1) |
|||||||||||||
Linked List Traversal |
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 |
||||
Insertion |
O(1) Hopefully O(log n) |
|||
Deletion |
||||
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 |
||
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
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |