Abstract:
A new method of sorting and indexing data using a new data structure is introduced. The new data structure is a version of a binary search tree that provides indexing operations on complex data structures. The indexing is achieved by storing additional information on comparison of the keys in every node of a binary search tree. In most cases this information helps avoid repeated comparisons of the initial elements or completely excludes comparison of keys. The new data structure permits rotations and deleting of its nodes using methods of restoring the structure before, during or after the operations

Description:
FIELD OF THE INVENTION  
         [0001]    This invention relates to a computer implementable method of sorting and indexing of complex data.  
         BACKGROUND OF THE INVENTION  
         [0002]    The known balanced binary search trees such as AVL tree or red-black tree provide fast sorting and search for simple data with indivisible operation of comparison. However, for more complex data such as character strings, the efficiency of direct application of binary search tree is lowered, as it is necessary to duplicate comparisons of all initial characters up to the position of the difference of the keys on all levels of the tree.  
         SUMMARY OF THE INVENTION  
         [0003]    The new method of sorting and indexing complex data is based on the properties of the new data structure, called Position Tree, that gives the possibility to use benefits of binary search trees and balanced binary search trees while working with complex data types.  
           [0004]    Position Tree stores results of comparison of complex data in the nodes of a binary tree. The data structure helps avoiding repeated comparisons and allows standard rotations and deletion of nodes with minor modifications of the algorithms.  
           [0005]    Simplicity and unification of Position Tree make it useful in application programs for fast sorting and search of strings and many other complex types of data including database tables. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]    The present invention will now be described, by way of example only, with reference to the following drawings:  
         [0007]    [0007]FIG. 1. A Position Tree node diagram.  
         [0008]    [0008]FIG. 2. Example of Pascal definition of Position Tree node.  
         [0009]    [0009]FIG. 3. Example of Pascal implementation of P function for C-strings.  
         [0010]    [0010]FIG. 4. Diagram of insertion algorithm.  
         [0011]    [0011]FIG. 5 a - 5   d . Insertion of nodes into Position Tree.  
         [0012]    [0012]FIG. 6. The parent node is an Ancestor Node.  
         [0013]    [0013]FIG. 7. The parent node is not an Ancestor Node.  
         [0014]    [0014]FIG. 8. Diagram of search algorithm.  
         [0015]    [0015]FIG. 9. Example of Pascal implementation of helper function that can be used for navigation in Position Tree.  
         [0016]    [0016]FIG. 10. Example of Pascal implementation of the search algorithm.  
         [0017]    [0017]FIG. 11 a ,  11   b . Examples of using of the definition of Twin Node.  
         [0018]    [0018]FIG. 12. Example of Pascal implementation of the Twin Node search and update algorithm.  
         [0019]    [0019]FIG. 13. Example of Pascal implementation of the exchanging Positions algorithm.  
         [0020]    [0020]FIG. 14 a ,  14   b . Example of Single Rotation Left procedure in Position Tree.  
         [0021]    [0021]FIG. 15 a ,  15   b . Example of Single Rotation Left with exchanging Position values.  
         [0022]    [0022]FIG. 16 a ,  16   b . Example of Single Rotation Left with updating of Twin Node.  
         [0023]    [0023]FIG. 17 a ,  17   b . Diagrams of single rotations of nodes in Position Tree.  
         [0024]    [0024]FIG. 18. Example of Pascal implementation of the single rotation algorithms.  
         [0025]    [0025]FIG. 19. Diagram of selection of replacement node for the deleting one.  
         [0026]    [0026]FIG. 20. Example of Pascal implementation of calculating the Position values for delete node algorithm.  
         [0027]    [0027]FIG. 21. Example of Pascal implementation of the selecting Replacement Node algorithm.  
         [0028]    [0028]FIG. 22 a ,  22   b . Diagrams of updating nodes during deletion of a node.  
         [0029]    [0029]FIG. 23 a ,  23   b . Examples of Pascal implementation of updating Position values during deleting of a node from Position Tree.  
         [0030]    [0030]FIG. 24. Example of Pascal implementation of the delete node algorithm.  
         [0031]    [0031]FIG. 25 a ,  25   b . Example of deletion of node from Position Tree.  
         [0032]    [0032]FIG. 26 a ,  26   b . Example of deletion of node with updating Position values in the right sub-tree. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
     Definitions  
       [0033]    First of all, we have to define, which data we can use to construct the Position Tree. Besides the already mentioned character strings, one can use complex types of data, presenting the sets of elements, arranged in enumerated positions. Elements in different positions can be of different types, including the described one. Elements in different positions or even in all positions can also be of the same type.  
         [0034]    The comparison of two of such complex values is defined as consequent comparison of the elements in corresponding positions, starting from the first position, until the first pair of differing elements is found. The result of comparing this pair determines the general result of comparison of complex values. In the case of equality of the elements in all the positions, the quantities are considered to be identical.  
         [0035]    Now we can give a formal definition of the described data type.  
         [0036]    Definition 1.  
         [0037]    We shall say that data set C with elements {c 1 , c 2 , . . . c n } is of complex type if it fulfils the following conditions:  
         [0038]    [0038] 1 . Each element c of C is an array of m sub-elements c[i], where position i:1≦i≦m;  
         [0039]    [0039] 2 . There are standard comparison operations on sub-elements defined for each position i of C;  
         [0040]    [0040] 3 . There is a comparison operation defined for all pairs of elements (c x , c y ) from C:  
         [0041]    a. Let D be the set of all d, 1≦d≦m: c x [d]≠c y [d];  
         [0042]    b. If D is empty, then c x =c y ,  
         [0043]    c. If D is not empty and d min  is a minimal element of D:  
         [0044]    i. if c x [d min ]&gt;c y [d min ], then c x &gt;c y ,  
         [0045]    ii. if c x [d min  ]&lt;c y [d min ], then c x &lt;c y .  
         [0046]    Note  1 .  
         [0047]    Sub-elements c 
         [0048]    of elements c can be of different types for different positions. They also can be of the same type for some or even for all positions of C.  
         [0049]    Note 2.  
         [0050]    It is possible to expand the definition to include sets of arrays with different length by introducing an “empty” sub-element (fictitious or real) E for each position in C with the next properties:  
         [0051]    [0051] 1 . E is equal to itself;  
         [0052]    [0052] 2 . E is less than any other sub-element of the position.  
         [0053]    Note 3.  
         [0054]    The actual data type of the position value itself is not important for the methods of Position Tree.  
         [0055]    Further on, speaking about complex type of data, we will intend the type, which will comply with the definition and the notes above.  
         [0056]    Let us consider some examples of data set, which are suitable for constructing the Position Tree:  
         [0057]    [0057] 1 . A set of n strings of the same length: S={s 1 , s 2 , . . . , s n }. In this simplest case, the sub-elements in all positions of the strings (symbols) are of the same type.  
         [0058]    [0058] 2 . Sets of strings of different length. A special ‘zero’ symbol can be used for defining strings&#39; ends.  
         [0059]    [0059] 3 . A table of relational database. Elements c are the records of the given table, the positions define field numbers. We can also expand the notion of position, including in it the positions within the fields of complex types, if such are present.  
         [0060]    In order to build the Position Tree, we need to save the comparison result and the position number of the first two differing elements of the compared keys. The signs: ‘+’ for ‘greater’, ‘−’ for ‘less’, ‘0’ for ‘equal’ can be used as the result of comparison.  
         [0061]    Definition 2.  
         [0062]    A binary search tree, built on data of complex type, will be called the Position Tree if it complies the following conditions:  
         [0063]    1. There is an attribute defined for each node of the tree, except maybe the root node, that may take on two different values correspondent to greater and less results of comparison;  
         [0064]    2. There is an attribute defined for each node of the tree, except maybe the root node, that may take on the values of the positions of sub-elements within the data.  
         [0065]    Note 4.  
         [0066]    The binary search tree may be not balanced, balanced or near-balanced. One can use AVL tree or Red-Black tree or any other binary search tree to build the Position Tree.  
         [0067]    Definition 3.  
         [0068]    The combination of the two additional attributes of the Position Tree, that represents a signed value of position of sub-elements of complex data, where the sign is ‘+’ for ‘greater’ and ‘−’ for ‘less’ comparison result, we will call Position. We will use the standard comparison operation of signed values for the new data type.  
         [0069]    Let us add the new Position field according to Definition 3 into a binary tree node&#39;s structure. Let us define the new type of node as N={Key, LeftChild, RightChild, Position}, where Key is the value of complex type or the pointer to the value, LeftChild and RightChild are the corresponding pointers to the left and the right child nodes. We shall use the field Position in correspondence with the algorithms, given further.  
         [0070]    In order to present graphically a Position Tree node, it is expedient to use the diagram as shown in FIG. 1, where Nx is the definition of the given node, p is the Position value for the given node, and Ny is its Ancestor Node. The notion Ancestor Node will be defined in the next chapter.  
         [0071]    [0071]FIG. 2 shows an example of Pascal definition of Position Tree node. The key value KeyValue is a Pascal string. The BalanceFactor field can be used in AVL balancing algorithm.  
         [0072]    Definition 4.  
         [0073]    We shall call the Position Tree as being in the Initial State, if no operations were done in it, such as rotations or deleting, which would change relative positions of nodes.  
         [0074]    Let us also introduce a new function we will use in search and insert algorithms.  
         [0075]    Definition 5.  
         [0076]    For any two elements c x , c y  from the set of complex type C (see Definition  1 ), let us define function P(c x , c y , i), 1≦i≦m, in the following way:  
         [0077]    1. Let D be the set of all d, i≦d≦m: c x [d]≠c y [d];  
         [0078]    2. If D is empty then P(c x , c y , i)=0,  
         [0079]    3. If D is not empty and d min  is a minimal element of D:  
         [0080]    a. if c x [d min ]&gt;c y [d min ], then P(c x , c y , i)=d min ;  
         [0081]    b. if c x [d min ]&lt;c y [d min ], then P(c y , c y , i)=−d min .  
         [0082]    [0082]FIG. 3 gives us an example of such a function written on Pascal for C-strings.  
         [0083]    Let us list some evident properties of the function P:  
         [0084]    1. If P(c x ,c y , 1)=p:  
         [0085]    a. p=0         c x =c y ;  
         [0086]    b. p&gt;0         c x &gt;c x &gt;c y ;  
         [0087]    c. p&lt;0         c x &lt;c x &lt;c y ;  
         [0088]    2. If P(c x , c y , 1)=p, then P(c x , c y , q)=p for all q: 1≦q≦|p|;  
         [0089]    3. If P(c x , c z , 1)=p and P(c y , c z , 1)=q, where p and q have the same sign:  
         [0090]    a. if p&lt;q         c x &gt;c y ;  
         [0091]    b. if p&gt;q         c x &lt;c y .  
         [0092]    Here and further on we denote absolute value of a value p as |p|. The absolute value of Position represents a position of sub-element regardless of the comparison sign attribute.  
         [0093]    The last two properties  3   a  and  3   b  are the most useful for us. Using them, we can substitute the by-elements keys&#39; comparison by a simple comparison of corresponding result values of P function. This makes the main idea of creation of Position Tree.  
         [0094]    Let us consider the examples of usage of the introduced function on a set of three-character strings S={s 1 , s 2 , . . . , s n }. A usual procedure of by-character comparison, starting from the i-th character, is used as function P(s x , s y , i):  
         [0095]    1. P(“AAA”, “AAA”, 3)=0;  
         [0096]    2. P(“ABC”, “AAA”, 2)=P(“ABC”, “AAA”, 1)=2;  
         [0097]    3. P(“AAC”, “AAA”, 2)=P(“AAC”, “AAA”, 1)=3;  
         [0098]    4. P(“AAC”, “AAA”, 2) &gt;P(“ABC”, “AAA”, 2) &gt;0         “AAC”&lt;“ABC”.  
       Algorithm of Insertion  
       [0099]    [0099]FIG. 4 shows the diagram of the insertion of a new node into the Position Tree. To insert a new node for the key value Key into the Position Tree, which is in the Initial State, it is necessary to perform the following steps (FIG. 4):  
         [0100]    1. Set new variable Position←1. Set current node N to the root node of the tree.  
         [0101]    2. If N is empty insert the new node I, set I.Positions Position←and exit  
         [0102]    3. If N is not empty compare Position and N. Position:  
         [0103]    a. If Position&lt;N.Position set N←N.RightChild;  
         [0104]    b. If Position&gt;N.Position set N←N.LeftChild;  
         [0105]    c. If Position=N.Position set Position←P(Key, N.Key, |N.Position|) and do:  
         [0106]    i. If Position=0 do “on equal values” and exit;  
         [0107]    ii. If Position&gt;0 set N←N. RightChild;  
         [0108]    iii. If Position&lt;0 set N←N. LeftChild.  
         [0109]    4. Continue from step 2.  
         [0110]    [0110]FIGS. 5 a - 5   d  illustrate the insertion operation on a set of three-character strings. We have considered the creation of Position Tree with consecutive insertion of strings ‘AAA’, ‘AAC’, ‘ABC’ and ‘AAB’ by using the comparison rules, taken from the example above.  
         [0111]    [0111]FIG. 5 a  shows insertion of the root node for the key value ‘AAA’. The Position field of the new node N 1  is assigned the initial value 1.  
         [0112]    [0112]FIG. 5 b  shows insertion of the second node for the key value ‘AAC’. The following steps were performed:  
         [0113]    1. The initial value of Position field of the node to be inserted equals to the value of Position field of the root node N 1 . We perform comparison of nodes&#39; keys, starting from the first character. ‘AAC’ is greater than ‘AAA’ in the third character.  
         [0114]    2. The new node N 2  is placed to the right of the root node with the current value of the Position field equal to 3.  
         [0115]    [0115]FIG. 5 c  shows insertion of the third node for the key value ‘ABC’. The following steps were performed:  
         [0116]    1. Comparison the new key value with the value of the root node N 1 . ‘ABC’ is greater than ‘AAA’ in the second character.  
         [0117]    2. We save the current value of Position, equal to 2, and proceed to the second node N 2 .  
         [0118]    3. Comparison the obtained Position value with the value of Position field of the second node.  
         [0119]    4. The current Position value (equal to 2) is less than Position field of the second node (equal to 3), thus the third node N 3  is to be placed to the right of the second, and no comparison of their keys is made.  
         [0120]    [0120]FIG. 5 d  shows insertion of the fourth node for the key value ‘AAB’. The following steps were performed:  
         [0121]    1. Comparison the new key value with the value of the root node N 1 . ‘AAB’ is greater than ‘AAA’ in the third character.  
         [0122]    2. As the obtained value 3 is equal to the value of the Position field of the second node N 2 , it is necessary to perform comparison of the key to be inserted with the key of the second node, but starting from the third character.  
         [0123]    3. ‘AAB’ is less than ‘AAC’ in the third character. Consequently the fourth node N 4  is placed to the left of the second with the value of Position field equal to −3.  
         [0124]    Using the given algorithm of insertion, let us introduce a number of new notions, which will be useful for us in future.  
         [0125]    Definition 6.  
         [0126]    The Position Tree node N shell be called the Ancestor Node for some certain node I from the same tree if the tree is in Initial Sate and the result of comparison P(I.Key, N.Key, . . . ) during inserting of node I is saved in the Position field of node I.  
         [0127]    In other words, Ancestor Node is the last node where key comparison with the inserting node has occurred.  
         [0128]    [0128]FIGS. 6 and 7 show that the parent node can either be, or not be the Ancestor Node for the given Position Tree node. The parent node N 2  is at the same time also the Ancestor Node for the node N 3  in FIG. 6. For the node N 3  in FIG. 7: its parent node is node N 2 , while its Ancestor Node is node N 1 .  
         [0129]    Definition 7.  
         [0130]    The chain of nodes of Position Tree, beginning from a certain node, in which each subsequent node is the Ancestor Node for the previous one, will be called the Ancestry Chain for the given node.  
         [0131]    Search Algorithm  
         [0132]    Search algorithm repeats the algorithm of insertion in many respects. The same logic is used in progressing from node to node. In order to find the key value Key in Position Tree, which is in the Initial State, the following steps are to be followed (FIG. 8):  
         [0133]    1. Set new variable Position&lt;1. Set node pointer N to the root node.  
         [0134]    2. If N is empty         search failed, exit.  
         [0135]    3. If N is not empty compare Position and N. Position:  
         [0136]    a. If Position&lt;N.Position set N←N.RightChild;  
         [0137]    b. If Position&gt;N. Position set N←N.LeftChild;  
         [0138]    c. If Position=N.Position set Position←P(Key, N.Key, |Position|) and do:  
         [0139]    i. If Position=0         N. Key=Key, node found, exit,  
         [0140]    ii. If Position&gt;0 set N←N. RightChild;  
         [0141]    iii. If Position&lt;0 set N←N. LeftChild.  
         [0142]    4. Continue from step 2.  
         [0143]    [0143]FIG. 9 shows an example of Pascal implementation of step 3 of the algorithm as a separate function. The utilization of the function is illustrated in FIG. 10, where we can see the full search algorithm for Pascal strings. The search starts from the root node RootNode and returns the node with KeyValue key value if such a node exists.  
       Position Tree Properties  
       [0144]    In this chapter let us examine some characteristics of Position Tree that is in Initial State.  
         [0145]    We have included in the first group those properties that affect the speed of insertion and search operations. We denote the current value of the Position variable from corresponding algorithms as p and make the following obvious statements:  
         [0146]    1. While comparing two keys during insertion or search it is not necessary to compare key elements up to the elements in positions |p|, |p|≧1.  
         [0147]    2. |p| value does not decrease while progressing from one tree node to another.  
         [0148]    3. If the value of the Position field of the current node is not equal to p, comparison of keys is not required at all.  
         [0149]    The above-noted properties of the Position Tree show that it is possible to accelerate the search and insertion of keys by decreasing the number of compared key elements or by replacing the comparison of keys with the faster comparison of integer Position fields.  
         [0150]    Now let us examine the properties related to the balancing and deleting of nodes from the Position Tree. While during insertion and search the nodes within the tree are not repositioned, this is not the case with the balancing and deletion procedures. In addition, any repositioning of nodes changes the order of key comparison for further operations and hence disturbs all logic of the using of Position fields values.  
         [0151]    It appears that in order to continue using the Position Tree with balancing and removal procedures there is a way of changing the values of Position fields for a small number of nodes in such manner that the resulting structure will appear as if it were formed using only node insertion without repositioning of the same. We will refer to such changes as the restoring of the Initial State of the given Position Tree.  
         [0152]    In order to facilitate the understanding of the algorithms of the restoring of the Initial State presented below, let us examine some features of the Position fields of the Position Tree nodes:  
         [0153]    1. For parent node PN and its child nodes RC=PN.RightChild and LC=PN.LeftChild:  
         [0154]    a. if RC.Position≧PN.Position         PN is Ancestor Node for RC;  
         [0155]    b. if LC.Position≦PN.Position         PN is Ancestor Node for LC;  
         [0156]    2. Denoting the Position field&#39;s value of node N as p:  
         [0157]    a. if p&gt;0          |LS.Position|≧|p| for all nodes LS from the left subtree of N;  
         [0158]    b. if p&lt;0          |RS.Position|≧|p| for all nodes RS from the right subtree of N.  
         [0159]    Another important feature of the Position Tree requires some preliminary definitions.  
         [0160]    Definition 8.  
         [0161]    Let us say that the node of the binary tree is located between two other nodes of this tree—M and N, if it belongs to the chain of nodes connecting nodes M and N.  
         [0162]    Definition 9.  
         [0163]    We will call Position Tree node M belonging to one of the sub-trees of node N the Twin Node of node N if the following conditions are met:  
         [0164]    1. M.Position=N.Position;  
         [0165]    2. There are no such nodes X between N and M that |X.Position|=|N.Position|.  
         [0166]    [0166]FIGS. 11 a  and  11   b  show examples of using the definition of the Twin Node. Node N 3  is a Twin Node for node N 1  in FIG. 11 a , but it is not a Twin Node for node N 1  in FIG. 11b because of the node N 2  with the same absolute value of Position between N 1  and N 3 .  
         [0167]    It is easily verifiable that the following property is true for Twin Nodes:  
         [0168]    1. For all nodes N with N.Position&gt;0: there is no Twin Node for N in the left sub-tree of N;  
         [0169]    2. For all nodes N with N.Position&lt;0: there is no Twin Node for N in the right sub-tree of N.  
         [0170]    Later on we will need Twin Node search algorithm. To find the Twin Node T for node N in one of the left or right sub-tree of node N we will use the function FindTwinNode(CN, Position), where CN is one of N.RightChild or N.LeftChild and Position is N.Position:  
         [0171]    1. Set T←CN;  
         [0172]    2. If T is empty=         search failed, exit;  
         [0173]    3. If T is not empty then do compare Position and T Position:  
         [0174]    3.1. If Position=T.Position         node found, exit,  
         [0175]    3.2. If Position&gt;T.Position set T←T.LeftChild;  
         [0176]    3.3. If Position&lt;T.Position set T←T.RightChild;  
         [0177]    4. Continue from step 2.  
         [0178]    Another algorithm that is used in the transformations related to the restoring of Initial State of Position Tree determines the rules for the repositioning of Position fields values. Let us define ExchangePositions(FirstNode, SecondNode) procedure for nodes FirstNode and SecondNode as:  
         [0179]    1. Set new parameter Position←FirstNode.Position;  
         [0180]    2. Set FirstNode.Position←−SecondNode.Position;  
         [0181]    3. Set SecondNode.Position←Position.  
         [0182]    Note the asymmetry of this procedure: one of the nodes receives Position field value from another with the opposite sign.  
         [0183]    Examples of the implementation of the methods are shown in FIGS. 12 and 13.  
       Rotations  
       [0184]    As we noted above, node rotations performed for the balancing of the binary tree disturb the sequence of keys comparison, which makes it impossible to use insertion and search procedures in the Position Tree. The purpose of the algorithms presented in this chapter is to restore the Initial State of Position Tree when balancing rotations are used.  
         [0185]    Before writing proper algorithms let us examine possible variants of changes in Position fields using Single Rotation Left as an example.  
         [0186]    [0186]FIGS. 14 a  and  14   b  show the simplest case of Single Rotation Left in node N 2 . The value of the Position field of node N 2  (equal to 3) is greater than the value of the Position field of node N 3  (equal to 2) in FIG. 14 a . In this case no changes in the Position fields are required (FIG. 14 b ).  
         [0187]    [0187]FIGS. 15 a  and  15   b  show an example of Single Rotation Left in node N 2  with exchanging Position values for the nodes. The value of the Position field of node N 2  (equal to −1) is less than the value of the Position field of node N 3  (equal to 2) in FIG. 15 a . In this case the repositioning of the Position values of nodes N 2  and N 3  is required using the ExchangePositions(N 2 , N 3 ) algorithm (FIG. 15 b ).  
         [0188]    [0188]FIGS. 16 a  and  16   b  show an example of Single Rotation Left in node N 1  with updating Twin Node sign. Changes in the values of Position fields for nodes N 1  and N 2  (FIG. 16 a ) lead to the violation of the Twin Node rule. After the rotation and the application of the procedure ExchangePositions(N 1 , N 2 ) we find that node N 3  located in the right sub-tree of node N 1  has the same value of the Position field as node N 1  (equal to −3 before rotation). In this case it is necessary to change the sign of the Position field of node N 3  to the opposite one (FIG. 16 b ).  
         [0189]    Similar examples can be easily constructed for Single Rotation Right. Double rotations may be presented as a sequence of single rotations and do not need to be examined separately.  
         [0190]    This is the algorithm of Single Rotation Left in node N with the renewal of the Initial State of Position Tree (FIG. 17 a ):  
         [0191]    1. Set new pointer RN←N.RightChild;  
         [0192]    2. Do standard Single Rotation Left procedure in node N;  
         [0193]    3. If RN. Position≧N. Position do:  
         [0194]    3.1. Do ExchangePositions(N, RN);  
         [0195]    3.2. Find T←FindTwinNode(N.RightChild, N.Position);  
         [0196]    3.3. If T is not empty set T.Position←−T.Position.  
         [0197]    This algorithm can be written for Single Rotation Right as follows (FIG. 17 b ):  
         [0198]    1. Set new pointer LN←N.LeftChild;  
         [0199]    2. Do standard Single Rotation Right procedure in node N;  
         [0200]    3. If LN. Position≦N.Position do:  
         [0201]    3.1. Do ExchangePositions(N, LN);  
         [0202]    3.2. Find T FindTwinNode(N.LeftChild, N.Position);  
         [0203]    3.3. If T is not empty set T.Position←−T.Position.  
         [0204]    Examples of Pascal implementation of the methods are shown in FIG. 18.  
       Deletion Algorithm  
       [0205]    The deletion of a node from the Position Tree using the standard algorithm for the binary tree may disturb the Initial State of the given Position Tree too. In this chapter we shall examine transformations that are necessary for the restoring of Initial State in the course of the deletion.  
         [0206]    Let us denote the node to be deleted as N. At first let us examine the most complete case when both sub-trees of N are not empty and the sub-trees of nodes N.LeftChild and N.RightChild are not empty either. Let us denote the preceding and the next nodes for node N as PN and NN respectively (please remember that the preceding node is the rightmost node from Node N.LeftChild, and the next node is the leftmost one from N.RightChild).  
         [0207]    The known algorithm for the deletion of a node from the binary tree involves moving any of PN or NN to the location of the deleted node N. We will denote the node selected for the replacement as RN. It turns out that for Position Tree it is important which node is used for the replacement—PN or NN.  
         [0208]    Indeed, if |P(N.Key, RN.Key, 1)| is maximum on {PN, NN}, the replacement can not affect the nodes from the opposite sub-tree of node N because the difference between N and RN keys manifests in a more remote position than the one between the key of node N and any node from the opposite sub-tree.  
         [0209]    To choose the node between PN and NN with the above condition, we can use the function SelectReplacementNode(N) (FIG. 19):  
         [0210]    1. Calculate MaximumRightPositivePosition value as maximum Position on nodes R, where R is set of all those nodes between N and NN and NN itself, where Position&gt;0. Set MaximumRightPositivePosition=0 if R is empty;  
         [0211]    2. Calculate MinimumLeftNegativePosition value as minimum Position on nodes L, where L is set of all those nodes between N and PN and PN itself, where Position&lt;0. Set MinimumLeftNegativePosition=0 if L is empty;  
         [0212]    3. Compare MaximumRightPositivePosition and |MinimumLeftNegativePosition|:  
         [0213]    3.1. If  
         [0214]    MaximumRightPositivePosition&gt;|MinimumLeftNegativePosition|, then set RN←NN;  
         [0215]    3.2. If  
         [0216]    MaximumRightPositivePosition&lt;|MinimumLeftNegativePosition|, then set RN←PN;  
         [0217]    3.3. If  
         [0218]    MaximumRightPositivePosition=|MinimumLeftNegativePosition|, then set RN to any of PN or NN;  
         [0219]    Examples of Pascal code for calculating the MaximumRightPositivePosition and MinimumLeftNegativePosition values are shown in FIG. 20. FIG. 21 shows an example of the full implementation of selection replacement node algorithm.  
         [0220]    The second characteristic of the deletion is that the moving node RN to the place of node N disturbs the sequence of the comparison of keys for the nodes belonging to Ancestry Chain of RN and located between N and RN. Therefore, we have to update Position field values for all the nodes.  
         [0221]    Apart from that it is necessary to verify the Twin Node rule for every change in the value of Position fields as we did in the rotation algorithms.  
         [0222]    Let us write the procedure UpdateLeftSubtree(N, PN) for RN=PN (FIG. 22 a ):  
         [0223]    1. Set new pointer P←parent node for PN;  
         [0224]    2. Do following steps:  
         [0225]    2.1. If P=N, then continue from step 3;  
         [0226]    2.2. If PN. Position≧P. Position, then do:  
         [0227]    2.2.1. Do ExchangePositions(P, PN);  
         [0228]    2.2.2. Find T←FindTwinNode(P.RightChild, P.Position);  
         [0229]    2.2.3. If T is not empty, then set T.Position←−T.Position;  
         [0230]    2.3. Set P←parent node for P, continue from step 2.1;  
         [0231]    3. If PN.Position&lt;N.Position, then set PN.Position←N.Position.  
         [0232]    Similar procedure UpdateRightSubtree(N, NN) for RN=NN (FIG. 22 b ):  
         [0233]    1. Set new pointer P←parent node for NN;  
         [0234]    2. Do following steps:  
         [0235]    2.1. If P=N, then continue from step 3;  
         [0236]    2.2. If NN.Position≦P.Position, then do:  
         [0237]    2.2.1. Do ExchangePositions(P, NN);  
         [0238]    2.2.2. Find T←FindTwinNode(P.LeftChild, P.Position);  
         [0239]    2.2.3. If T is not empty, then set T.Position←−T.Position;  
         [0240]    2.3. Set P←parent node for P, continue from step 2.1;  
         [0241]    3. If NN.Position&gt;N.Position, then set NN.Position←N.Position.  
         [0242]    [0242]FIGS. 23 a  and  23   b  show examples of Pascal implementation of the methods.  
         [0243]    After these explanations it can be easily understood how the complete algorithm of deletion of node N from Position Tree with the restoring of Initial State of the Position Tree:  
         [0244]    1. If both subtrees of N are empty, then continue from step 5 with empty RN;  
         [0245]    2. If one of subtrees of N is empty, then set RN to the node left and continue from step 4;  
         [0246]    3. Set RN←SelectReplacementNode(N);  
         [0247]    4. If RN is PN, then do UpdateLeftSubtree(N, RN), else do UpdateRightSubtree(N, RN);  
         [0248]    5. Do standard delete operation for node N using node RN for replacement if RN is not empty.  
         [0249]    An example of delete algorithm implementation is shown in FIG. 24. FIGS. 25 and 26 illustrate various cases of the deletion of a node from Position Tree.  
         [0250]    The value of Position field of the replacement node N 4  (equal to 1) is less than the value of the Position field of the deleted node N 2  (equal to 3) in FIG. 25 a . Hence node N 4  retains the value of its Position field when being moved to the location of node N 2  (FIG. 25 b ).  
         [0251]    [0251]FIG. 26 a  illustrates selecting the replacement node for node N 1 . The following steps where performed:  
         [0252]    1. Calculating maximum right positive Position value (equal 2 in node N 2 ).  
         [0253]    2. Calculating minimum left negative Position value (equal −1 in node N 4 ).  
         [0254]    3. Maximum right positive Position is greater then the absolute value of minimum left negative Position, therefore the replacement node for N 1  is next node (N 3 ).  
         [0255]    [0255]FIG. 26 b  shows deleting of node N 1  from the tree of the FIG. 26 a  with updating its right sub-tree. The following steps where performed:  
         [0256]    1. Selecting replacement node as shown in FIG. 26 a.    
         [0257]    2. Finding and updating Ancestry Chain nodes. Node N 2  belonging to Ancestry Chain of node N 3  assumes the Position value of node N 3  with the opposite sign.  
         [0258]    3. Assigning the Position value for the replacement node. Node N 3  receives the Position field value of the deleted node because the current value of its Position field (equal to 2 after ExchangePositions(N 2 , N 3 )) is greater than the Position field value of node N 1  (equal to 1).