avl tree

An AVL tree is a self-balancing binary search tree where the heights of the left and right subtrees of any node differ by at most one. Here are the steps for performing various operations on an AVL tree:

1. Insertion:
2. Start at the root and compare the value to be inserted with the current node's value.
3. If the value is less than the current node's value, move to the left subtree. If it is greater, move to the right subtree.
4. Recursively repeat the above steps until reaching a null position.
5. Create a new node with the value and insert it at the null position.
6. Update the heights of the nodes from the inserted node up to the root and check for any imbalances.

7. If an imbalance is found, perform rotations to restore the balance of the tree.

8. Deletion:

9. Start at the root and compare the value to be deleted with the current node's value.
10. If the value is less than the current node's value, move to the left subtree. If it is greater, move to the right subtree.
11. Recursively repeat the above steps until finding the node to be deleted.
12. If the node has no children, simply remove it from the tree.
13. If the node has one child, replace it with its child.
14. If the node has two children, replace it with either the inorder predecessor or inorder successor, and recursively delete that predecessor or successor.
15. Update the heights of the nodes from the deleted node up to the root and check for any imbalances.

16. If an imbalance is found, perform rotations to restore the balance of the tree.

17. Searching:

18. Start at the root and compare the value to be searched with the current node's value.
19. If the value is less than the current node's value, move to the left subtree. If it is greater, move to the right subtree.
20. Recursively repeat the above steps until finding the node with the desired value or reaching a null position.

21. If the node is found, return it. Otherwise, the value is not present in the tree.

22. Rotations:

23. There are four types of rotations: left rotation, right rotation, left-right rotation, and right-left rotation.
24. Left Rotation: This operation is performed to fix a right-heavy subtree. It involves moving the right child of a node up to become its parent, while the node becomes the left child of its former right child.
25. Right Rotation: This operation is performed to fix a left-heavy subtree. It involves moving the left child of a node up to become its parent, while the node becomes the right child of its former left child.
26. Left-Right Rotation: This operation is a combination of left and right rotations. It is performed to fix a left-heavy subtree with a right-heavy child. It involves performing a left rotation on the left child, followed by a right rotation on the node.
27. Right-Left Rotation: This operation is a combination of right and left rotations. It is performed to fix a right-heavy subtree with a left-heavy child. It involves performing a right rotation on the right child, followed by a left rotation on the node.

These steps ensure that the AVL tree remains balanced after performing insertions, deletions, and other operations.