Write short notes संक्षिप्त नोट्स लिखिए a) Binary search बाइनरी खोज b) Heap sort हीप सॉर्ट c) Red Black tree रेड ब्लैक ट्री d) Stack स्टैक

Binary Search

Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.

If the search ends with the remaining half being empty, the target is not in the array.

Binary search is much more efficient than linear search, especially for large arrays. Linear search checks each element of the array in sequence until the target is found or the end of the array is reached, which takes O(n) time. Binary search, on the other hand, eliminates half of the array in each step, reducing the search time to O(log n).

Heap Sort

Heap sort is a sorting algorithm that uses a binary heap data structure to sort an array of elements. Heap sort is an in-place algorithm, meaning it operates directly on the input array, and it is not a stable algorithm, meaning the order of equal elements in the input array is not preserved.

Heap sort works by first building a binary heap from the input array. A binary heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. Once the binary heap is built, the largest element in the heap is at the root. This element is swapped with the last element in the heap, and the heap is rebuilt. This process is repeated until the entire array is sorted.

Heap sort has an average time complexity of O(n log n) and a worst-case time complexity of O(n^2).

Red Black Tree

A red-black tree is a self-balancing binary search tree that maintains the following properties:

1. Every node is either red or black.
2. The root is always black.
3. Every red node has two black children.
4. Every path from a node to a descendant leaf contains the same number of black nodes.

Red-black trees are used to implement sets and maps in many programming languages and libraries. Red-black trees have a worst-case time complexity of O(log n) for search, insertion, and deletion operations.

Stack

A stack is a linear data structure that follows the last-in-first-out (LIFO) principle. This means that the last element added to the stack is the first element to be removed. Stacks are implemented using an array or a linked list.

Stacks are used in many applications, such as:

• Managing function calls in a program
• Evaluating expressions in a programming language
• Implementing a depth-first search algorithm