Ordered Binary Trees Here we would like to define an OrderedBinaryTree as a data
ID: 3600487 • Letter: O
Question
Ordered Binary Trees Here we would like to define an OrderedBinaryTree as a data type where for each node with label n, all of the children in the left sub-tree have labels smaller than n, and all the children in the right sub-tree have labels larger than n Base case: null E OrderedBinaryTree. -Constructor case: if t1,t2 E OrderedBinaryTree and n E N, and (empty(ti) V maximum(ti) n) and You may assume all the other tree operations (including traverse from question 5) are defined for Tree. OrderedBinaryTree s also. 7. Define the minimum : OrderedBinaryTree N and maximum : Ordered inaryTree N opera- tions used in the definition of OrderedBinaryTree above. (pi,P2, . . . ,Pn) is an (*) Prove that Vt E OrderedBinaryTee. traverse(t) is an ordered list. (A list, p ordered list if Vi e 1,--.,n -1).piExplanation / Answer
Answer 7
In a n ordered binary tree, a new key is always inserted at leaf. We start searching a key from root till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
In the worst case, the tree may be skewed and n operations may be required to insert a node. Best case is of a balanced tree where log2n operations would be required to find the correct position of the node to be inserted.
The worst case time complexity of search and insert operations is O(log2n) where h is height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of search and insert operation may become O(n).
Answer 8
Our goal is to show that in-order traversal of a finite ordered binary tree produces an ordered sequence.
To prove this by contradiction, we start by assuming the opposite: that there exists some ordered binary tree such that its in-order traversal yields a non-ordered sequence. Since our trees are finite, there must be a minimal such instance. Let's call this tree T.
Now, T cannot be a singleton (i.e., just a leaf) because the traversal of a singleton yields a sequence of length one, which is trivially ordered.
Therefore T must have some shape, L-x-R where x is a vertex value connecting left and right subtrees L and R respectively.
Since T is minimal and ordered, L and R must be ordered trees whose in-order traversals produce ordered sequences. Moreover, we know that all items in L can be no greater than x and all items in R can be no smaller than x. Now, the traversal of T is [T] = [L] ++ [x] ++ [R]. But this sequence must be ordered, which contradicts our initial assumption concerning T.
Therefore no such T exists, hence in-order traversal of any ordered binary tree must produce an ordered sequence.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.