1. Why is it good for binary search trees to be balanced? 2. A binary search tre
ID: 658050 • Letter: 1
Question
1. Why is it good for binary search trees to be balanced?
2. A binary search tree has a right subtree but no left subtree. What node contains the
least element in the tree?
3. What is the height of a binary tree?
4. Explain the concept of order as used with priority queues.
1320 Chapter 22 Binary Trees, AVL Trees, and Priority Queues
5. What is a priority queue?
6. Explain why the depth of a complete binary tree with n nodes is at most log n + 1.
7. How does an AVL tree differ from an ordinary binary search tree?
Explanation / Answer
1. Balances binary tree provide fast looup which is very effective in dynamic memory allocation when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array.
2. the least element will be the left node of the right sub tree.
3.?n where n is the number of elements.
4.
5.a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
6.The number of nodes in the tree is the sum of the number of nodes at each level:
n = 2h+2h-1+2h-2+...+21+20 = 2h+1 - 1
n = 2h+1 - 1
n+1 = 2h+1
log(n+1) = log(2h+1)
log(n+1) = h+1
h = log(n+1) - 1.
where n=number of nodes
and h=height of the tree
7.A binary search tree (BST) is a binary tree data structure which has the following properties:
->each node has a value;
->a total order is defined on these values;
->the left subtree of a node contains only values less than the node's value;
->the right subtree of a node contains only values greater than or equal to the node's value.
An AVL tree is a self-balancing binary search tree.
In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.