14.1) Can a tree ever be both a heap and a binary search tree? If so, give an ex

Question

14.1) Can a tree ever be both a heap and a binary search tree? If so, give an example. If not, explain why not

14.4) Java's built-in TreeSet class uses time in O(log n) for insertion and deletion. It seems that we could build a (n log n) sorting algorithm by simply inserting all of the data into a TreeSet, then traversing the TreeSet inorder (Figure 14-10). The running-time analysis is correct, but this algorithm fails to sort some ArrayLists. Why? (Hint: Think about the definition of a Set.

14.5) Which order is higher: (log (log n)) or (log* n)?

14.17) Prove that a red node must have either zero or two children.

14.18) What is the tallest possible linear red-black tree?

14.20) The deletion repair case shown in Figure 14-37 makes node lower in the tree. Why is there no danger that this could lead to an infinite loop, where no progress is made toward the root? (Hint: What is the color of node 4's right child?)

Explanation / Answer

1) By definition Heap assures that elements of higher level are greater where as BST gives the order from left to right so yes we can say a tree can be both heap an BST if its in increasing order this way it will fulfill the heap basic idea of keeping greater value at high and maintain order of BST.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.