Data Structures to Learn (Ordered by Priority)

  1. Arrays
  2. Strings
  3. Hash Table
  4. Recursion
  5. Sorting/searching
  6. Matrix
  7. Linked List
  8. Queue
  9. Stack
  10. Tree
  11. Graph
  12. Heap
  13. Trie
  14. Interval
  15. Dynamic Programming
  16. Binary
  17. Math
  18. Geometry

Arrays

A type of data structure that stores more than one data item of the similar data type. It is a container of elements. Items of an array are allocated at adjacent memory locations.

Elements - Memory locations found in array.

Length - Total number of elements in an array.

NOTE:

To access a specific element of an array, you use its index/subscript.

Declaring an array: In python, you declare an array the following way:

arrName = array.array( 'i', [300,200,100] )

Where i is the data type (type code) and [300,200,100] are the elements of the array

In C++, you declare an array the following way:

int arrName[3] = {300,200,100};
Why Are Arrays Important/Useful?
  1. They can store multiple values in a single variable.
  2. Better at processing many values easily and quickly.
  3. Sorting and searching values are easy to do.
Difference Between Lists and Arrays in Python

In Python, a list can have different data types, whereas arrays can only have items of the same type.

Array Operations

For arrays, there are various operations:

  1. Insert - Inserting one or more elements into an array at the beginning, end, or any given index.
  2. Delete - Can delete an item from an array by value (value as in, removing the specified element in array).
  3. Search - Search an item in an array based by value.
  4. Traverse - Traversing through an array using a loop.

B Tree

It is a self-balancing data structure that follows a set of rules for searching, inserting, and deleting data in a faster and memory efficient way.

NOTE: Self-balancing means the height/depth of the left and right subtrees of any node differ by at most one.

Rules for B Tree
  1. All leaves are created at the same level.
  2. B Tree is determined by a number of degree, which is called the “order”
  3. Left subtree of the node will have lesser values than the right side of the subtree–nodes are sorted in ascending order from left to right (basically, an in-order traversal).
  4. For EVERY node, the maximum number of keys each node can have is: $m - 1$ For example, if $m = 4$, then the maximum number of children each node can have is $4$ and node can have at most $3$ keys.
  5. The minimum children a node can have is half of $m$, which is $m/2$ (the ceiling is taken).
  6. Every node, except for the root, MUST contain minimum keys of $[m/2]-1$

$m = 4$

            [30]
         /      \
      [10, 20]   [40, 50, 60]
     /   |   \       |    |    \
[5] [15] [25] [35] [45] [55] [65, 70]
Why use a B Tree?
  1. It reduces number of reads on the disk.
  2. They are optimized to adjust the number of children nodes according to disk size.
  3. It is designed for handling a bulky amount of data.
  4. Useful for databases and file systems.
  5. Useful for reading and writing large blocks of data.
How a B Tree Works in Memory

Index Tables are created that saves the record reference of records based on the blocks they reside in–this reduces time and memory consumption.

Operations of a B Tree
  1. Search
  2. Insert
  3. Delete
Search Operation

Steps to search:

  1. You have some value/key, $k$, be searched.
  2. Start searching from the root and recursively traverse down.
  3. If $k$ is less than root value, search the left subtree, else search the right.
  4. If $k$ is found within a node, simply return the node, else keep traversing down to the child with a greater key.
  5. If $k$ is not found in the tree, return NULL.
Insert Operation

Since a B Tree is self-balanced, you cannot just insert a key into any node.

Steps to insert:

  1. First search and find the appropriate place to insert the key.
  2. Once a proper location is found, insert the key at that location.
  3. If the proper location is found but the node has a maximum number of keys:
  • Then the node, along with the inserted key, will split from the middle element (the split will have each key be its own node).
  • The middle element will become the parent for the other two child nodes.
  • Nodes need to re-arrange keys in ascending order.

https://www.guru99.com/b-tree-example.html