What is the primary characteristic of a binary search tree (BST)?
A Nodes have two children
B Unordered
C Nodes are ordered
D Balanced
In a binary search tree, the left child of a node is smaller than the node, and the right child is larger. This ordering property ensures that search operations can be performed efficiently in O(log n) time for balanced trees.
Which operation ensures that an AVL tree remains balanced?
A Rotation
B Insertion
C Deletion
D Traversal
Rotations are used to maintain balance in an AVL tree. After insertion or deletion, rotations are performed to ensure the height difference between the left and right subtrees of any node does not exceed 1.
Which of the following properties is true for a Red-Black Tree?
A Nodes are always balanced
B The tree is never empty
C Each node has at most two children
D Every path from the root to the leaves contains the same number of black nodes
In a Red-Black tree, the number of black nodes from the root to any leaf is the same. This ensures the tree remains balanced, providing efficient search, insertion, and deletion operations.
What is the worst-case time complexity of searching in an unbalanced binary search tree?
A O(log n)
B O(n)
C O(n log n)
D O(1)
In an unbalanced binary search tree, the worst-case time complexity for searching is O(n) because the tree could degrade into a linked list, where each node only has one child, requiring a linear scan of all nodes.
What type of tree is used to implement associative arrays in many programming languages?
A AVL Tree
B B-Tree
C Red-Black Tree
D Binary Search Tree
Many programming languages, such as C++ and Java, use Red-Black trees to implement associative arrays (maps or dictionaries) due to their efficient balancing and logarithmic time complexity for search, insertion, and deletion.
In a Red-Black Tree, which of the following statements is true?
A Insertion
B All leaf nodes are black
C Deletion
D Searching
In a Red-Black tree, all leaf nodes are considered black (these are NIL nodes). Additionally, the tree must maintain several other properties to ensure balance, like no two adjacent red nodes.
Which of the following is a key advantage of an AVL tree over a regular binary search tree?
A Automatic balancing
B Faster insertion
C Lower space complexity
D No rotations needed
An AVL tree is a self-balancing binary search tree that automatically maintains balance after each insertion or deletion, ensuring that the tree remains balanced with a height difference of at most 1 between subtrees.
What is the average time complexity for search operations in a balanced binary search tree?
A O(n)
B O(log n)
C O(1)
D O(n log n)
In a balanced binary search tree, the average time complexity for search operations is O(log n), because the height of the tree is kept minimal, allowing for efficient searching through the tree.
What does a left rotation operation do in an AVL tree?
A Reverses the order of nodes
B Balances the tree by changing the root
C Doubles the number of nodes
D Increases the height of the right subtree
A left rotation in an AVL tree is performed when the right subtree becomes unbalanced. It changes the root of the subtree, making the right child the new root, while maintaining the binary search tree properties.
What is the primary reason for using a Red-Black tree over an AVL tree in practice?
A Faster insertions
B Simpler balancing rules
C Lower space complexity
D More balanced tree structure
Red-Black trees are preferred over AVL trees in practice because they have simpler balancing rules. While both provide O(log n) time complexity, Red-Black trees perform fewer rotations, leading to faster insertion and deletion operations in some cases.
Which of the following operations is generally faster in a Red-Black Tree than in an AVL Tree?
A Insertion
B Deletion
C Searching
D All of the above
In a Red-Black tree, insertion is generally faster than in an AVL tree because Red-Black trees require fewer rotations to maintain balance. AVL trees enforce stricter balance conditions, leading to more complex balancing during insertions.
What is the time complexity of inserting a node into an AVL tree?
A O(log n)
B O(n)
C O(1)
D O(n log n)
The time complexity of insertion into an AVL tree is O(log n) because the tree maintains balance after each insertion. Rotations may be required, but the number of rotations is limited and logarithmic with respect to the tree’s height.
Which of the following trees provides efficient search and is used in databases for disk-based indexing?
A AVL Tree
B Red-Black Tree
C B-Tree
D Binary Search Tree
B-Trees are commonly used for disk-based indexing in databases due to their ability to store large amounts of data efficiently. They are balanced and ensure that search, insertion, and deletion operations are efficient, even with large datasets.
What is the time complexity of searching for an element in a Red-Black tree?
A O(log n)
B O(n)
C O(1)
D O(n log n)
The time complexity of searching in a Red-Black tree is O(log n), which is guaranteed because the tree is balanced. The path from the root to any leaf is logarithmic in height, ensuring efficient search operations.
What happens if an AVL tree becomes unbalanced during an insertion operation?
A A Red-Black tree is used instead
B A left or right rotation is performed
C The tree is automatically resized
D The insertion fails
When an AVL tree becomes unbalanced due to an insertion, a rotation (either left or right) is performed to restore balance. This ensures the tree remains balanced, keeping its height logarithmic and maintaining efficient operations.