Practice TestTake a test on your terms and definitions
Spaced RepetitionScientifically backed study method
Matching GameHow quick can you match all your cards?
FlashcardsStudy terms and definitions
1 / 39
There's no tags or description
Looks like no one added any tags here yet for you.
40 Terms
1
What is a binary search tree (BST)?
It is a data structure that consists of nodes, where each node has a key, and the left subtree contains node with smaller keys, while the right subtree contains node with the larger keys.
New cards
2
What are the 3 fundamentals operations of a set?
find, insert and remove (FIR)
New cards
3
How does a map differ from a set?
A map stores key-value pairs, allowing access to values based on their associated keys, while a set is just a collection of unique elements.
New cards
4
What is the time complexity for find
insert and remove operations in a balanced binary search tree?,O(log n)
New cards
5
What happens if a binary search tree is not balanced?
Its height can become linear, leading to O(n) time complexity for operations.
New cards
6
What is the binary search tree property?
It is that any node, all elements in the left subtree are smaller and all elements in the right subtree are larger.
New cards
7
Why is it important to keep a binary search tree balanced?
It helps ensures that the height remains logarithmic, which maintains efficient operation times for find, insert and remove (FIR).
New cards
8
What is a degenerate tree?
It is a binary search tree that has become unbalanced, resembling a linked list, where each node has only one child.
New cards
9
What is the relationship between binary search trees and quicksort?
The comparison made when building a binary search tree correspond to the comparisons made during the partitioning steps of quicksort.
New cards
10
What is the expected depth of randomly built binary search tree?
O(log n) with high probability.
New cards
11
What are some mechanisms to keep a binary search tree balanced?
AVL trees, Red-Black trees and Splay trees.
New cards
12
What is the significance of the height of a binary search tree?
It directly affects the efficiency of its operations; a lower height leads to faster operations.
New cards
13
How does recursion play a role in binary search tree?
Most operations in binary search trees can be implemented recursively, as each subtree is also a binary search tree.
New cards
14
What is the average-case time complexity for inserting elements into a binary search tree?
O(log n)
New cards
15
What is a priority queue
and how can it be implemented using a binary search tree?,It is a data structure that allows for the retrieval of the highest (or lowest) priority element. It can be implemented using a binary search tree by maintaining the order of elements based on their priority.
New cards
16
What is balanced binary search tree?
A balanced binary search tree maintains its height to be logarithmic relative to a number of nodes, ensuring efficient operations. Ex. AVL tree and Red-Black trees.
New cards
17
What is the purpose of "find" operation in binary search tree?
It searches for a specific key in the tree, returning whether the key exists and its associated value if applicable.
New cards
18
What is a leaf node in binary search tree?
A leaf node is a node that does not have any children, it is the end point of a path in the tree.
New cards
19
What is the difference between a binary search tree and a binary tree?
A binary tree is a general tree structure where each node can have up to two children, while a binary search tree has specific ordering rules that allow for efficient searching.
New cards
20
Why use a binary search tree?
It is efficient for searching, adding and deleting numbers. They help keep everything organized, making it easy to find what you need quickly, just like a well-organized library.
New cards
21
What is an IN-ORDER traversal in a binary tree?
It is a recursive traversal where you traverse the left subtree, print the root, and then traverse the right subtree, resulting in sorted order.
New cards
22
What is the time complexity of IN-ORDER traversal?
O(n) which is linear.
New cards
23
How can you find the minimum element in a binary search tree?
By walking down the left spine of the tree until you can't go left anymore.
New cards
24
What is the purpose of PRE-ORDER traversal?
It visits the root first and then recursively visits the children, often used for calculations on binary search trees.
New cards
25
What is the difference between predecessor and successor in a binary search tree?
The predecessor is the maximum in the left subtree, while the successor is the minimum in the right subtree.
New cards
26
How do you delete a node with two children in a binary search tree?
You can swap it with either its predecessor or successor, which will have at most one child, making it easier to delete.
New cards
27
What is a split operation in a binary search tree?
It divides a binary search trees into two smaller trees based on a specified value.
New cards
28
What is a join operation in a binary search tree?
It combines two binary search trees with disjoint key ranges into a single tree.
New cards
29
What is the significance of the Eulerian Traversal?
It is equivalent to a depth-first search of a tree and walks down every edge once and back up once.
New cards
30
How can a binary search tree serve as a priority queue?
It can easily find and remove the minimum element, as well as insert new elements.
New cards
31
What is the time complexity for inserting (n) elements into a balanced binary search tree?
O(n log n)
New cards
32
What is the relationship between trees and sequences?
Trees can represent sequences, and traversals can convert a tree into a corresponding sequence.
New cards
33
What is the role of POST-ORDER traversal?
It visits all children before the root, useful for bottom-up computations like counting nodes.
New cards
34
How do you find the predecessor of an element in a binary search tree?
If the element has a left subtree, it is the maximum of that subtree; otherwise, it is first ancestor that is a left child.
New cards
35
What is the time complexity for finding the predecessor or successor in a balanced binary search tree?
O(log n).
New cards
36
What is the time complexity for searching an element in a balanced binary search tree?
O(log n).
New cards
37
What is a balanced binary search tree?
A balanced binary search tree maintains its height to be logarithmic relative to the number of nodes, ensuring efficient operations.
New cards
38
What is a range query in the context of binary search trees?
A range query retrieves all elements within a specified range of values, allowing for efficient enumeration of data.
New cards
39
How does a binary search tree differ from a hash table?
A binary search tree maintains order and allows for range queries, while a hash table provides constant time access but does not maintain order.
New cards
40
What is the significance of the split and join operations in binary search trees?
The split operation divides a tree into two based on a value, while the join operation combines two disjoint trees, facilitating efficient data management.
Studied by 0 people
