What applications for binary trees implemented in vectors?

Asked

Viewed 1,296 times

0

I know the theory of binary trees, I have already implemented a stroke in C. I understand the functioning and applications of it when developed dynamically. However, a teacher asked me to develop a binary tree in vector, I did it perfectly only I can not identify a utility or advantage for this type of specific structure.

c

  • Depending on how it is implemented, it may not even be actually making a binary tree. It may be that you are just simulating memory with it and in fact are using pointers created by you to implement. I wanted to see this implementation to see if it’s still a tree in fact and if it is, if it’s not just an extra layer on something unnecessary.

  • One of the greatest advantages of an array is direct access. On this, take a look at Heaps, which are binary trees of maximum and minimum, very well implemented with vectors, due to the way it is organized. If you like, search for Heapsort, a sort algorithm using this structure.

2 answers

1

Are some advantages:

1) The search in width becomes a simple interaction over the Array

2) You have O(1) access to any node in your tree instead of having to go through its height to get there.

3) Arrays exist in virtually all programming languages, unlike pointers.

Source: https://www.quora.com/When-is-it-good-to-represent-a-binary-tree-as-an-array-instead

Surely there are other advantages/applications, so comment that I edit in the answer, but I think it is clear that there is a yes application and a reason to use the tree in this way.

0

The Heapsort is a classic case where you have a binary tree represented on a vector.

The advantages of using a binary tree represented on a vector are relative to performance:

  • the data is not totally independent of each other in memory, so you will have less cache miss
  • the processor will not need to navigate from the pointer to the memory region containing the node, only then to pick up its value, so you do less memory access, which results in less processing and decreases the chances of changing the data that is cached
  • you allocate less memory and in a contiguous region as you are working with an element vector

There are disadvantages related to use in vector representation as well. Removal/insertion can become problematic as it requires manipulation of subtrees.

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.