Computer and Information Sciences is a unique and comprehensive review of advanced technology and research in the field of Information Technology. It provides an up to date snapshot of research in Europe and the Far East (Hong Kong, Japan and China) in the most active areas of information technology, including Computer Vision, Data Engineering, Web Engineering, Internet Technologies, Bio-Informatics and System Performance Evaluation Methodologies.
In this paper we are adding partial persistence to a balanced search tree with a worst case constant update time [6] (in the case that the position of the update is given), via the node-copying method [5].
The idea in [6] is to organize the leaves of an (a, b) tree into buckets, with each bucket containing O(h) leaves, where h is the height of tree. A brief description of the structure is as follows: In every bucket, a pointer (called r_pointer) is stored, that points to an ancestor (or to a node “near” an ancestor) of the bucket. When an update occurs inside the bucket, we follow the r_pointer, rebalance the pointed ancestor and set the r_pointer to point one level upwards. After each such step, the bucket is split incrementally and, when the r_pointer reaches the root of the tree, the incremental process completes. Let u be the node pointed by the r_pointer of a bucket. To rebalance u, the following actions are performed: If u has more than b children (we call such a node big), u is split into two small nodes otherwise u is left intact (we call such a node small). In either case, the r_pointer is moved up one level. It is proved in [6] that, starting from an (α, b)-tree, this algorithm produces an (α, 2b)-tree.