What applications for binary trees implemented in vectors?

Question

What applications for binary trees implemented in vectors?

Navigation

#1 by (1 votes)
#2 by (0 votes)

0

I know the theory of binary trees, I have already implemented an AVL in C. I understand the operation and applications of it when dynamically developed. But a teacher asked me to develop a binary tree in vector, I made it perfectly just that I can not identify a utility or advantage for this kind of structure specific.

c

asked by anonymous 17.01.2017 / 19:34

2 answers

What implementation would I use to initialize the data in the bank using 1: N relationship? Questions Assembly mips

score 1 · Answer 1

There are some advantages:

1) The width search becomes a simple interaction on the Array

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

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

Source: link

Of course there are other advantages / applications, so comment that I edit in the answer, but I think it's clear that it has application and a reason to use the tree in this way.

score 0 · Answer 2

The HeapSort is a classic case where you have a binary tree represented in a vector.

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

The data is not totally independent of each other in memory, so you will have less than cache miss
The processor will not have to navigate the pointer to the memory region containing the node, only to get its value, so you get less access to the memory, which means less processing and less chance of changing the data that is Cached
You allocate less memory and a contiguous region because you are working with an element vector

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