Data Structures and Algorithms Programs

Overview

This repository contains a set of standalone C++ programs that implement classic data structures and algorithms. Each program reads input from standard input and writes results to standard output, making them suitable for coursework, lab evaluation, or automated grading.

Contents

• program-1.cpp: Threaded Binary Tree (TBT) creation and inorder traversal.
• program-2.cpp: Threaded Binary Tree (TBT) creation and preorder traversal.
• program-3.cpp: AVL tree insertion with inorder traversal output.
• program-4.cpp: Priority queue (max-heap) using the C++ standard library.
• program-5.cpp: Trie (prefix tree) insertion and search for lowercase strings.
• program-6.cpp: Randomized quicksort for integer arrays.
• program-7.cpp: Treap insertion with inorder traversal output.
• program-8.cpp: Skip list insertion and linear display of level 0.

Build

Use a C++ compiler that supports at least C++11.

g++ -std=c++11 -O2 -Wall -Wextra -pedantic program-1.cpp -o program-1

Repeat for any other program you want to run.

Run

All programs read from standard input and print to standard output.

Example:

./program-6

Input and Output Conventions

Most programs follow this pattern:

• Input: an integer n followed by n values (integers or strings).
• Output: a traversal or sorted/processed sequence.

Program-specific notes:

• program-1.cpp (TBT inorder): outputs inorder traversal of the threaded BST.
• program-2.cpp (TBT preorder): outputs preorder traversal of the threaded BST.
• program-3.cpp (AVL): outputs inorder traversal of the balanced BST.
• program-4.cpp (Priority queue): outputs elements in descending order.
• program-5.cpp (Trie): outputs "Found" or "Not Found" for a query string.
• program-6.cpp (Randomized quicksort): outputs the array in nondecreasing order.
• program-7.cpp (Treap): outputs inorder traversal of the treap.
• program-8.cpp (Skip list): outputs the elements in ascending order (level 0).

Algorithmic Notes

• Threaded BST (TBT): provides traversal without recursion or an explicit stack by using threads for null pointers.
• AVL Tree: maintains height balance via rotations, guaranteeing logarithmic search and insertion.
• Priority Queue: uses a max-heap as implemented by the C++ standard library.
• Trie: supports efficient prefix-based insert and search for lowercase English strings.
• Randomized Quicksort: uses random pivot selection to reduce worst-case behavior.
• Treap: combines BST ordering with heap-based random priorities to maintain balance.
• Skip List: uses probabilistic levels for expected logarithmic search and insertion.

Complexity Summary (Typical)

• TBT insertion: O(h) where h is tree height.
• TBT traversal: O(n).
• AVL insertion: O(log n).
• Priority queue insertion: O(log n); top/pop: O(log n).
• Trie insertion/search: O(L) where L is key length.
• Randomized quicksort: expected O(n log n).
• Treap insertion: expected O(log n).
• Skip list insertion: expected O(log n).

Notes

• All programs are self-contained and do not share code.
• Inputs are assumed to be valid and within typical classroom constraints.