Some of these problems use the following type, Node.
struct Node { int item; Node* left; Node* right; Node(int i, Node* L, Node* R) { item = i; left = L; right = R; } };
Write a function that writes all of the numbers in a binary search tree in ascending order on the standard output, one number per line. The function takes a parameter of type const Node*, pointing to the tree, and has a void return type.
Write a function to return the largest number in a binary search tree. There should be one parameter, of type const Node*, pointing to the tree. Assume that the tree is nonempty.
If you insert 62 into the following binary search tree, using the basic algorithm that does not rebalance, what tree do you get?
If you insert 26 into the following binary search tree, without rebalancing, what tree do you get?
If you insert 26 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
If you insert 27 into the following binary search tree, without rebalancing, what tree do you get?
If you insert 27 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
If you remove 40 from the following binary search tree using the algorithm discussed in class, without rebalancing, what binary search tree do you get?
If you remove 40 from the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
If you remove 60 from the following binary search tree using the algorithm discussed in class, without rebalancing, what binary search tree do you get?
If you insert 20 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
If you insert 27 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
If you remove 8 from the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?
Which of the following is true about log2(500)?
What is log2(32)?
To within a constant factor, how much time does it take to insert a value into a height-balanced binary search tree that has n values in it already, in the worst case?
To within a constant factor, how much time does it take to remove a value from a height-balanced binary search tree that has n values in it, in the worst case?
Does the height-balancing algorithm based on single and double rotations always keep a tree height-balanced, or are there some rare sequences of insertions and removals that can cause the tree to become non-height-balanced?