Design & Implement AVL Tree Structure
Budget: $15 – $25 USD
1. AVL Tree Structure
Develop a Node data structure to represent the nodes of the AVL tree.
Each node must have the following fields:
int key: Integer value to store the node key.
int height: Stores the node height for balancing control.
Node* left and Node* right: Pointers to the child nodes.
2. Mandatory Operations
Insertion:
Implement the insert(Node* root, int value) function that inserts a value into the tree and ensures AVL balancing.
At each insertion, check and correct the tree balancing using rotations (single and double) when necessary.
Rotation:
Implement the necessary rotations: right rotation, left rotation, double right rotation and double left rotation.
Removal:
Implement the remove(Node* root, int value) function that removes a node from the tree and ensures AVL balancing after removal.
Search:
Implement the function search(Node* root, int value) that searches for a value in the AVL tree and returns whether it is present.
Display:
Implement a function that displays the AVL tree in order or in pre-order, showing the key and height of each node.
3. Test Requirements
Insert and remove elements to demonstrate the functionality and balancing of the tree.
At the end of the implementation, present a sequence of insertions and removals that illustrates balancing by rotations.
4. Evaluation Criteria
Correct implementation of insertion, removal and balancing operations.
Correct use of rotations to maintain AVL balancing.
Code functionality and readability (comments, variable and function naming).
Adequate testing and output of the tree display after operations.
5. Final Guidelines
The code must be developed in C language.
Comment the code explaining each function and the balancing processes.
Comment the code with the full name and RA of each group member.
The delivery must include a .PDF file with the code implementation and examples of running the AVL tree.
Develop a Node data structure to represent the nodes of the AVL tree.
Each node must have the following fields:
int key: Integer value to store the node key.
int height: Stores the node height for balancing control.
Node* left and Node* right: Pointers to the child nodes.
2. Mandatory Operations
Insertion:
Implement the insert(Node* root, int value) function that inserts a value into the tree and ensures AVL balancing.
At each insertion, check and correct the tree balancing using rotations (single and double) when necessary.
Rotation:
Implement the necessary rotations: right rotation, left rotation, double right rotation and double left rotation.
Removal:
Implement the remove(Node* root, int value) function that removes a node from the tree and ensures AVL balancing after removal.
Search:
Implement the function search(Node* root, int value) that searches for a value in the AVL tree and returns whether it is present.
Display:
Implement a function that displays the AVL tree in order or in pre-order, showing the key and height of each node.
3. Test Requirements
Insert and remove elements to demonstrate the functionality and balancing of the tree.
At the end of the implementation, present a sequence of insertions and removals that illustrates balancing by rotations.
4. Evaluation Criteria
Correct implementation of insertion, removal and balancing operations.
Correct use of rotations to maintain AVL balancing.
Code functionality and readability (comments, variable and function naming).
Adequate testing and output of the tree display after operations.
5. Final Guidelines
The code must be developed in C language.
Comment the code explaining each function and the balancing processes.
Comment the code with the full name and RA of each group member.
The delivery must include a .PDF file with the code implementation and examples of running the AVL tree.