KJB
|
a balanced binary search tree storing subtree sums in each node. More...
#include <redblack.h>
Classes | |
class | const_iterator |
iterator class for a tree – lets you access node locators. More... | |
Public Types | |
typedef SATELLITE_TYPE | Sat_tp |
typedef DijkstraPriorityQueue < SATELLITE_TYPE >::Key_tp | Key_tp |
typedef DijkstraPriorityQueue < SATELLITE_TYPE >::Loc_tp | Loc_tp |
Public Types inherited from kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE > | |
typedef SATELLITE_TYPE | Sat_tp |
type of satellite data More... | |
typedef float | Key_tp |
type that we use for keys More... | |
typedef size_t | Loc_tp |
type that we use for locators More... | |
Public Member Functions | |
Redblack_subtree_sum () | |
default ctor More... | |
void | clear () |
destroy the tree or the linear array. More... | |
Redblack_subtree_sum (const Redblack_subtree_sum< SATELLITE_TYPE > &tree) | |
copy ctor (same locators will work in this one too) More... | |
Redblack_subtree_sum & | operator= (const Redblack_subtree_sum< SATELLITE_TYPE > &tree) |
assignment operator (same locators will work in this one too) More... | |
~Redblack_subtree_sum () | |
dtor clears the structure More... | |
Loc_tp | insert (const Key_tp &key, const Sat_tp &sat) |
insert a new key+value pair in the dictionary More... | |
Loc_tp | ins_max_key (const Sat_tp &sat) |
the following is a hack to mimic StochasticPriorityQueue More... | |
void | debug_print (std::ostream &) const |
stub: remove print code when not checking aggressively More... | |
bool | tree_valid_in_nlogn_time () const |
scan dictionary in linear time to verify invariants are valid More... | |
bool | find_key (const Key_tp &key, Sat_tp *sat_out, Loc_tp *loc_out) |
search for a key in the dictionary; return first one. More... | |
bool | erase_key (const Key_tp &query_key, Sat_tp *sat_out) |
erase a key+value pair from the dictionary More... | |
bool | access_loc (Loc_tp query_loc, Key_tp *key_out, Sat_tp *sat_out) const |
access a record via its locator, a constant-time operation. More... | |
bool | erase_loc (Loc_tp query_loc) |
remove the record indicated by query_loc, or return false if bad More... | |
Loc_tp | loc_min () const |
return the locator for the record with the minimum key, or 0 More... | |
Loc_tp | loc_max () const |
return the locator for the record with the maximum key, or 0 More... | |
size_t | size () const |
return the number of key+value pairs in the dictionary. More... | |
bool | is_empty () const |
return whether the size is zero More... | |
bool | rekey_loc (Loc_tp query_loc, const Key_tp &newkey) |
change the key value for a node to a new value, O(log n) time More... | |
Key_tp | root_sum () const |
return subtree sum at root node (i.e., the sum of all keys). More... | |
Loc_tp | loc_using_cumulative_key_sum (Key_tp cumulative_keysum) const |
fetch a node based on inorder cumulative sum of tree keys More... | |
Loc_tp | Dijkstra_extraction () const |
hack proxy to make this and a stochastic pri queue work alike More... | |
const_iterator | begin () const |
const_iterator | end () const |
Public Member Functions inherited from kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE > | |
virtual | ~DijkstraPriorityQueue () |
obligatory virtual destructor More... | |
Friends | |
class | const_iterator |
a balanced binary search tree storing subtree sums in each node.
This is a so-called Red-Black tree, thus it maintains a height of O(log n) where n is the number of nodes.
A Red-Black Tree is a binary search tree augmented with one bit of "color" information associated with each node. Each node is either red or black. Keys are stored only in internal nodes, not in the leaves. The critical properties of a Red-Black tree are these:
Every red node has two black children.
If p, q are simple descending paths starting from the same node and ending at leaves, then p and q include the same number of black nodes.
The final invariant guarantees that the tree has a well-defined value called the black height, which is the number of black nodes from the root to any leaf, along a simple path of descent.
The tree not only maintains the Red-Black invariants, but it stores real-valued keys and stores in each node the sum of the keys in the subtree rooted at that node.
This is a class template, actually. The template is parameterized by one type, the satellite data that you want to store in each node. The type for the satellite data must be copyable and it must have a default constructor, just like the requirements for standard containers.
This dictionary allows the user to insert using the same key value as already found in the tree. Both sets of satellite data will be stored. An erase operation on a key that exists in the tree multiple times will cause one of those nodes to be extracted and removed, but it is impossible to say which one it will be (it does not in general follow a LIFO or FIFO rule).
Functionally, a "locator" is an opaque pointer (see References). This tree offers the user locators that point to the nodes in the tree. The user can read, modify, and delete nodes using their corresponding locators.
The tree data structure returns a locator every time a new record is created and inserted into the tree. The user can then read the node (
The ability to alter the key value of a node is a specific requirement of Dijkstra's algorithm (and was the motivation for providing this feature).
Operationally, a locator is an integer of type size_t. Locator numbers may be recycled. When the user deletes a node, that node's locator number could be used again for a future insertion. Thus, do not use a stale locator. (That advice applies to any pointer!)
The tree also offers a bidirectional const_iterator, which can be used to enumerate the locators of the nodes.
This tree is (in a sense) organized so that both keys and satellite data are stored in the internal nodes of the tree, not in the leaves. All leaves are represented by a single node called "nil." All nodes also have a parent pointer, which is not useful for the root node and for the nil node (their parent pointers should equal zero). During a deletion, however, the nil node might have its parent pointer set to the parent of the deleted node.
In an attempt to simplify the code, I've made the class store its nodes in a linear array for dictionaries of size TREE_THRESH or smaller, currently set at a size of seven nodes. So this doesn't really build a red-black tree unless there are eight or more internal nodes to be kept.
The Red-Black tree is due to Bayer, Guibas and Sedgewick. I'm basing my code on the presentation found in CLR, but I didn't follow their pseudocode.
CLR = Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press.
The locator pattern is described in Goodrich and Tamassia, Data Structures and Algorithms in Java, section 6.4, John Wiley, 1998.
typedef DijkstraPriorityQueue< SATELLITE_TYPE >::Key_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Key_tp |
typedef DijkstraPriorityQueue< SATELLITE_TYPE >::Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Loc_tp |
typedef SATELLITE_TYPE kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Sat_tp |
|
inline |
default ctor
|
inline |
copy ctor (same locators will work in this one too)
|
inline |
dtor clears the structure
|
inlinevirtual |
access a record via its locator, a constant-time operation.
[in] | query_loc | Locator to look for in the tree. |
[out] | key_out | Optional pointer at which, if not eq. to NULL, this will write the record's key value. |
[out] | sat_out | Optional pointer at which, if not eq. to NULL, this will write the record's satellite field. |
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
|
inlinevirtual |
destroy the tree or the linear array.
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
stub: remove print code when not checking aggressively
|
inlinevirtual |
hack proxy to make this and a stochastic pri queue work alike
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
|
inline |
erase a key+value pair from the dictionary
[in] | query_key | Key for which to search. If multiple key+value pairs have been inserted in the dictionary using the same key, it is undefined which one will be found. |
[out] | sat_out | Optional pointer to which, if not equal to NULL, this will write the satellite data when and if the key value is found. |
|
inlinevirtual |
remove the record indicated by query_loc, or return false if bad
[in] | query_loc | Locator of record to remove |
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
search for a key in the dictionary; return first one.
[in] | key | key value in node to be searched for. If multiple (key,value) pairs have been inserted in the dictionary using the same key, it is undefined which one will be found. Also remember the problems that occur when searching for exact floating-point equality. |
[out] | sat_out | Optional output storage for satellite data. If equal to NULL, satellite data is ignored. |
[out] | loc_out | Optional output storage for locator of this node (biased). If equal to NULL, locator is ignored. |
If the key is not found, the output locations are not written.
|
inlinevirtual |
the following is a hack to mimic StochasticPriorityQueue
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inlinevirtual |
insert a new key+value pair in the dictionary
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inlinevirtual |
return whether the size is zero
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
return the locator for the record with the maximum key, or 0
|
inline |
return the locator for the record with the minimum key, or 0
|
inline |
fetch a node based on inorder cumulative sum of tree keys
cumulative_keysum | value we want to find or minimally exceed. |
This method is most useful when keys are all positive. Keys do not need to be distinct. If keys are nonpositive, screwy things will probably occur.
Let n denote a node and n.k denote its key. Neither n or k will be used to represent integers (but i, j will).
Let n1,n2,n3,... be an inorder listing of nodes, such that n1.k <= n2.k <= n3.k <= ...
Now consider the cumulative sum of keys starting with n1: s_0 = 0; s_1 = s_0 + n1.k; s_2 = s_1 + n2.k; ... As a special case, let S equal the sum of all nodes' keys.
If it exists, this method finds a value j such that s_{j-1} < cumulative_keysum <= s_j and if such a value exists, this returns the locator of node nj.
Degenerate cases:
|
inline |
assignment operator (same locators will work in this one too)
|
inlinevirtual |
change the key value for a node to a new value, O(log n) time
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
return subtree sum at root node (i.e., the sum of all keys).
|
inlinevirtual |
return the number of key+value pairs in the dictionary.
Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.
|
inline |
scan dictionary in linear time to verify invariants are valid
|
friend |