AVL Tree Implementation and Experimental Analysis

This repository showcases the implementation and performance evaluation of an AVL Tree-based list.

Overview

The project is divided into two main parts:

1. Practical Implementation: A Python-based implementation of an AVL Tree-based list, supporting typical list operations like insertion, deletion, search, and more.
2. Theoretical and Experimental Analysis: Performance evaluation of AVL trees in comparison to linked lists and arrays, based on various operations like:
   • Insertion at the beginning, end, or random positions.
   • Deletion and rebalancing analysis.
   • Sorting and permutation operations.

Key Features

• AVL Tree Implementation:

  • Supports operations such as insert, delete, retrieve, sort, concat, and permutation.
  • Maintains balance for efficient operations with worst-case time complexity of O(log n).

• Performance Analysis:

  • Compares the performance of AVL trees, linked lists, and arrays under various scenarios.
  • Includes analysis of rebalancing operations and their costs.

File Structure

• Theoretical_Part_Q1_Code.py: Contains code for performance analysis of AVL tree operations like insertion, deletion, and mixed operations.
• Theoretical_Part_Q2_Code.py: Compares the runtime of AVL tree operations against linked lists and arrays.
• AVLTREE_fullcode.py: The full implementation of the AVL Tree and its helper classes and methods.
• Theoretical_Part.docx & Theoretical_Part.pdf: Documentation detailing the AVL tree implementation, method descriptions, complexity analysis, and experimental results.
• Assignment.pdf: Project requirements and instructions.