Implemented AVL Tree Data Structure

[Ramy-Badr-Ahmed]

Contents:

• AVLTreeNode Class: Represents individual nodes in the AVL Tree with key, value, height, left, and right attributes.

  It also provides methods to:

  update: Updates the height of the node. balance: Calculates the balance factor of the node.

• AVLTree Class: Implements the core functionalities of an AVL Tree:

  insert: Inserts a key-value pair into the tree while maintaining the AVL balance. delete: Deletes a node by key and rebalances the tree accordingly. search: Retrieves the value associated with a given key. rotateLeft and rotateRight: Helper methods to perform rotations for balancing the tree. balance: Balances the AVL Tree after insertion or deletion. getRoot: Returns the root of the tree. size: Returns the number of nodes in the tree.

• TreeTraversal Class (Abstract): Provides traversal methods:

  inOrder: In-order traversal (left-root-right). preOrder: Pre-order traversal (root-left-right). postOrder: Post-order traversal (left-right-root). breadthFirst: Breadth-first (level-order) traversal.

• Unit Tests:

  AVLTreeTest.php: Tests covering AVL Tree insertions, deletions, rebalancing, and searches. Additionally, tests for correct traversal behavior using in-order, pre-order, post-order, and breadth-first traversals.

GitHub Actions

All tests and workflows (in my forked repository) have passed:

• PHPCS

• DIRECTORY.md

• build

---

Reference

Data Structures and Algorithms in C++, 2nd Edition

[Ramy-Badr-Ahmed]

Note

PR is complemented with #173