Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees, AVL Trees - Coggle Diagram
Balanced Search Trees
Types
AVL Trees: The first self-balancing binary search tree, named after its inventors Adelson-Velsky and Landis.
Red-Black Trees: Another type of self-balancing binary search tree with different balancing properties.
Other Types: Includes B-trees, Splay trees, and 2-3 trees, each with unique balancing mechanisms.
Definition and Importance: Balanced search trees are data structures that maintain their height as low as possible, ensuring efficient operations for searching, insertion, and deletion.
Motivation: Unbalanced trees can degrade to linked lists with O(n) operations. Balanced trees maintain O(log n) height, ensuring efficient operations.
AVL Trees
Properties and Analysis
Height of AVL Tree: Always maintained as O(log n), ensuring efficient operations.
-
Rotations: Ensure that the tree remains balanced, leading to efficient search, insertion, and deletion operations.
-
Basic Operations
Insertion
-
Rebalancing: After insertion, check the balance factor of each node up to the root and perform rotations if necessary.
-
-
Deletion
-
Rebalancing: After deletion, check the balance factor of each node up to the root and perform rotations if necessary.
Rotations: Similar to insertion, to maintain the balance factor.
-
-
-
A binary search tree in which the height of the left and right subtrees of every node differs by at most one.
Balance Factor: For each node, the balance factor is the height of the left subtree minus the height of the right subtree. An AVL tree ensures the balance factor is always -1, 0, or 1.
-