CODEWITHSUNDEEP
tree
dstrac
dstrac

Reputation: 3

data structure tree complexity

I have this tree

tree

I am sure that it is a max heap, and I don't know about if it is a full tree because in course notes it says a binary tree is a full tree when every non-leave node have two children.

Upvotes: 0

Views: 151

Answers (2)

Simply Me
Simply Me

Reputation: 1587

Max-heap. there you have an example, and yes, your tree is a max-heap.

Also, for it to be a full tree, each level HAS to be filled with nodes, like in this example. Your tree is a complete tree, but not a full tree. Hope this helps.

To be a binary search tree, it has to respect some rules. For example, you have the root, left and right child.

   2
1    3

The left tree (made by 1 single node here) has to have lower values than the root, and the right tree (here made by 1 single node) has to have all the values greater than the root. So no, your tree is not a binary search tree.

Regarding the second question (you should post 1 question / post)... The worst case is O(n) if the tree is not a binary search tree. If it is a binary search tree, you get O(log n) in worst case, IF you have a balanced tree!.

If you have a binary tree, worst case is O(n) because of this valid binary search tree.

A balanced binary search tree is optimized for different kind of operations. In a general tree, depending how it is built, worst cases will be O(n)!

Upvotes: 2

OneCricketeer
OneCricketeer

Reputation: 191711

"A binary heap is a heap data structure created using a binary tree." - Wikipedia

A binary-tree means each node has 2 child references.

If each node in a binary-tree does not have two children it is not a full-tree.

O(logn) for searching because at each node, you split the dataset in half (because there are at most 2 children), going left or right to search until you reach a leaf or the data you are searching for.

Upvotes: 0

Related Questions