C++ Footprint and Performance Optimization

Binary Trees

Binary trees, sometimes called binary search trees (bst), are popular storage structures. You can search through trees much faster than through linked lists. A well-balanced tree can be searched as efficiently as a sorted array: O(n log2 n). This is because tree searching has the same properties as a binary search algorithm for an array—see the binsearch function in the section on arrays. However, the overhead per stored element is higher with trees than with a single linked list. A binary tree has references to (at most) two child nodes so, just like with double linked lists, two pointer fields need to be added to each stored element. As with linked lists, the elements of a tree are stored in memory separately, causing the same ...