Week 5 - AVL Tree Flashcards
(20 cards)
What is an imbalanced Binary Search Tree (BST)?
An imbalanced BST is a tree where the left and right subtrees of some nodes differ significantly in height, leading to inefficient operations.
How does an imbalanced BST affect search operations?
In an imbalanced BST, search operations can degrade to O(n) time complexity, similar to a linked list, instead of the optimal O(log n).
What causes a BST to become imbalanced?
Inserting elements in sorted or nearly sorted order without balancing can cause one-sided growth, leading to imbalance.
Why is balancing a BST important?
Balancing ensures that the tree maintains minimal height, which keeps operations like search, insert, and delete efficient.
What is the concept of the height of a node in a binary tree?
The height of a node is the length of the longest path from that node to a leaf node. It is also the same as the height of the subtree rooted at that node.
What is the formula to calculate the balance factor in the binary tree?
BalanceFactor = Height of left subtree - Height of right subtree
How is the balance of a node defined in a binary tree?
balance (Empty) = 0
balance(Fork(X,L,R)) = height (L) - height (R)
This measures how balanced a node is by comparing the heights of its left and right subtrees.
What is an AVL Tree?
It is a self-balancing binary search tree. AVL (Adelson-Velsky and Landis) is where the balance factor at every node is -1, 0, or +1. This ensures the tree remains height-balanced.
What is a Perfectly Balanced Tree?
A Perfectly Balanced Tree is a binary tree in which all internal nodes have exactly two children and all leaf nodes are at the same level.
What is the relationship between the height (h) and the number of nodes (n) in an AVL Tree?
n grows exponentially as a function of h
h grows logarithmically as a function of n
What is the worst case of AVL tree?
n =F (h+2) - 1
What is the best case of AVL tree?
n = 2^h - 1
What is the range between best and worst case of AVL tree?
What is the formula for fibonacci numbers?
F(n) = F(n-1)+ F(n-2)
What is the minimum number of nodes in AVL?
N(h)=N(h−1)+N(h−2)+1
N(h) = F(n+2) -1
What is the balance factor of each node in an AVL Tree?
it is -1, 0 or 1
What are the two impacts found in AVL tree?
- Search: Same as BST, but the time complexity is O(log n)
- Insertion/deletion: It is possible to break the AVL invariant, need to rebalance the tree - Rotation
How could we rebalance it without going
through all the nodes
Start with the lowest node with an imbalance!
How many possible broken cases in generic cases?
With the constraint of AVL invariant, the new balance factor can only be -2 or 2.
- 4 possible cases
