CST211 - Data Structures: Binary Search Tree with Balancing

Overview

Self-balancing binary search tree implementation (AVL or Red-Black) for efficient search, insertion, and deletion operations.

Course Information

• Course: CST211 - Data Structures
• Assignment: Assignment 10 - Balanced Trees
• Institution: Oregon Institute of Technology

Features

• Binary search tree with O(log n) operations
• Self-balancing mechanism (AVL rotations)
• In-order, pre-order, post-order traversals
• Height balancing after modifications
• Recursive and iterative implementations

Technical Details

BST Operations

• Search: O(log n) with balancing
• Insert: O(log n) with rebalancing
• Delete: O(log n) with rebalancing
• Traversal: O(n) for all nodes

Balancing

• Height calculation and tracking
• Single and double rotations
• Balance factor maintenance
• Automatic rebalancing on insert/delete

Key Methods

• Insert(T) - Add element with balancing
• Delete(T) - Remove element with balancing
• Search(T) - Find element
• InOrder() / PreOrder() / PostOrder() - Tree traversals
• Height() - Get tree height
• Balance() - Rebalance tree

Learning Objectives

• Binary search tree properties
• Tree balancing algorithms
• Rotation operations
• Recursion in tree structures
• Performance analysis of balanced vs unbalanced trees

Technologies

• C++
• Visual Studio
• Tree data structures