Please enable JavaScript.
Coggle requires JavaScript to display documents.
Java Data Structure - Coggle Diagram
Java Data Structure
BINARY SEARCH TREES
-
-
Trees (Graph Theory): Trees are well-known as a non-linear data structure. They don't store data in linear way. They organize data hierarchically.
Technical definition: A tree is collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node. The first node of the tree is called the root. If this root nose is connected by another node, the root is then a parent node and the connected node is a child.
Binary tree is specific tree in which each node has at the most two children. Left child is smaller than parent node. Right child is greater than the parent node. We can access the root node exclusively and all other nodes can be accessed via the root node.
The height of a tree is the number of edges on the longest downward path between the root and a leaf node.
-
-
The tree structure may became imbalanced which means the number of nodes significantly differ in the subtress.
It keeps the key in sorted order so that lookup and other operations can use the principle of binary search with O(logN) running time
each comparison allows the operations to skip over half of the tree, so that each operation takes time proportional to the logarithm of the number of items stored in the tree
this is much better than O(N) the linear time required to find items by key in unsorted array but slower than the corresponding operations on hash tables with O(1)
-
INSERT
left child is smaller than parent, and right child is gather than parent
REMOVING
- Removing a leaf node by setting it to NULL
- Removing a node with a single child: update parent that the left (or right) child has been changed
- Removing a node with two children: a) find the smallest item in the right subtree.
b) the largest item in the left subtree.
c) chose one and swap them and remove the leaf
-
PERFORMANCE
- Insertion: O(logN)(AC), O(N)(WC).
- Deletion: O(logN)(AC), O(N)(WC).
- Search: O(logN)(AC), O(N)(WC).
Hashtables
-
-
-
-
it stores key in array - to achieve random access, and this is why the keys must be unique to avoid using the same indexes
h(x) hash-function transforms the key into an index in the range [0, m-1] O(1) running time.
The h(x) hash-function defines the relationship between the keys and the array indexes
-
-
if we have integer keys we just have to use the modulo (%) operator to transform the number into the range [0, m-1]
-
Collisions
-
-
-
RESOLUTION
- Chaining - we store the items in the same bucket (with same indexes) in a linked list.
in worst-case hash-function puts all the items into the same bucket, so we end up with linked list with O(N) linear running time for most of the operations
- open addressing - if we come to the conclusion that there is a collision then we generate a new index for the item (try to find another bucket).
a) linear probing - if collision at index k then we try k+1 and so on until empty bucket.
b) quadratic probing - if collision happened at k then try (1, 4, 9, 16...)
c) rehashing - if collision happened at k then we use the h(x) hash-function again to generate a new index
Load factor
-
-
n/m, where n - actual items and m is size of array
-
in java when the load factor is > 0.75 then Java resize the hashtable automatically to avoid too many collisions
Dynamic Resizing
when resizing here is a problem all old items in the hashtable need to inserted with new hash functions and it takes O(N) linear running time - this may make dynamic-sized hash tables inappropriate for real-time applications
-
LINKED LISTS
-
-
It has node implementation, with head and tail node on the beginning and the end, respectively.
-
Every node stores the data itself and the reference the next node in the linked list data structures, this is why need more memory than arrays
-
-
OPERATIONS
-
insert/remove item to the end are O(N) running time, because finding last node is linear search, but operation after finding node is has low complexity O(1)
-
-
LinkedList in Java
implements interfaces such as: List, Deque, Serializable, Cloneable
-
-
-
-
ARRAYS
-
the items in an array are placed right next to each other in RAM. So we can get them with index help in O(1)
-
-
-
-
PERFORMANCE
-
When is full it allocate large space (usually 2x), after that they copy existing items to new array. Resizing is O(N)
-
Adding/Removing items to array with given index is O(N), because of shifting items
When searching and no index is known, the algorithm check the elements one by one until found, so called LINEAR SEARCH O(N)
Use array when you want to manipulate the last item of the data structure or you want to access items with known indexes
-
ALGORITHMS
-
Anagram Problem
- check if differed length.
- sort both arrays
- check if all elements are equal
AVL Trees
-
-
AVL trees are faster than red-black trees because they ate more rigidly(równoważnie) balanced but needs more work
AVL trees are rigidly balanced this is why O(logN) running time is guaranteed (it is fast a binary search tree can be)
-
after every insertion and removal operations we have to check whether the tree has become imbalanced or not
-
HEIGHT
height = max(left child's height, right child's height) +1
-
Rotations
Right rotation
Positive balance factors means left heavy situation so we have to make a right rotation to rebalance the tree
Left rotation
Negative balance factor means right heavy situation so we have to make a left rotation to rebalance the tree
Red-Black Trees
-
-
-
-
There are no 2 adjacent (sasiadujące, jako child or parent) red nodes
-
every path from a given node to any of its descendant(potomków) NULL nodes contains the same number of black nodes
-
B-Trees
-
Support operations as insertion, deletion, sequential access and searching in O(logN) time complexity
-
-
-
-
-
Stacks
-
-
basic operations are pop()(take and remove), push() and peek() (just take)
-
-
Queues
-
basic operations are enqueue(), dequeue() and peek()
-
-
-
-