Binary trees (BTree.h BTree.c) are nice convenient temporary-storage containers that can be searched rapidly. However, when the items being stored are large or many, all the available system memory might be used, so it would be convenient to have all the benefits of a binary tree, but not risk using all the RAM. And that's why I made this variant of a tree - it stores a fixed number of items, and the least-recently used items are deleted when it gets full and new items are added.
Here's a recent Python code I created for a seminar on this subject.
My first need for such a device was in the mid '90s on a system that had very limited memory (2 MB), together with a requirement to maintain the stored data until it was properly communicated to the storage facility (written in C++). I think the next time I needed this was with a 3D Surface-Related Multiple Elimination (SRME-3D) application where the "traces" of data might be referenced many times when working through regions of the data (written in C). The problem was that each trace of data was around 50KB, and thousands of these would be needed at a time. To stop the algorithm from going back to the disk file to read the same trace repeatedly I stored the data in a Fixed-Size Binary Tree that was given a limit of how many traces to store at the start when the available amount of RAM was known.
This sort of tree stores all the data in a way that allows it to throw away the oldest data when new data is added. This may seem a trivial operation, but it must be done in a way that doesn't cost too much (in terms of compute time), and that won't rely upon things like the system clock.
Each node of the tree has pointers to the parent node in the tree, the node to the left, and the node to the right, together with a pointer to the stored data. And each node also has a pointer to the next node and to the previous node in the doubly linked list. This makes for six pointers for each node.
The container also has a pointer to the head node of the tree, and pointers to the head and tail of the list.
Each time an item is added to the FSBT, it's pushed to the head of the doubly linked list and also walked through the tree to where it belongs. And if an item in a node is referenced in the tree, it's pulled out of the list and then pushed to the top of the list.
When an item is added to the FSBT that is more than it's allowed, the item at the bottom of the list is deleted. (The items that are least referenced fall to the bottom of the list, so the least-used is easy to identify.) Deleted items are also removed from their position in the tree, and their left- and right-side nodes are re-added to the tree.
To keep the tree from being lopsided, when adding items to the tree, the number of elements to the left and right are examined, and if it's not balanced, the nodes are extracted and added to make the tree relatively level. This balancing of the tree is an optional parameter to the container object.