DCSN04C mid term

Searching

The process of locating a specific record with a particular key value.

LINEAR SEARCH (SEQUENTIAL SEARCH)

A method that checks each element one by one

Brute Force Approach

• No shortcut

• No assumption about order

• Just scan everything

Linear search

is SIMPLE but becomes SLOW as data grows.

BINARY SEARCH

a searching method that divides the data into halves repeatedly

Divide and Conquer

• Instead of checking ALL elements

• It eliminates half of the data each step

Binary search

is FAST but requires preparation (sorting)

BIG-O COMPLEXITY

Measures how operations scale as input size increases.

• Focus is NOT exact time

• Focus is growth behavior

Linear Search

None

Iterative

O(n)

Easy

Binary Search

Must be sorted

Divide & Conquer

O(log n)

Complex

BIG-O NOTATION

measures how fast an algorithm grows as input increases.

tree structure

• Data can be stored in different forms

• Efficiency depends on how we structure and access it

“Same data, different structure = different performance.”

BINARY SEARCH TREE (BST)

Fundamental Rule

Left child ≤ Parent ≤ Right child

organizes data for fast searching

TREE OPERATIONS (TRAVERSAL & SEARCH)

Inorder Traversal

Search

Min/Max

Inorder Traversal

• Left → Root → Right

• Output is sorted

Search

Compare and move left/right

Min/Max

Go extreme left/right

Binary Search Tree (BST) Search

A tree-based search where:

• Left child < Parent

• Right child > Parent

Sorting

arranging data in order (ascending/descending)

SIMPLE SORTING ALGORITHMS

Bubble Sort

Selection Sort

Insertion Sort

Bubble Sort

repeatedly swaps adjacent elements

Steps:

1. Compare adjacent elements

2. Swap if wrong order

3. Repeat

Selection Sort

finds the smallest element and places it in correct position

Steps:

1. Find minimum

2. Swap with first element

3. Repeat

Insertion Sort

builds sorted list one element at a time

Steps:

1. Take one element

2. Insert into correct position

EFFICIENT SORTING ALGORITHMS

Merge Sort

Quick Sort

Heap Sort

Merge Sort

Divide and conquer

Steps:

1. Divide array

2. Sort each part

3. Merge

Quick Sort

Uses pivot element

Steps:

1. Choose pivot

2. Partition

3. Recursively sort

Heap Sort

Uses heap data structure

TREE DATA STRUCTURES

• Root

• Parent / Child

• Leaf

• Height

In-order

Left → Root → Right

Pre-order

Root → Left → Right

Post-order

Left → Right → Root

Tree Traversal

In-order

Pre-order

Post-order

AVL Trees

Self-balancing BST

Key Idea:

• Balance factor = -1, 0, 1

Red-Black Trees

Balanced tree with rules:

1. Nodes are red or black

2. Root is black

3. No two red nodes adjacent

B-Trees & B+ Trees

Used in:

• Databases

• File systems

Key Idea:

• Multi-level indexing

• Efficient disk access

AVL Trees

are self-balancing Binary Search Trees. They automatically adjust themselves

to keep the height minimal, ensuring fast operations.

is a Binary Search Tree where the difference in height between the left

and right subtree (called the balance factor) is at most -1, 0, or +1.

RED-BLACK TREES

is also a self-balancing BST, but instead of strict balancing

it uses color rules to maintain balance.

is a Binary Search Tree where:

1. Each node is either Red or Black

2. The root is always Black

3. No two consecutive Red nodes

4. Every path has the same number of Black nodes

B-TREES

are multi-level, multi-child trees used in databases and file systems to handle

large amounts of data efficiently.

is a self-balancing tree where each node can have multiple keys and children,

designed to minimize disk reads.

B+ TREES

An improved version of B-Trees where all data is stored in leaf nodes, and leaves are

connected.

is a type of B-Tree where:

• Internal nodes store only keys (indexing)

• All actual data is stored in leaf nodes

• Leaf nodes are linked for fast traversal

AVL Tree

Strictly balanced

Fast searching

Red-Black Tree

Balanced with rules

Frequent insert/delete

B-Tree

Multi-children nodes

Databases

B+ Tree

Data in leaves only

Large systems & indexing

O(1)

Fastest

Constant

O(log n)

Fast

Dividing

O(n)

Normal

One-by-one

O(n²)

Slow

Nested loops

Bubble

O(n²)

Very slow

Selection

O(n²)

Simple

Insertion

O(n²)

Good for small

Merge

O(n log n)

Needs memory

Quick

O(n log n)

Fast in practice

Heap

O(n log n)

Efficient

Tree

tree is a finite nonempty set of elements.

It is an abstract model of a hierarchical structure.

consists of nodes with a parent-child relation.

Applications:

Organization charts

File systems

Programming environments

Root

node without parent (A)

Siblings

nodes share the same parent

Internal node

node with at least one child

External node (leaf )

node without children

Ancestors

parent, grandparent, grand-grandparent, etc of a node

Descendant

child, grandchild, grand-grandchild, etc of a node

Depth

number of ancestors

Height

maximum depth of any node (3)

Degree (node)

the number of its children

Degree (tree)

the maximum number of its node.

Subtree

tree consisting of a node and its descendants

Tree ADT

We use positions to abstract nodes

Generic methods of TREE ADT

integer size()

boolean isEmpty()

objectIterator elements()

positionIterator positions()

Accessor methods of TREE ADT

position root()

position parent(p)

positionIterator children(p)

Query methods of TREE ADT

boolean isInternal(p)

boolean isExternal(p)

boolean isRoot(p)

Update methods of TREE ADT

swapElements(p, q)

object replaceElement(p, o)

object

useful information

M

root of tree

Binary Tree

is a tree with the following properties:

• Each internal node has at most two children (degree of two)

• The children of a node are an ordered pair

We call the children of an internal node left child and right child

Alternative recursive definition: a binary tree is either

• a tree consisting of a single node, OR

• a tree whose root has an ordered pair of children, each of which is a binary tree

node

is represented by an object storing

Element

Parent node

Sequence of children nodes

Arithmetic Expression Tree

Binary tree associated with an arithmetic expression

internal nodes: operators

external nodes: operands

IN-order Traversal

a node is visited first going to its ancestor then on its sibling

Preorder Traversal

A traversal visits the nodes of a tree in a systematic manner

a node is visited before its descendants

Postorder Traversal

a node is visited after its descendants

Two Dimensional Array

It is an array of an array

Also called as tables or matrices

Row

first dimension of 2d array

Column

second dimension of 2d array

Curly braces

is the alternative constructor for 2D arrays

brackets

Declaration and instantiation of 2D array similar to that of 1D array

MATRIX

is a mathematical object which arises in many physical problems

Consists of m rows and n columns

m x n (read as m by n) is written to designate a matrix with m rows and n columns

LINEAR SEARCH

Checks every element of a list one at a time in sequence

Also called sequential search

Interpolation Search

is an improved version of binary search, especially suitable for large and uniformly distributed arrays. It calculates the probable position of the target value based on the value of the key and the range of the search space.

Jump Search

is another searching algorithm suitable for sorted arrays. It jumps ahead by a fixed number of steps and then performs a linear search in the smaller range.

an efficient searching algorithm for sorted arrays that balances the simplicity of Linear Search with the performance of Binary Search

Jump Search

works by skipping a fixed number of elements (jumping) and then performing a linear search within a specific block.

Time complexity

how long a task takes as the data increases

Space complexity

how much memory or space is needed