### Arrays

Arrays

#### Array Limitation #1

All data in an array must be of the same type

• An integer array must only contain integers.
• A string array must only contain strings.

We know two facts about arrays:

• Elements are all the same type.
• The size (number of bytes) of the type of data is known.

We can calculate the offset to any given index from the start of the array:

#### Array Limitation #2

Arrays have a fixed capacity.

• Arrays must store their data sequentially in memory.
• The capacity of an array is the maximum number of elements that can be stored.
• The size of an array is the current number of elements stored in the array.

The only way to add another element is to allocate a new, larger array and copy over all of the data

### std::vector

The std::vector implements an array that dynamically grows in size automatically. However, all properties remain true:

• Array elements are a fixed data type.
• At any given point, the array has a fixed capacity.
• The array must be expanded when the capacity is reached.

A list node refers to pair of both the data and the link. Zero or more ListNode elements linked together form a Linked List.

• A pointer called the “head pointer” stores the link to the beginning of the list.
• A pointer to NULL (Ø) marks the end of the list.

List.h

List.cpp

#### List Capacity

In a list, the time it takes to access a given index grows based on the size of the list.(In contrast, an array can access any element in a constant, fixed amount of time. Therefore, for accessing a given index, an array is faster than a list.)

• A basic linked memory structure is a Linked List, which consists of zero or more ListNodes lined together and a head pointer.
• A linked list provides a flexible alternative to an array.

### Array and List Operations

Arrays and Lists are both ordered collections of data. There are several key operations common to both all ordered collections that are worth analyzing.

Array and List
1. Objective: Access a given index in the collection.
• Array: O(1)
• List: O(n)
2. Objective: Insert an element at the front
• Array: O(1) (Amortized constant time when array size is doubled when copied)
• List: O(1)
3. Objective: Given data, find the location of that data in the collection.
• Unsorted Array: O(n)
• Sorted Array: O( lg(n) )
• List: O(n)
4. Objective: Given an element (array index), insert a new element immediately afterwards.
• Array: O(n)
• List: O(1)
5. Objective: Given an element (ListNode or index), delete the element immediately afterwards.
• Array: O(n)
• List: O(1)

### Queue (Data Structure)

A queue is a first-in first-out data structure that is similar to waiting in a line or queue.

A structure’s Abstract Data Type (ADT) is how data interacts with the structure. An ADT is not an implementation, it is a description.

• create : Creates an empty queue
• push : Adds data to the back of the queue
• pop : Removes data from the front of the queue empty è Returns true if the queue is empty
• empty : Returns true if the queue is empty

A queue may be implemented with an array or a doubly-linked list. Both an array-based and a list-based implementation can be built to run in constant, O(1) running time.

Queue

### Stack (Data Structure)

A stack is a last-in first-out data structure that is similar to a pile (stack) of papers.

• create : Creates an empty stack
• push : Adds data to the top of the stack
• pop : Removes data from the top of the stack
• empty : Returns true if the stack is empty

A stack may be implemented with an array or a linked list. Both an array-based and a list-based implementation can be built to run in constant, O(1) running time.

Stack

### Tree

Tree

#### Terminology

Most ancestry terms apply as expected:

• Sibling
B and D are siblings.
• Ancestor
M, L, and D share A as a common ancestor.
• Grandchild / grandchildren
M is a D’s grandchild.
• Grandparent
D is M’s grandparent.

• Trees formed with nodes and edges.

• Trees must be rooted, directed, and acyclic.
• The relationship between nodes in a tree follow classical ancestry terms (parent, child, etc).

#### Property

• The height of a binary tree is the number of edges in the longest path from the root to a leaf.
• A binary tree is full if and only if every node has either zero children or two children.
• A binary tree is perfect if and only if all interior nodes have two children and leaves are at the same level.
• A binary tree is complete if and only if the tree is perfect up until the last level and all leaf nodes on the last level are pushed to the left.

### Binary Search Tree

A binary search tree (BST) is an ordered binary tree capable of being used as a search structure:

BST

A binary tree is a BST if for every node in the tree:

• Nodes in the left subtree are less than itself.
• Nodes in the right subtree are greater than itself.

• find : Finds the data associated with a key in the dictionary
• insert : Adds a key/data pair to the dictionary
• remove : Removes a key from the dictionary
• empty Returns true if the dictionary is empty

BST-Based Dictionary

BST Dictionary

#### In-Order Predecessor (IOP):

The in-order predecessor is the previous node in an in-order traversal of a BST. The IOP of a node will always be the right-most node in
the node’s left sub-tree.

#### BST::remove

• Zero children: Simple, delete the node.
• One child: Simple, works like a linked list.
• Two children:
• Find the IOP of the node to be removed.
• Swap with the IOP.
• Remove the node in it’s new position.

#### BST Analysis

• There are n! different ways to create BSTs with the same data.
• The worst-case BST will have a height proportional to the number of nodes.
• An average BST will have a height proportional to the logarithm of the number of nodes.
• Using a height balance factor, we can formalize if a given BST is balanced.

### Balanced BST

Balanced BSTs are height-balanced trees that ensures nearly half of the data is
located in each subtree:

#### BST Rotations

https://zhangruochi.com/AVL-Tree/2019/09/15/

BST Dictionary
• BST rotations restore the balance property to a tree after an insert causes a BST to be out of balance.
• Four possible rotations: L, R, LR, RL
– Rotations are local operations.
– Rotations do not impact the broader tree.
– Rotations run in O(1) time.’

### B tree

https://www.cnblogs.com/nullzx/p/8729425.html

#### B-Tree Properties

For a B-tree “of order m”:

1. All keys within a node are in sorted order.
2. Each node contains no more than m-1 keys.
3. Each internal node has exactly one more child than key(at most m children, so a B-tree of order m is like an m-way tree).
• A root node can be a leaf or have [2, m] children.
• Each non-root, internal node has [ceil(m/2), m] children.
4. All leaves are on the same level.

#### B-Tree Insert

• 根据要插入的key的值，找到叶子结点并插入。
• 判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
• 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

Use can use the binary search ti replace the linear seach. But it is not important because the process of comsuming most time is _fetchChild.

### Heap

(min)Heap: A complete binary tree T is a min-heap if:

• T={} or
• T = {r, $T_L$, $T_R$}, where r is less than the roots of {$T_L$, $T_R$} and {$T_L$, $T_R$} are min-heaps.

#### Build heap

1. Sort the array–it’s a heap!
2. heapifyUp

3. heapifyDown

Donate article here