The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
667 views
Which of the following need not be a binary tree?
(a) Heap (b) B-Tree
(c) AVL- Tree (d) None of these
asked in DS by Boss (6.7k points) | 667 views
Heap need not be always binary , it may be $d_{ary}$ heap
A B-Tree is not a binary tree , it may be n-ary tree
Heap needn't be a binary tree always. The only requirement to be a heap is it should be a complete tree.
@smsubham : your argument is valid $\text{iff}$ Heap is a $\text{binary heap}$

sourav. 

By mistake added binary in 2nd sentence. Check now.

Heap Variants:

  • 2-3 heap
  • Binary heap
  • Many many others

The only requirement to be a heap is it should be a complete tree.

also $\text{Almost complete binary tree}$

What is the difference between complete and almost complete binary tree?
Saw that before asking, But things aren't clear there. Can you give an example which is complete BT but not almost complete BT and vice versa?

if last level of the tree are completely fill then it is complete binary tree 

and if 2nd last level are completely filled but the last level is not completely filled then it is almost complete binary tree

So definition and examples given here are wrong i suppose.

https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

According to it: 

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

Following are examples of Complete Binary Trees

               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9 

 

first one is complete and other is almost complete  binary tree

4 Answers

+1 vote
Best answer
B tree...................... B trees need not be the binary tree. B trees may have more than 2 children....

order of B tree is max. no. of children a node can have..
answered by Active (1.1k points)
selected by

let me see a binary tree with more than 2 children!!!!

binary tree always have  2 children...but B trees need not be only 2 children it may have more than 2 children.....

Priyanka Agarwal  yes you are right

I don't think this is correct. Check my answer.
+2 votes
(b) B-Tree
answered by Boss (6.7k points)
+1 vote
b) B-Tree
answered by (113 points)
0 votes

Will be both Heap and B tree.

Heaps
Definition: A heap is a specialized tree-based data structure that satisfied the heap property:
  • if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. Of course, there's also a min-heap.

Variants:

  • 2-3 heap
  • Binary Heap
  • Many many others

Binary heap storage rules  -- A heap implemented with a binary tree in which the following two rules are followed:

  • The element contained by each node is greater than or equal to the elements of that node's children.
  • The tree is a complete binary tree.

So heap needn't be binary always.

AVL tree is BST with balancing factor.

Source: https://www.cpp.edu/~ftang/courses/CS241/notes/heap.htm

answered by Boss (5.6k points)
@smshubham : you are half correct.

you have wriiten that $\text{B tree}$ are not necessarily binary .It is correct.where is your explanation?

Related questions

+3 votes
3 answers
2


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,714 questions
40,263 answers
114,377 comments
38,898 users