CODEWITHSUNDEEP
binary-treebinary-search-tree
Mode77
Mode77

Reputation: 1041

How does a binary tree waste memory when stored as nodes and references?

I'm researching binary trees and came across this section describing storage methods.

It states that:

In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child...

...This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time...

Can someone demonstrate or further explain why this happens?

https://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees

Upvotes: 1

Views: 333

Answers (2)

lrleon
lrleon

Reputation: 2648

The typical binary tree representation consists of the data associated with the node and two pointers to the left and right subtree respectively.

I think that with representation it is easy to realize that every node spends two pointers. Consequently, every tree of n nodes, spends a total of 2 x n pointers in storage (for the pointers).

Now well, at the exception of the root, n-1 nodes have a parent (that is an arc or edge). So, you really use n-1 pointers of 2n that you have (as explained in the previous paragraph).

That said, of a total of 2n pointers, you always use n-1. The remaining 2n - (n-1) = n+1 are always set to null. So, no matter the tree topology, you always spend more space for storing null pointers than for storing tree arcs.

Upvotes: 1

Alexey Frunze
Alexey Frunze

Reputation: 62106

Imagine a full binary tree of height 3. It has 7 nodes. 4 of them have no children. 4/7 > 1/2.

Upvotes: 1

Related Questions