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

Welcome to an introduction to AVL trees, a special type of self-balancing binary search tree.An AVL tree is a binary search tree that maintains balance through specific height constraints.The key property of an AVL tree is that the height difference between any two subtrees must not exceed one.Let's compare this with an unbalanced binary search tree to understand why balance is important.The balanced structure of AVL trees ensures optimal performance for search operations.The balance factor of each node is crucial - it's calculated as the difference between the heights of its right and left subtrees.These balancing properties make AVL trees ideal for applications requiring frequent searches and modifications while maintaining optimal performance.In the next section, we'll look at how to insert new elements into an AVL tree.Let's learn how to insert new nodes into an AVL tree.Let's insert the value 5. First, we compare it with the root node 10.Since 5 is less than 10, we go to the left. Finding no node there, we create a new leaf node.Now let's insert 15. We start at the root and compare.15 is greater than 10, so we go to the right. Finding no node there, we create a new leaf.Let's insert 3. We start at the root and compare with 10.3 is less than 10, so we go left to 5.3 is less than 5, so we create a new leaf node to the left of 5.Finally, let's insert 7. We follow the same process, starting at the root.7 is less than 10, so we go left to 5.7 is greater than 5, so we create a new leaf node to the right of 5.These are the basic rules for inserting nodes in an AVL tree. We compare values and move left or right until we find an empty spot.Notice how our insertions have maintained a relatively balanced structure, though we haven't needed any rotations yet.In the next section, we'll learn how to calculate the balance factor for each node.To maintain an AVL tree's balance, we need to calculate the balance factor for each node.The balance factor is the difference between the heights of the right and left subtrees.Let's understand how to calculate node heights. We start from the leaf nodes and work our way up.When we add a new leaf node, we need to update the heights of all nodes above it.The height of a node is always one plus the maximum height of its children.Let's calculate the balance factor for our root node. The right subtree has height 1, and the left subtree has height 1.There are several possible balance factor values. A balanced node will have a balance factor of negative one, zero, or positive one.When we add another leaf node, we need to recalculate balance factors along the path to the root.First, we update the heights. Each parent's height becomes one plus the maximum height of its children.After all updates, we verify that our tree remains balanced, with a balance factor of zero at the root.Let's examine the four cases of imbalance in AVL trees, starting with the balance factor explanation.When we insert or delete nodes, four types of imbalances can occur. Let's look at them one by one.The Left-Left case occurs when a node has a balance factor greater than 1, and its left child has a balance factor greater than or equal to 0.The Right-Right case is the mirror image, where a node has a balance factor less than negative 1, and its right child has a balance factor less than or equal to 0.The Left-Right case happens when a node has a balance factor greater than 1, but its left child has a negative balance factor.Finally, the Right-Left case occurs when a node has a balance factor less than negative 1, and its right child has a positive balance factor.Let's summarize the balance factor patterns that help us identify each case.Let's first examine the right rotation, which we use to fix a left-left imbalance.In this case, the root node has a balance factor of negative two, indicating a left-heavy imbalance.During right rotation, the left child becomes the new root of the subtree.Now let's look at the left rotation, which we use to fix a right-right imbalance.Here, the root has a balance factor of positive two, showing a right-heavy imbalance.In a left rotation, the right child becomes the new root of the subtree.After rotation, we must update the heights of affected nodes to maintain the AVL property.Let's examine the Left-Right double rotation case.In this case, we have an imbalance where the left subtree is heavier, but through its right child.First, we perform a left rotation on the left child node.Then, we perform a right rotation on the root node to complete the double rotation.Now let's look at the Right-Left double rotation case.Here we have an imbalance where the right subtree is heavier, but through its left child.First, we perform a right rotation on the right child node.Finally, we perform a left rotation on the root node to complete the double rotation.After these double rotations, both trees are now perfectly balanced.First, let's look at the simplest case: deleting a leaf node.To delete a leaf node, we first locate it in the tree.Since it has no children, we can simply remove it and update its parent's reference.Next, let's examine deleting a node with one child.When deleting a node with one child, we replace it with its child.The child node takes the position of its parent, maintaining the tree structure.The most complex case is deleting a node with two children.When deleting a node with two children, we first find its successor - the smallest value in its right subtree.The successor replaces the deleted node, maintaining the binary search tree property.After the replacement, we update all affected connections to maintain the tree structure.Remember these key points when implementing deletion in an AVL tree.In the next section, we'll learn how to rebalance the tree after deletion.After deleting a node from an AVL tree, we need to check and update balance factors along the path to the root.We start from the deleted node's parent and move upward, recalculating balance factors at each step.At each node, we calculate the difference between the heights of its right and left subtrees.If we find a node where the balance factor becomes greater than 1 or less than negative 1, we need to perform rotations.Depending on the balance factors, we apply the appropriate rotation to restore balance.Let's look at an example where we need a right rotation after deletion.The rotation process involves several steps to restore balance while maintaining the binary search tree properties.After the rotation, we have restored the AVL tree properties, with all balance factors between negative one and positive one.Finally, we verify that all nodes in the path to the root have valid balance factors.Let's examine how to handle duplicate values in AVL trees.There are two main strategies for handling duplicate values. First, we can add a count field to each node.Alternatively, we can store duplicates in the right subtree, which maintains the binary search tree property.Now, let's look at various performance optimizations for AVL trees.Path caching during search operations can significantly speed up rebalancing. Height caching prevents redundant calculations.Batch operations can be more efficient than individual ones, especially for multiple insertions or deletions.Memory optimization is also crucial for large AVL trees.Node pooling reuses deleted nodes to reduce memory allocation overhead.Optimizing the node structure layout can significantly reduce memory usage.Let's work through a comprehensive example of AVL tree operations.We begin by inserting 50 as our root node.Next, we insert 30 as a left child.Adding 70 as a right child restores perfect balance.When we insert 20, we need to check balance factors up to the root.Adding 40 as another child of 30 maintains acceptable balance.We continue growing our tree by adding 60 under 70.And finally, 80 completes our initial insertion sequence.Now let's perform some deletions. First, we'll remove leaf node 20.Next, we'll delete node 30, which has one child.Finally, we'll remove node 70, requiring tree restructuring.Our tree remains balanced after all operations, demonstrating the self-balancing nature of AVL trees.