SUBMITTED BY:

BURHAN KHAN
SUBMITTED TO:
MAM TAHREEM
REG NO:
FA21-BCS-216
SUBJECT:
DSA
QUESTION 1
i. AVL Tree
Self-balancing binary search trees known as AVL trees have left and right subtree heights that
deviate by no more than one for each node. This balancing characteristic enables both efficient
operations and a balanced tree structure.
Insertion
 Start at the root and traverse the tree to find the appropriate position for the new node
based on its value.
 Perform a standard binary search tree insertion by comparing the value of the new node
with the current node and going left or right accordingly.
 After inserting the new node, check the balance factor of each node encountered during
the traversal. The balance factor of a node is defined as the difference between the
heights of its left and right subtrees.

To restore balance, perform the necessary rotations on the unbalanced nodes.

Left-Left (LL) Rotation: If the balance factor of the node is greater than 1 and the
new node is inserted in the left subtree of the left child, perform a right rotation.

Right-Right (RR) Rotation: If the balance factor of the node is less than -1 and
the new node is inserted in the right subtree of the right child, perform a left
rotation.
Left-Right (LR) Rotation: If the balance factor of the node is greater than 1 and
the new node is inserted in the right subtree of the left child, perform a left
rotation followed by a right rotation.
Right-Left (RL) Rotation: If the balance factor of the node is less than -1 and the
new node is inserted in the left subtree of the right child, perform a right rotation
followed by a left rotation.
Deletion
 Start at the root and traverse the tree to find the node to be deleted based on its value.
 Perform a standard binary search tree deletion by considering different cases:

If the node has no children, simply remove it.

If the node has one child, replace the node with its child.
If the node has two children, find either the predecessor or successor node, swap
their values with the node to be deleted, and then delete the
predecessor/successor node (which will have at most one child).
 After deleting the node, check the balance factor of each node
encountered during the traversal. If the balance factor of any node
becomes greater than 1 or less than -1, the tree has become unbalanced.

 Restore balance by performing rotations, similar to the insertion process,

on the unbalanced nodes.
ii. B-tree
B-trees are self-balancing search trees that are commonly used in databases and file
systems. They are designed to efficiently handle large amounts of data by minimizing the
number of disk accesses required for operations. B-trees have the following properties:

 Every node can have multiple children.

 Each node, except the root, has a minimum and maximum number of keys it can hold.
 All leaves are at the same level.
Insertion
 Start at the root and traverse the tree to find the appropriate leaf node where the new key
should be inserted.
 If the leaf node has space to accommodate the new key, insert it in the correct position
while maintaining the order of keys.
 If the leaf node is full, split it into two by moving the middle key to the parent node. The
left half of the keys remains in the original node, and the right half goes to a new node.
 If the parent node becomes full after the split, recursively split the parent node as well.
 Repeat this process until a suitable leaf node with space is found.
 If the root node splits, create a new root node and update the tree's structure accordingly.
Deletion
 Start at the root and traverse the tree to find the node containing the key to be deleted.
 If the key is found in a leaf node, remove it from the node.
 If the key is found in an internal node, replace it with its predecessor or successor, and
recursively delete the predecessor or successor from the appropriate child node.

 If the node from which the key is removed falls below the minimum number of keys,
perform rebalancing steps:
Borrow a key from a sibling node (left or right) if the sibling has more than the
minimum number of keys.
If both siblings have only the minimum number of keys, merge the node with one
of its siblings, reducing the height of the tree.
Update the parent node accordingly and repeat the rebalancing process if
necessary.

QUESTION 2
HASHING
Hashing is a technique used in computer science to map data of arbitrary size to a
fixed-size value. It is commonly used for efficient storage and retrieval of data in
data structures called hash tables. Hashing involves using a hash function to
convert the input data into a unique hash code or hash value.
HASH TABLE
Hash tables are data structures that provide fast insertion, deletion, and retrieval
operations, using an array of buckets or slots to store key-value pairs. The hash
code determines the index of the bucket where the value will be stored.
HASH FUNCTION
A hash function takes an input (such as a string, number, or object) and produces
a fixed-size output, typically a hash code. The key properties of a good hash
function are:
 Deterministic: For the same input, the hash function should always
produce the same output.
 Uniformity: The hash function should distribute the inputs uniformly
across the range of possible hash values.
 Efficiency: The hash function should be computationally efficient to
calculate.
Two strategies for avoiding and resolving collisions in hashing.
 Separate Chaining.
 Open Addressing.