Use of a Binary Tree for Storage De Allocation
Original Publication Date: 1981-Nov-01
Included in the Prior Art Database: 2005-Feb-12
Many current storage de-allocation techniques maintain a chained list of all space available for allocation. Each time a new entry is to be made in this list, a search is made to see if the space to be made available is adjacent to an existing entry in the free space chain. The method described here uses a binary tree to represent available space. This reduces the worst-case number of comparisons necessary before making an entry from N to 2 log - N, where N is the number of entries.