Binary search trees Flashcards
What is an AVL tree, and why is it significant
An AVL tree is a type of self-balancing binary search tree (BST) where the height difference between the left and right subtrees of any node is at most one. This balance ensures that operations like insertion, deletion, and search have a time complexity of O(log n), making AVL trees significant for maintaining efficient operations in a sorted structure.
What are the basic properties of binary search trees (BSTs)?
A binary search tree (BST) has the following properties:
It is a rooted binary tree.
For any node x, all keys in its left subtree are less than x, and all keys in its right subtree are greater than x.
This structure allows efficient search, insertion, and deletion operations, depending on the height of the tree.
What are the common operations in binary search trees, and what is their time complexity?
The common operations in binary search trees are:
Search(T, k): Searches for a key k in the tree T. The time complexity is O(h), where h is the height of the tree.
Insert(T, k): Inserts a key k into the tree T. The time complexity is O(h).
Delete(T, k): Deletes a key k from the tree T. The time complexity is O(h).
The height h of a BST determines the operation’s efficiency.
What is the balance factor in AVL trees, and how is it used?
The balance factor in AVL trees is the difference in heights between the left and right subtrees of a node. It can be -1, 0, or +1, indicating whether a tree is left-heavy, balanced, or right-heavy. This balance factor is used to determine if the AVL property is maintained and if rotations are needed to restore balance.
What is a rotation in AVL trees, and why is it performed?
A rotation in AVL trees is an operation that adjusts the tree’s structure to restore the AVL property. It is performed when the balance factor of a node exceeds the allowable range, indicating that the tree is unbalanced. There are two types of rotations:
Right Rotation: Applied when a subtree is left-heavy.
Left Rotation: Applied when a subtree is right-heavy.
Rotations ensure that the tree remains balanced, maintaining efficient operations.
Describe a Right Rotation and its effect on an AVL tree.
A Right Rotation occurs when a subtree is left-heavy. The root of the subtree is moved to the right child, and the left child becomes the new root. This rotation helps restore balance by adjusting the tree structure, preserving the binary search tree property, and ensuring the AVL property is maintained.
Describe the process of inserting a node into an AVL tree.
The insertion process in an AVL tree involves:
Inserting the node as in a standard binary search tree.
Checking if the AVL property is violated (balance factor greater than 1 or less than -1).
Applying rotations to restore balance:
Left Rotation: If the tree is right-heavy.
Right Rotation: If the tree is left-heavy.
Right-Left Rotation: For certain left-right cases.
Left-Right Rotation: For certain right-left cases.
Ensuring that all nodes comply with the AVL property after insertion.
What is the worst-case height of an AVL tree, and how does it compare to a standard BST?
The worst-case height of an AVL tree is O(log n), where n is the number of nodes. This is significantly better than a standard BST, which can have a height of O(n) in the worst case. AVL trees maintain balance, ensuring a consistent height, which provides efficient operations even as the number of nodes grows.
What is AVL sort, and how does it differ from standard BST sort?
AVL sort is a sorting technique that uses AVL trees to maintain a balanced structure. It involves inserting elements into an AVL tree and then performing an in-order traversal to extract the sorted elements. Unlike standard BST sort, which can have a worst-case time complexity of O(n^2) due to unbalanced trees, AVL sort maintains O(log n) height, resulting in a worst-case time complexity of O(n log n).
What is the expected running time for AVL insertion, and why is it efficient?
The expected running time for AVL insertion is O(log n). This efficiency comes from the self-balancing nature of AVL trees, where the height is kept in check through rotations. Since the height of the tree is O(log n), insertion operations maintain this time complexity, ensuring consistent performance regardless of the number of nodes.
