Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorytms on Array, LinkedList, Trees, Sorting, Matrix, HashMap, Stack -…
Algorytms on Array
-
-
-
Fréquence Array
-
Bucket Sort by Frequency: Create a bucketList where each index corresponds to a frequency, and store elements in the appropriate bucket based on how often they appear.
We can convert Hashmap<Value, Integer_with_frequency> to sorted Array
-
-
-
-
LinkedList
-
it is better to use while rather than recursive approach - as I tried to use it a few times and failed
If reverse, can do this recursively, but need to remove link in the first node head.next = null.
overall - keep simple this tasks, make algorithm with a few steps - are fine. Like go thru the list -> than split it to two -> that merge two
-
Trees
Binary Search Tree
-
-
Order traversal
-
post order: left, right, X
In order traversal: left, X, right
Level-order Traversal: Visit nodes level by level, starting from the root and moving downwards.
in-order traversal
Successor
Definition: The successor of a node is the next node in the sequence that follows the given node, according to some traversal order or sequence.
Binary Search Tree (BST):
In an in-order traversal, the successor of a node is the node with the smallest key greater than the current node's key.
If the node has a right child, the successor is the leftmost node in the right subtree.
If the node does not have a right child, the successor is the lowest ancestor of the node whose left child is also an ancestor of the node.
-
Predecessor
Binary Search Tree (BST):
In an in-order traversal, the predecessor of a node is the node with the largest key smaller than the current node's key.
If the node has a left child, the predecessor is the rightmost node in the left subtree.
If the node does not have a left child, the predecessor is the lowest ancestor of the node whose right child is also an ancestor of the node.
-
Definition: The predecessor of a node is the previous node in the sequence that comes before the given node, according to some traversal order or sequence.
Delete Node in InOrder:
-
-
Algorytm:
-
-
-
If two nodes: 1) find smallest value in the right node and assign it to this node; - this is successor node
2) as now we have duplicate - need to find it. This is always node with at most one children - it has zero or only right children.
-
-
-
Characteristics
-
-
Horizontaly balanced
-
check - compare depth of left and right nodes and ensure, that depth is always <= Math.abs(1)
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
-
Sorting
Radix sort
-
-
-
-
-
Complexity:
Radix Sort is a linear sorting algorithm. Radix Sort's time complexity of O(nd), where n is the size of the array and d is the number of digits in the largest number. It is not an in-place sorting algorithm because it requires extra space.
- Sorting by last number
- only works for digits
Count sort
It is particularly efficient when the range of input values is small compared to the number of elements to be sorted.
The basic idea behind Counting Sort is to count the frequency of each distinct element in the input array and use that information to place the elements in their correct sorted positions.
-
Matrix
We can treat 2D matrix as 1D array:
Treat the 2D matrix as a 1D array, calculate the row (mid / length) and column (mid % length) to get the mid element.
We can also treat some blocks of matrix as additonal matrix with blocks, like matrix 9 on 9, we can imagine as matrix 3 on 3, and identify in this case - that some item in that block, means 0,0 - first 3 on 3 block
-
-