DS

DS.ipynb

# Data Structure

## Introduction
* Data structure (is a way) or (are the special format/structures in computer memory) to store & organize the data. 
* To suit a specific purpose.
* So, that we can perform some operations on them like search, add, delete, insert

### Data Structure Vs Data Type

**Data Type**
* It is class of objects sharing certain properties.
* It is a premitive element of a particular language like C, C++, Java, Python, Go
* Have predefined characteristics according to the language
* Contains data/information without any semantic
* Can't be reduced anymore
* e.g. integer, float, character, string, boolean


**Data Structure**
* It is an abstract description of organization of data & operations on them
* It uses data types
* Can be decomposed to smaller
* DS are data type as well, but not a premitive type

**Abstract Data Type (ADT)**
* Its visualization, thought, logical description, or a picture of a new data type which we are going to create
* while DS is a real & concrete thing, we can directly use them

**DS is a super set and Data type is sub set or building block for DS**

## Types
#### Linear Data Structure
* Traverses the data elements sequentially
* only one data element can directly be reached

#### Non Linear Data Structure
* Every data item is attached to several other data items with a relationships
* The data items are not arranged in a sequential structure

1. Linear
    * [Array](#array)
    * Linked-list
        * Singly Linked List
        * Circular Linked List
        * Doubly Linked List
    * Stack
    * Queue
    * Hash
    * Matrix

2. Non-Linear
    * [Tree](#tree)
        * [Binary Tree](#binary-tree)
        * Binary Search Tree (BST)
            * Self Balancing BST
        * B-Tree
        * AVL Tree
        * Heap
            * Min/Max Heap
            * Fibbonacci Heap
        * Trie
    * Graph
        * Undirected
        * Directed
        * Weighted

### Array <a id="array"/>

### Linked List

### Stack

### Queue

### Hash

### Tree <a id="tree"/>
* **Desc:**
    * Are hierchical data structure
    * made up of nodes or vertices and edges without having any cycle
    * The tree with no nodes is called the null or empty tree
* **Terminologies:**
    * Root: The top node in a tree.
    * Child: A node directly connected to another node when moving away from the Root.
    * Parent: The converse notion of a child.
    * Siblings: A group of nodes with the same parent.
    * Descendant: A node reachable by repeated proceeding from parent to child.
    * Ancestor: A node reachable by repeated proceeding from child to parent.
    * Leaf: (less commonly called External node) A node with no children.
    * Branch: Internal node, A node with at least one child.
    * Degree: The number of subtrees of a node.
    * Edge: The connection between one node and another.
    * Path: A sequence of nodes and edges connecting a node with a descendant.
    * **Level**: The level of a node is defined by 1 + (the number of connections between the node and the root).
    * **Height of node**: The height of a node is the number of edges on the longest path between that node and a leaf.
    * Height of tree: The height of a tree is the height of its root node.
    * Depth: The depth of a node is the number of edges from the tree's root node to the node.
    * Forest: A forest is a set of n ≥ 0 disjoint trees.
* **Why:**
    * need to store in hierchical way, e.g. computer filesystem
    * provides quicker insertion/deletion than array but slower than unordered linked list
    * No upper limit on number of nodes (like linkedlist & unlike array)
* **Application:**    
    * Easy to search (using traversal)
    * Router Algorithm
    * decision making
    
#### Binary Tree <a id="binary-tree" />
* **Desc:**
    * tree whose each node have at most 2 children
    * children typically known as left and right child
* **Representation:**
    * a node consist of data, pointer to left child, pointer to right child
* **Travesal:**
    * In Order: left, root, right
    * Pre Order: root, left, right
    * Post Order: left, right, root
* **Operations:**
* **Properties:**
    * Level(Root) = 1, but height = 0 (don't get confuse)
    * Maximum number of nodes at level $ i = 2^{i-1}$ 
    * Level of a Node = Height of the Node + 1
    * Minimum Possible Height of a tree having N nodes: $h = \lfloor \log_2{(N+1)} \rfloor$
    
#### Binary Search Tree (BST)
* **Desc:**
* **Operations:**
    * SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE.   

#### Self Balancing Binary Tree

#### B-Tree
* **Desc:**
    * Generalization of BST i.e. a node can have more than 2 children
* **Application:**
    * Indexing in Databases
    * Filesystem

### Heap

### Trie


### Language Specific
1. Python
2. Java
3. C#