Give a recursive version of the TREE-INSERT procedure.
Suppose that a binary search tree is constructed by repeatedly inserting distinct values into the tree. Argue that the number of nodes examined in searching for a value in the tree is one plus the number of nodes examined when the value was first inserted into the tree.
多检查一次是否相等.
We should check one more time of this node, obviously.
We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?
退化成链表就是最坏情况.
If it's Degenerated into a list, then the worst situation.
Suppose that another data structure contains a pointer to a node y in a binary search tree, and suppose that y's predecessor z is deleted from the tree by the procedure TREE-DELETE. What problem can arise? How can TREE-DELETE be rewritten to solve this problem?
当要删除的节点有两个子节点时，节点y会被删除. 如果指向的是节点y,那么就出问题的.在这种情况下应该修改成指向节点z.
If the node being deleted has two child nodes, then y will be deleted. If the pointer point to y, there will be problem. Under such situation, the pointer should point to node z.
Is the operation of deletion "commutative" in the sense that deleting x and then y from a binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample.
NO.
When node z in TREE-DELETE has two children, we could splice out its predecessor rather than its successor. Some have argued that a fair strategy, giving equal priority to predecessor and successor, yields better empirical performance. How might TREE-DELETE be changed to implement such a fair strategy?
- Randomly choose one
- Assign each node with an attribute height, choose the higher one.
Follow @louis1992 on github to help finish this task.