Binary search tree system and method
A binary search tree is provided for efficiently organizing values for a set of items, even when values are duplicated. In generating the binary search tree, the value of each item in a set of values is determined. If a particular value is unique and is found only once in the set, than that unique value is used as a node in the binary search tree. If a value is duplicative and is found two or more times in the set, then the duplicative value is used as a hook in the binary search tree. The hook element has a list branch that is used to identify items having a value equal to the duplicative value. A node tree may be extended from a second branch of the hook, with the node tree having a base node equal to the duplicative value. The base node may have a first branch for holding a value less than the duplicative value, and a second branch for holding a value greater than the duplicative value.
1. A method for managing a memory, comprising:
providing a plurality of available memory blocks, each memory block having a size;
providing a tree comprised of elements where each element has between 0 and 2 branches inclusive, a value, and an indicator, the indicator enabled to indicate if an element is further a hook-element, each hook-element comprising a first branch to a linked list where each element in the linked list has a value the same as the hook-element value, and a second branch to an element with a same value as the hook-element, and where each of the plurality of available memory blocks is associated with one element with the size of the associated memory block being equal to the value of the associated element;
requesting an allocation of memory comprised of a request size;
searching for one of the available memory blocks that satisfies the allocation request, the searching process further comprising:
comparing the request size to a first value of a first element;
determining if the indictor indicates the first element is a hook-element and if the first value is equal to the request size;
traversing, if the indicator indicates a hook-element and the first value and request size are equal, to the hook-element's first branch;
traversing, if the indicator indicates a hook-element and the first value and request size are unequal, to the hook-element's second branch;
traversing, if the indicator did not indicate a hook-element and the request size is larger than first value, to a branch comprised of elements with values all greater than the first value;
traversing, if the indicator did not indicate a hook-element and the request size is smaller than first value, to a branch comprised of elements with values all smaller than the first value;
continuing determining and then traversing until an element that is not a hook-element and has a same value as the request value is reached, being a request element thereby;
removing the request element from the tree; and
making the memory block associated with the removed element available for the memory request.
2. The method according to claim 1 , further comprising:
providing each element with an address; and
indicating an element is a hook-element by providing a negative number as the address.
3. The method according to claim 1 , wherein the being equal to the value of the associated element further comprises being equal to the absolute value of the associated element, and the indicator indicates the element is a hook-element when the value is negative.
4. A hand held portable device, comprising:
RAM memory;
input and output subsystems;
a processor; and
a binary search tree engine implementing a memory management process further comprising:
receiving a request for an allocation of memory comprised of a request size;
searching for an available memory block that satisfies the allocation request, the searching process further comprising:
traversing a binary tree, the tree comprised of elements where each element has between 0 and 2 branches inclusive, a value, and an indicator, the indicator enabled to indicate if an element is further a hook-element, a hook-element comprising a first branch to a linked list and a second branch to an element with a same value as the hook-element, and where each of a plurality of available memory blocks is associated with one element with a size of the associated memory block being equal to the value of the associated element;
comparing the request size to a first value of a first element;
determining if the indictor indicates the first element is a hook-element and if the first value is equal to the request size;
traversing, if the indicator indicates a hook-element and the first value and request size are equal, to a linked list of elements having a same value as the request size;
traversing, if the indicator indicates a hook-element and the first value and request size are unequal, to an element having a same value as the request size;
traversing, if the indicator did not indicate a hook-element and the request size is larger than first value, to a branch comprised of elements with values all greater than the first value;
traversing, if the indicator did not indicate a hook-element and the request size is smaller than first value, to a branch comprised of elements with values all smaller than the first value;
continuing determining and then traversing until an element that is not a hook-element and has a same value as the request value is reached, being a request element thereby;
removing the request element from the tree; and
making the memory block associated with the removed element available for the memory request.
5. The device according to claim 4 , further comprising a transceiver and an antenna.