8 Replies - 557 Views - Last Post: 05 December 2017 - 03:50 PM

#1 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 178
  • Joined: 05-January 17

Memory advantages of Binary Search Tree

Posted 01 December 2017 - 07:35 AM

Hi There!

I have been researching into the memory efficiency advantages of Binary Search Tree implementation. I haven't been able to find any good online resources/clear explanations. The few relevant explanations that I have found seem to compare BST to HashTable. HashTable is something that I haven't covered. I would really appreciate a clear explanation, or if you could direct me in the correct direction.

Many Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Memory advantages of Binary Search Tree

#2 NeoTifa   User is online

  • NeoTifa Codebreaker, the Scourge of Devtester
  • member icon





Reputation: 4216
  • View blog
  • Posts: 18,501
  • Joined: 24-September 08

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 08:45 AM

http://bigocheatsheet.com/
Was This Post Helpful? 2
  • +
  • -

#3 ndc85430   User is online

  • I think you'll find it's "Dr"
  • member icon

Reputation: 849
  • View blog
  • Posts: 3,407
  • Joined: 13-June 14

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 09:25 AM

You might want to be a bit more specific with the question. Both hash tables and BSTs are going to store all the items, so the space complexity should be O(n). Off topic somewhat, but hash tables sacrifice ordering for speed, so searching for an item in a hash table should take O(1) time (assuming a good hash function that distributes the items over the underlying storage, of course).

This post has been edited by ndc85430: 01 December 2017 - 09:28 AM

Was This Post Helpful? 2
  • +
  • -

#4 g00se   User is online

  • D.I.C Lover
  • member icon

Reputation: 3561
  • View blog
  • Posts: 16,232
  • Joined: 20-September 08

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 09:48 AM

Memory-wise a BST should theoretically have maximum memory efficiency - nodes are added only when needed, with no redundancy. Hash tables, OTOH are nearly always redundant in terms of storage. Space redundancy means faster lookups
Was This Post Helpful? 1
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12324
  • View blog
  • Posts: 45,424
  • Joined: 27-December 08

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 10:11 AM

Moved to a computer Science, as this is a theoretical question not a Java-specific question.

Please remember as well to include your thoughts and efforts in the question.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2627
  • View blog
  • Posts: 4,181
  • Joined: 21-June 11

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 10:50 AM

View PostchloeCodes, on 01 December 2017 - 03:35 PM, said:

I have been researching into the memory efficiency advantages of Binary Search Tree implementation.


Advantages over what? Compared to a plain old array, a BST has worse memory efficiency. Both in the sense that it needs more memory (each node of the tree needs memory to store its pointers as well as the value, whereas an array only uses exactly as much memory as each element needs plus, depending on the language, some constant overhead for the whole array (as opposed to per-element)) and that the memory isn't all in one place (and thus less cache-efficient).

Compared to other data structures it might fare better, but it all depends on what data structure you're comparing it to.

View Postg00se, on 01 December 2017 - 05:48 PM, said:

Memory-wise a BST should theoretically have maximum memory efficiency - nodes are added only when needed, with no redundancy. Hash tables, OTOH are nearly always redundant in terms of storage. Space redundancy means faster lookups


Asymptotically both hash maps and BSTs consume O(n) memory. In terms of actual bytes, both need more memory than the sum of the elements' sizes. Hash maps need extra memory because they allocate more memory than needed to store their number of elements (but by a constant factor, so it's still O(n)) and BSTs need extra pointers for each node. So both have constant overheads and how much depends on the implementation.
Was This Post Helpful? 1
  • +
  • -

#7 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7197
  • View blog
  • Posts: 15,004
  • Joined: 16-October 07

Re: Memory advantages of Binary Search Tree

Posted 01 December 2017 - 11:18 AM

View Postsepp2k, on 01 December 2017 - 12:50 PM, said:

BSTs need extra pointers for each node.


Technically, that's an implementation detail. If you were seriously concerned about memory, you could store a balanced tree in an array. Of course, getting to that state might require even more memory...

Honestly, I'd put memory at the bottom of the list of optimizations concerns. Assume you have infinite memory and limited CPU cycles. A program should be concerned about its operations. It is not memory that would be the issue for a standard binary tree implementation, but the cost of allocating all those nodes. A common optimization at that point would be to allocate blocks at a time.
Was This Post Helpful? 1
  • +
  • -

#8 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6285
  • View blog
  • Posts: 21,609
  • Joined: 05-May 12

Re: Memory advantages of Binary Search Tree

Posted 03 December 2017 - 06:39 PM

It maybe interesting to compare memory of the binary search tree with a linked list. Recall in your other thread that you noted the worst case for a binary search tree was to end up with something looking like a linked list.
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6285
  • View blog
  • Posts: 21,609
  • Joined: 05-May 12

Re: Memory advantages of Binary Search Tree

Posted 05 December 2017 - 03:50 PM

I just realized that the original context that this question was asked was with regards to Java. I don't have enough experience with Java, so I'll ask the general forum: Does Java even give the user enough control to be able to allocate the node in blocks as hinted at in post #7 without having to recall all your operating systems lectures and take on the cost of implementing your own memory allocator?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1