كيف تعمل عمليات الإدراج والحذف في شجرة AVL؟ (رسوم متحركة بسيطة)

Let's understand how balance factors work in AVL trees.A balance factor is the difference between the heights of the right and left subtrees at any node.In a balanced tree, all nodes have a balance factor between negative one and positive one.Here, both subtrees have the same height, resulting in a balance factor of zero at the root.Now, let's look at an unbalanced tree where the balance factor exceeds our valid range.In this unbalanced tree, the right subtree has a height of two, while the left subtree has height zero.This gives us a balance factor of positive two at the root, which violates our valid range.When we calculate two minus zero, we get a balance factor of two, indicating this tree needs rebalancing.Let's start with the right rotation, also known as the LL case.In a right rotation, node B becomes the new root, with A becoming its right child.Now let's look at the left rotation, or RR case.In a left rotation, node Y becomes the new root, with X becoming its left child.The left-right rotation is a combination of two rotations.First, we perform a left rotation on the left subtree.Then, we perform a right rotation on the entire tree.Finally, let's look at the right-left rotation.First, we perform a right rotation on the right subtree.Then, we perform a left rotation on the entire tree.Let's begin by inserting our first value, 50, which becomes the root node.Next, we'll insert 30. Since it's less than 50, it becomes the left child.Now inserting 70 on the right. This brings the tree back into perfect balance.When we insert 20, it creates a left-heavy situation that requires rebalancing.To fix this imbalance, we perform a right rotation.Now let's see what happens when we delete node 20.When we delete node 70, we need to check and update balance factors.Let's review the key points about AVL tree operations.Thanks for learning about AVL tree operations!