home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Misc / CLISP-1.LHA / CLISP960530-sr.lha / src / avl.d < prev    next >
Encoding:
Text File  |  1996-04-15  |  36.7 KB  |  780 lines
  1. # AVL-Bäume für CLISP
  2. # Bruno Haible 25.10.1993
  3.  
  4. # Ziel: Eine Menge von Elementen sortiert zu halten, in der ab und zu
  5. # einmal ein Element dazukommt oder ein Element seinen Sortierschlüssel
  6. # verändert.
  7.  
  8. # ==============================================================================
  9. # Spezifikation:
  10.  
  11. # Von außen ist einzustellen:
  12. # Identifier AVLID :
  13. #   Identifier, der die Inkarnation dieser Package identifiziert
  14. # Typ AVL_ELEMENT :
  15. #   Typ der Elemente, die in einem AVL-Baum eingetragen werden.
  16. # Funktion AVL_EQUAL, mit
  17. #   local boolean AVL_EQUAL (AVL_ELEMENT element1, AVL_ELEMENT element2);
  18. #   stellt fest, ob zwei Elemente als gleich gelten.
  19. #   In einem AVL-Baum dürfen keine zwei Elemente abgespeichert werden, die
  20. #   als gleich gelten. (D.h. kein Element darf doppelt abgespeichert werden.)
  21. # Typ AVL_KEY :
  22. #   Typ des Key, nach dem ein AVL-Baum sortiert wird.
  23. # Funktion AVL_KEYOF, mit
  24. #   local AVL_KEY AVL_KEYOF (AVL_ELEMENT element);
  25. #   liefert den Sortier-Key eines Elements, das in einem AVL-Baum sitzt.
  26. # Funktion AVL_COMPARE, mit
  27. #   local sintL AVL_COMPARE (AVL_KEY key1, AVL_KEY key2);
  28. #   liefert >0 falls key1>key2, <0 falls key1<key2, 0 falls key1=key2.
  29. # NB: Aus AVL_EQUAL(element1,element2) sollte
  30. #     AVL_COMPARE(KEY_OF(element1),KEY_OF(element2)) = 0 folgen,
  31. #     sonst funktionieren avl_member und avl_delete nicht!
  32. # NB: 'signean' statt 'sintL' wäre eleganter, aber evtl. nicht korrekt!
  33. # Dann ist avl.c zu includen.
  34. # Dann kann ein eigener struct-Typ NODE definiert werden:
  35. #   typedef struct NODE { ...; NODEDATA nodedata; ...; } NODE;
  36. #   #define HAVE_NODE  # nur zum Anzeigen, daß NODE definiert wurde
  37. # Dann ist avl.c abermals zu includen.
  38. # Werden einige der Macros NO_AVL_MEMBER, NO_AVL_INSERT[1], NO_AVL_DELETE[1],
  39. # NO_AVL_LEAST, NO_AVL_MOVE, NO_AVL_SORT definiert, so werden die
  40. # entsprechenden Funktionen nicht definiert.
  41.  
  42. # ==============================================================================
  43.  
  44. #ifndef __AVL_D_
  45. #define __AVL_D_
  46.  
  47. # Deklarations-Teil:
  48.  
  49. #ifndef ALLOC
  50.   #ifndef NO_AVL_INSERT
  51.     #define ALLOC(eltype,number)  ((eltype*) malloc((uintL)sizeof(eltype) * (uintL)(number)))
  52.   #endif
  53.   #ifndef NO_AVL_DELETE
  54.     #define FREE(item)  free(item)
  55.   #endif
  56. #endif
  57.  
  58. #ifndef AVL
  59.   # Eine Art "AVL-Package" für Identifier von Typen und Funktionen:
  60.   #define AVL(incarnation,identifier)  CONCAT4(avl_,incarnation,_,identifier)
  61. #endif
  62.  
  63. #define NODE       AVL(AVLID,node)
  64. #define ELEMENT    AVL_ELEMENT
  65. #define EQUAL      AVL_EQUAL
  66. #define KEY        AVL_KEY
  67. #define KEYOF      AVL_KEYOF
  68. #define HEIGHT     uintBWL
  69. #define MAXHEIGHT  41
  70. #define COMPARE    AVL_COMPARE
  71.  
  72. #define NODEDATA  \
  73.   struct { struct NODE * left;  # linker Teilbaum                               \
  74.            struct NODE * right; # rechter Teilbaum                              \
  75.            HEIGHT height;       # 1+max(heightof(left),heightof(right))         \
  76.            ELEMENT value;       # an der Spitze dieses Baumes stehendes Element \
  77.          }
  78.  
  79. #else
  80.  
  81. # ------------------------------------------------------------------------------
  82. # Implementations-Teil:
  83.  
  84. #define TYPEDEF  typedef  # kleiner Trick, um TRADDECL zu überlisten
  85.  
  86. #ifndef HAVE_NODE
  87.   typedef struct NODE { NODEDATA nodedata; } NODE;
  88. #endif
  89.  
  90. # Ein AVL-Baum ist entweder leer oder ein NODE.
  91. # Der leere Baum hat die Höhe 0, ein NODE hat als Höhe das Maximum der Höhen
  92. # der beiden Teilbäume + 1.
  93.   #define EMPTY  ((NODE *) 0)
  94.   #define heightof(tree)  ((tree)==EMPTY ? 0 : (tree)->nodedata.height)
  95.  
  96. # Invarianten eines jeden AVL-Baumes:
  97. # 1. Die Höhe eines jeden NODE ist korrekt berechnet:
  98. #    node.height = 1+max(heightof(node.left),heightof(node.right))
  99. # 2. Die Höhen der Teilbäume eines jeden NODE unterscheiden sich um höchstens 1:
  100. #    | heightof(node.left) - heightof(node.right) | <= 1
  101. # 3. In jedem NODE gilt:
  102. #    forall x in node.left : COMPARE(KEYOF(x.value),KEYOF(node.value)) <= 0,
  103. #    forall x in node.right : COMPARE(KEYOF(x.value),KEYOF(node.value)) >= 0.
  104. # Ein AVL-Baum der Höhe h hat also mindestens F_(h+2) [Fibonacci-Zahl] und
  105. # höchstens 2^h - 1 Elemente. Also h<=41 (denn ein Baum mit Höhe h>=42 hätte
  106. # mindestens F_44 Elemente, und wegen sizeof(NODE) * F_44 > 2^32 paßt das
  107. # in keinen 32-Bit-Adreßraum.) Daher reicht auch ein uintB für HEIGHT.
  108.  
  109. # Stellt fest, ob in einem Baum ein Element mit einem gegebenen Key vorkommt.
  110. #ifndef NO_AVL_MEMBER
  111.   local boolean AVL(AVLID,member0) (KEY key, NODE * tree);
  112.   local boolean AVL(AVLID,member0) (key,tree)
  113.     var reg3 KEY key;
  114.     var reg1 NODE * tree;
  115.     { loop
  116.         { if (tree == EMPTY) { return FALSE; }
  117.          {var reg2 sintL sign = COMPARE(key,KEYOF(tree->nodedata.value));
  118.           if (sign == 0) # gefunden?
  119.             { return TRUE; }
  120.           if (sign < 0)
  121.             # key < KEYOF(tree->nodedata.value)  --> Suche im linken Teilbaum:
  122.             { tree = tree->nodedata.left; }
  123.             else
  124.             # key > KEYOF(tree->nodedata.value)  --> Suche im rechten Teilbaum:
  125.             { tree = tree->nodedata.right; }
  126.     }   }}
  127. #endif
  128.  
  129. # Stellt fest, ob in einem Baum ein Element vorkommt.
  130. # Setzt voraus, daß keine zwei Elemente mit demselben Key im Baum vorkommen.
  131. #ifndef NO_AVL_MEMBER
  132.   local boolean AVL(AVLID,member) (ELEMENT element, NODE * tree);
  133.   local boolean AVL(AVLID,member) (element,tree)
  134.     var reg4 ELEMENT element;
  135.     var reg1 NODE * tree;
  136.     { var reg3 KEY key = KEYOF(element);
  137.       loop
  138.         { if (tree == EMPTY) { return FALSE; }
  139.          {var reg2 sintL sign = COMPARE(key,KEYOF(tree->nodedata.value));
  140.           if (sign == 0)
  141.             { if (EQUAL(element,tree->nodedata.value)) # gefunden?
  142.                 { return TRUE; }
  143.                 else
  144.                 { return FALSE; }
  145.             }
  146.           if (sign < 0)
  147.             # key < KEYOF(tree->nodedata.value)  --> Suche im linken Teilbaum:
  148.             { tree = tree->nodedata.left; }
  149.             else
  150.             # key > KEYOF(tree->nodedata.value)  --> Suche im rechten Teilbaum:
  151.             { tree = tree->nodedata.right; }
  152.     }   }}
  153. #endif
  154.  
  155. # Stellt die Balance neu her: Beim Einfügen bzw. Löschen eines Elements
  156. # eines Baumes ist eine Folge nodes[0],...,nodes[k-1] von Teilbäumen
  157. # (mit nodes[i+1] = nodes[i] -> (left oder right) für alle i)
  158. # neu auszubalancieren. Da dabei die Wurzel eines Teilbaums sich
  159. # verändern kann, müssen alle nodes[i] nicht NODE*, sondern NODE** sein.
  160.   local void AVL(AVLID,rebalance) (NODE** * nodeplaces_ptr, uintC count);
  161.   local void AVL(AVLID,rebalance) (nodeplaces_ptr,count)
  162.     var reg6 NODE** * nodeplaces_ptr;
  163.     var reg10 uintC count;
  164.     { dotimesC(count,count,
  165.         { var reg5 NODE** nodeplace = *--nodeplaces_ptr;
  166.           var reg2 NODE* node = *nodeplace; # nächster zu balancierender Teilbaum
  167.           var reg3 NODE* nodeleft = node->nodedata.left;
  168.           var reg4 NODE* noderight = node->nodedata.right;
  169.           var reg8 HEIGHT heightleft = heightof(nodeleft);
  170.           var reg9 HEIGHT heightright = heightof(noderight);
  171.           if (heightright + 1 < heightleft)
  172.             # Teilbaum linkslastig, rotiere von links nach rechts: #
  173.             #                                                      #
  174.             #                            *                         #
  175.             #                          /   \                       #
  176.             #                       n+2      n                     #
  177.             #                                                      #
  178.             { var reg7 NODE* nodeleftleft = nodeleft->nodedata.left;
  179.               var reg1 NODE* nodeleftright = nodeleft->nodedata.right;
  180.               var reg10 HEIGHT heightleftright = heightof(nodeleftright);
  181.               if (heightof(nodeleftleft) >= heightleftright)
  182.                 #                                                        #
  183.                 #                *                    n+2|n+3            #
  184.                 #              /   \                  /    \             #
  185.                 #           n+2      n      -->      /   n+1|n+2         #
  186.                 #           / \                      |    /    \         #
  187.                 #         n+1 n|n+1                 n+1  n|n+1  n        #
  188.                 #                                                        #
  189.                 { node->nodedata.left = nodeleftright; nodeleft->nodedata.right = node;
  190.                   nodeleft->nodedata.height = 1 + (node->nodedata.height = 1 + heightleftright);
  191.                   *nodeplace = nodeleft;
  192.                 }
  193.                 else
  194.                 #                                                        #
  195.                 #                *                     n+2               #
  196.                 #              /   \                 /     \             #
  197.                 #           n+2      n      -->    n+1     n+1           #
  198.                 #           / \                    / \     / \           #
  199.                 #          n  n+1                 n   L   R   n          #
  200.                 #             / \                                        #
  201.                 #            L   R                                       #
  202.                 #                                                        #
  203.                 { nodeleft->nodedata.right = nodeleftright->nodedata.left;
  204.                   node->nodedata.left = nodeleftright->nodedata.right;
  205.                   nodeleftright->nodedata.left = nodeleft;
  206.                   nodeleftright->nodedata.right = node;
  207.                   nodeleft->nodedata.height = node->nodedata.height = heightleftright;
  208.                   nodeleftright->nodedata.height = heightleft;
  209.                   *nodeplace = nodeleftright;
  210.                 }
  211.             }
  212.           elif (heightleft + 1 < heightright)
  213.             # Teilbaum rechtslastig, rotiere von rechts nach links:
  214.             # (Analog zu oben, nur 'left' <--> 'right' vertauscht.)
  215.             { var reg7 NODE* noderightright = noderight->nodedata.right;
  216.               var reg1 NODE* noderightleft = noderight->nodedata.left;
  217.               var reg10 HEIGHT heightrightleft = heightof(noderightleft);
  218.               if (heightof(noderightright) >= heightrightleft)
  219.                 { node->nodedata.right = noderightleft; noderight->nodedata.left = node;
  220.                   noderight->nodedata.height = 1 + (node->nodedata.height = 1 + heightrightleft);
  221.                   *nodeplace = noderight;
  222.                 }
  223.                 else
  224.                 { noderight->nodedata.left = noderightleft->nodedata.right;
  225.                   node->nodedata.right = noderightleft->nodedata.left;
  226.                   noderightleft->nodedata.right = noderight;
  227.                   noderightleft->nodedata.left = node;
  228.                   noderight->nodedata.height = node->nodedata.height = heightrightleft;
  229.                   noderightleft->nodedata.height = heightright;
  230.                   *nodeplace = noderightleft;
  231.                 }
  232.             }
  233.           else
  234.             { var reg1 HEIGHT height = # neue Gesamthöhe
  235.                 (heightleft<heightright ? heightright : heightleft) + 1;
  236.               # Gesamthöhe dieses Teilbaumes bleibt unverändert ->
  237.               # die diesen enthaltenden Teilbäume sind bereits ausbalanciert.
  238.               if (height == node->nodedata.height) break;
  239.               node->nodedata.height = height;
  240.             }
  241.         });
  242.     }
  243.  
  244. # Fügt ein Element in einen AVL-Baum ein und liefert den neuen AVL-Baum.
  245. #ifndef NO_AVL_INSERT
  246.   local NODE* AVL(AVLID,insert) (ELEMENT value, NODE* tree);
  247.   local NODE* AVL(AVLID,insert) (value,tree)
  248.     var reg6 ELEMENT value;
  249.     var NODE* tree;
  250.     { var reg5 KEY key = KEYOF(value);
  251.       var reg2 NODE** nodeplace = &tree;
  252.       var NODE** stack[MAXHEIGHT]; # Ein kleiner Privat-Stack
  253.       var reg4 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack
  254.       var reg3 NODE** * stack_ptr = &stack[0]; # stets = &stack[stack_count]
  255.       loop
  256.         { var reg1 NODE* node = *nodeplace;
  257.           if (node == EMPTY) break;
  258.           *stack_ptr++ = nodeplace; stack_count++;
  259.           if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
  260.             # key < KEYOF(node->nodedata.value)  --> im linken Teilbaum einfügen:
  261.             { nodeplace = &node->nodedata.left; }
  262.             else
  263.             # key >= KEYOF(node->nodedata.value)  --> im rechten Teilbaum einfügen:
  264.             { nodeplace = &node->nodedata.right; }
  265.         }
  266.      {var reg1 NODE* new_node = ALLOC(NODE,1);
  267.       new_node->nodedata.left = EMPTY; new_node->nodedata.right = EMPTY; new_node->nodedata.height = 1;
  268.       new_node->nodedata.value = value;
  269.       *nodeplace = new_node;
  270.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  271.       return tree;
  272.     }}
  273. #endif
  274. # Dito, jedoch ohne ALLOC aufzurufen:
  275. #ifndef NO_AVL_INSERT1
  276.   local NODE* AVL(AVLID,insert1) (NODE* new_node, NODE* tree);
  277.   local NODE* AVL(AVLID,insert1) (new_node,tree)
  278.     var reg6 NODE* new_node;
  279.     var NODE* tree;
  280.     { var reg5 KEY key = KEYOF(new_node->nodedata.value);
  281.       var reg2 NODE** nodeplace = &tree;
  282.       var NODE** stack[MAXHEIGHT]; # Ein kleiner Privat-Stack
  283.       var reg4 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack
  284.       var reg3 NODE** * stack_ptr = &stack[0]; # stets = &stack[stack_count]
  285.       loop
  286.         { var reg1 NODE* node = *nodeplace;
  287.           if (node == EMPTY) break;
  288.           *stack_ptr++ = nodeplace; stack_count++;
  289.           if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
  290.             # key < KEYOF(node->nodedata.value)  --> im linken Teilbaum einfügen:
  291.             { nodeplace = &node->nodedata.left; }
  292.             else
  293.             # key >= KEYOF(node->nodedata.value)  --> im rechten Teilbaum einfügen:
  294.             { nodeplace = &node->nodedata.right; }
  295.         }
  296.       new_node->nodedata.left = EMPTY;
  297.       new_node->nodedata.right = EMPTY;
  298.       new_node->nodedata.height = 1;
  299.       *nodeplace = new_node;
  300.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  301.       return tree;
  302.     }
  303. #endif
  304.  
  305. # Entfernt ein Element aus einem AVL-Baum und liefert den neuen AVL-Baum.
  306. # Setzt voraus, daß keine zwei Elemente mit demselben Key im Baum vorkommen.
  307. #ifndef NO_AVL_DELETE
  308.   local NODE* AVL(AVLID,delete) (ELEMENT value, NODE* tree);
  309.   local NODE* AVL(AVLID,delete) (value,tree)
  310.     var reg8 ELEMENT value;
  311.     var NODE* tree;
  312.     { var reg6 KEY key = KEYOF(value);
  313.       var reg2 NODE** nodeplace = &tree;
  314.       var NODE** stack[MAXHEIGHT]; # Ein kleiner Privat-Stack
  315.       var reg4 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack
  316.       var reg3 NODE** * stack_ptr = &stack[0]; # stets = &stack[stack_count]
  317.       var reg7 NODE* node_to_delete;
  318.       loop
  319.         { var reg1 NODE* node = *nodeplace;
  320.           if (node == EMPTY) goto fertig; # Element nicht gefunden
  321.           *stack_ptr++ = nodeplace; stack_count++;
  322.          {var reg5 sintL sign = COMPARE(key,KEYOF(node->nodedata.value));
  323.           if (sign == 0)
  324.             { if (EQUAL(value,node->nodedata.value)) # gefunden?
  325.                 { node_to_delete = node; break; }
  326.                 else
  327.                 goto fertig;
  328.             }
  329.           if (sign < 0)
  330.             # key < KEYOF(node->nodedata.value)  --> im linken Teilbaum entfernen:
  331.             { nodeplace = &node->nodedata.left; }
  332.             else
  333.             # key > KEYOF(node->nodedata.value)  --> im rechten Teilbaum entfernen:
  334.             { nodeplace = &node->nodedata.right; }
  335.         }}
  336.      {var reg5 NODE** nodeplace_to_delete = nodeplace;
  337.       # node_to_delete = *nodeplace_to_delete ist zu entfernen.
  338.       if (node_to_delete->nodedata.left == EMPTY)
  339.         # node_to_delete wird ersetzt durch node_to_delete->nodedata.right.
  340.         { *nodeplace_to_delete = node_to_delete->nodedata.right;
  341.           stack_ptr--; stack_count--; # doch kein rebalance bei *nodeplace_to_delete!
  342.         }
  343.         else
  344.         # node_to_delete wird ersetzt durch das am weitesten rechts gelegenene
  345.         # Element von node_to_delete->nodedata.left.
  346.         { var reg8 NODE** * stack_ptr_to_delete = stack_ptr;
  347.           var reg2 NODE** nodeplace = &node_to_delete->nodedata.left;
  348.           var reg1 NODE* node;
  349.           loop
  350.             { node = *nodeplace;
  351.               if (node->nodedata.right == EMPTY) break;
  352.               *stack_ptr++ = nodeplace; stack_count++;
  353.               nodeplace = &node->nodedata.right;
  354.             }
  355.           *nodeplace = node->nodedata.left;
  356.           # node nimmt die Stellung von node_to_delete ein:
  357.           node->nodedata.left = node_to_delete->nodedata.left;
  358.           node->nodedata.right = node_to_delete->nodedata.right;
  359.           node->nodedata.height = node_to_delete->nodedata.height;
  360.           *nodeplace_to_delete = node; # statt node_to_delete
  361.           # Der Rebalance-Stack (Weg von der Wurzel nach unten) führt jetzt
  362.           # nicht mehr über node_to_delete, sondern über node:
  363.           *stack_ptr_to_delete = &node->nodedata.left; # statt &node_to_delete->nodedata.left
  364.      }  }
  365.       FREE(node_to_delete);
  366.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  367.       fertig:
  368.       return tree;
  369.     }
  370. #endif
  371.  
  372. # Entfernt ein Element aus einem AVL-Baum und liefert den neuen AVL-Baum.
  373. # Ohne FREE aufzurufen.
  374. #ifndef NO_AVL_DELETE1
  375.   local NODE* AVL(AVLID,delete1) (NODE* node_to_delete, NODE* tree);
  376.   # Stellt fest, wo in einem Baum ein Element node_to_delete (mit Key key)
  377.   # vorkommt. Legt den Pfad ab stack_ptr ab, und liefert das neue stack_ptr.
  378.   local NODE** * AVL(AVLID,delete1find) (NODE* node_to_delete, KEY key, NODE* tree, NODE** * stack_ptr);
  379.   local NODE** * AVL(AVLID,delete1find) (node_to_delete,key,tree,stack_ptr)
  380.     var reg6 NODE* node_to_delete;
  381.     var reg5 KEY key;
  382.     var reg2 NODE* tree;
  383.     var reg1 NODE** * stack_ptr;
  384.     { loop
  385.         { if (tree == EMPTY) { return (NODE***)NULL; }
  386.          {var reg3 sintL sign = COMPARE(key,KEYOF(tree->nodedata.value));
  387.           if (sign == 0)
  388.             # key = KEYOF(tree->nodedata.value)  --> Suche in beiden Teilbäumen:
  389.             { if (tree == node_to_delete) { return stack_ptr; }
  390.               *stack_ptr = &tree->nodedata.left;
  391.              {var reg4 NODE*** part = AVL(AVLID,delete1find)(node_to_delete,key,tree->nodedata.left,stack_ptr+1);
  392.               if (part) { return part; }
  393.              }
  394.               *stack_ptr = &tree->nodedata.right;
  395.              {var reg4 NODE*** part = AVL(AVLID,delete1find)(node_to_delete,key,tree->nodedata.right,stack_ptr+1);
  396.               if (part) { return part; }
  397.              }
  398.               return (NODE***)NULL;
  399.             }
  400.           if (sign < 0)
  401.             # key < KEYOF(tree->nodedata.value)  --> Suche im linken Teilbaum:
  402.             { *stack_ptr++ = &tree->nodedata.left; tree = tree->nodedata.left; }
  403.             else
  404.             # key > KEYOF(tree->nodedata.value)  --> Suche im rechten Teilbaum:
  405.             { *stack_ptr++ = &tree->nodedata.right; tree = tree->nodedata.right; }
  406.     }   }}
  407.   local NODE* AVL(AVLID,delete1) (node_to_delete,tree)
  408.     var reg7 NODE* node_to_delete;
  409.     var NODE* tree;
  410.     { var reg6 KEY key = KEYOF(node_to_delete->nodedata.value);
  411.       var reg2 NODE** nodeplace = &tree;
  412.       var NODE** stack[MAXHEIGHT]; # Ein kleiner Privat-Stack
  413.       var reg4 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack
  414.       var reg3 NODE** * stack_ptr = &stack[0]; # stets = &stack[stack_count]
  415.       loop
  416.         { var reg1 NODE* node = *nodeplace;
  417.           if (node == EMPTY) goto fertig; # Element nicht gefunden
  418.           *stack_ptr++ = nodeplace; stack_count++;
  419.          {var reg5 sintL sign = COMPARE(key,KEYOF(node->nodedata.value));
  420.           if (sign == 0)
  421.             { var reg5 NODE** * new_stack_ptr =
  422.                 AVL(AVLID,delete1find)(node_to_delete,key,node,stack_ptr);
  423.               if (new_stack_ptr) # oder irgendwo im Baum ab node gefunden?
  424.                 { stack_count += (new_stack_ptr - stack_ptr);
  425.                   stack_ptr = new_stack_ptr;
  426.                   nodeplace = stack_ptr[-1];
  427.                   break;
  428.                 }
  429.                 else
  430.                 goto fertig; # nicht gefunden
  431.             }
  432.           if (sign < 0)
  433.             # key < KEYOF(node->nodedata.value)  --> im linken Teilbaum entfernen:
  434.             { nodeplace = &node->nodedata.left; }
  435.             else
  436.             # key > KEYOF(node->nodedata.value)  --> im rechten Teilbaum entfernen:
  437.             { nodeplace = &node->nodedata.right; }
  438.         }}
  439.       # stack_ptr = &stack[stack_count], nodeplace = stack_ptr[-1],
  440.      {var reg5 NODE** nodeplace_to_delete = nodeplace;
  441.       # node_to_delete = *nodeplace_to_delete ist zu entfernen.
  442.       if (node_to_delete->nodedata.left == EMPTY)
  443.         # node_to_delete wird ersetzt durch node_to_delete->nodedata.right.
  444.         { *nodeplace_to_delete = node_to_delete->nodedata.right;
  445.           stack_ptr--; stack_count--; # doch kein rebalance bei *nodeplace_to_delete!
  446.         }
  447.         else
  448.         # node_to_delete wird ersetzt durch das am weitesten rechts gelegenene
  449.         # Element von node_to_delete->nodedata.left.
  450.         { var reg8 NODE** * stack_ptr_to_delete = stack_ptr;
  451.           var reg2 NODE** nodeplace = &node_to_delete->nodedata.left;
  452.           var reg1 NODE* node;
  453.           loop
  454.             { node = *nodeplace;
  455.               if (node->nodedata.right == EMPTY) break;
  456.               *stack_ptr++ = nodeplace; stack_count++;
  457.               nodeplace = &node->nodedata.right;
  458.             }
  459.           *nodeplace = node->nodedata.left;
  460.           # node nimmt die Stellung von node_to_delete ein:
  461.           node->nodedata.left = node_to_delete->nodedata.left;
  462.           node->nodedata.right = node_to_delete->nodedata.right;
  463.           node->nodedata.height = node_to_delete->nodedata.height;
  464.           *nodeplace_to_delete = node; # statt node_to_delete
  465.           # Der Rebalance-Stack (Weg von der Wurzel nach unten) führt jetzt
  466.           # nicht mehr über node_to_delete, sondern über node:
  467.           *stack_ptr_to_delete = &node->nodedata.left; # statt &node_to_delete->nodedata.left
  468.      }  }
  469.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  470.       fertig:
  471.       return tree;
  472.     }
  473. #endif
  474.  
  475. # Macros zum Durchlaufen eines AVL-Baumes:
  476. # AVL_map(tree,node,statement);
  477. # Ein Baum wird durchlaufen, jeweils node gebunden und statement ausgeführt.
  478.   # Durchlaufungsreihenfolge:
  479.   #               AVL_map : in Reihenfolge  L N R
  480.   #     N         AVL_map_reverse : in umgekehrter Reihenfolge  R N L
  481.   #    / \        AVL_map_preorder : in Präfix-Reihenfolge  N L R
  482.   #   L   R       AVL_map_postorder : in Postfix-Reihenfolge  L R N
  483.   #
  484.   TYPEDEF struct { NODE* node; boolean rightp; } AVL(AVLID,mapstackitem);
  485.   TYPEDEF AVL(AVLID,mapstackitem) AVL(AVLID,mapstack)[MAXHEIGHT];
  486.   #define AVL_map(tree,nodevar,statement)  \
  487.     { var reg2 NODE* nodevar = (tree);                               \
  488.       var AVL(AVLID,mapstack) stack; # Ein kleiner Privat-Stack      \
  489.       var reg3 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack \
  490.       var reg1 AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; # stets = &stack[stack_count] \
  491.       BEGIN_DECLTAG                                                  \
  492.      {DECLTAG(down); DECLTAG(up); DECLTAG(end);                      \
  493.       GENTAG(down): # rekursiv absteigen                             \
  494.         if (nodevar == EMPTY) goto GENTAG(up);                       \
  495.         stack_ptr->node = nodevar;                                   \
  496.         stack_ptr->rightp = FALSE; nodevar = nodevar->nodedata.left; \
  497.         stack_ptr++; stack_count++;                                  \
  498.         goto GENTAG(down);                                           \
  499.       GENTAG(up): # wieder hochsteigen                               \
  500.         if (stack_count == 0) goto GENTAG(end);                      \
  501.         stack_count--; stack_ptr--;                                  \
  502.         if (stack_ptr->rightp) goto GENTAG(up);                      \
  503.         nodevar = stack_ptr->node;                                   \
  504.         statement;                                                   \
  505.         stack_ptr->rightp = TRUE; nodevar = nodevar->nodedata.right; \
  506.         stack_ptr++; stack_count++;                                  \
  507.         goto GENTAG(down);                                           \
  508.       GENTAG(end): ; # fertig                                        \
  509.      }END_DECLTAG                                                    \
  510.     }
  511.   #define AVL_map_reverse(tree,nodevar,statement)  \
  512.     { var reg2 NODE* nodevar = (tree);                               \
  513.       var AVL(AVLID,mapstack) stack; # Ein kleiner Privat-Stack      \
  514.       var reg3 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack \
  515.       var reg1 AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; # stets = &stack[stack_count] \
  516.       BEGIN_DECLTAG                                                  \
  517.      {DECLTAG(down); DECLTAG(up); DECLTAG(end);                      \
  518.       GENTAG(down): # rekursiv absteigen                             \
  519.         if (nodevar == EMPTY) goto GENTAG(up);                       \
  520.         stack_ptr->node = nodevar;                                   \
  521.         stack_ptr->rightp = TRUE; nodevar = nodevar->nodedata.right; \
  522.         stack_ptr++; stack_count++;                                  \
  523.         goto GENTAG(down);                                           \
  524.       GENTAG(up): # wieder hochsteigen                               \
  525.         if (stack_count == 0) goto GENTAG(end);                      \
  526.         stack_count--; stack_ptr--;                                  \
  527.         if (!(stack_ptr->rightp)) goto GENTAG(up);                   \
  528.         nodevar = stack_ptr->node;                                   \
  529.         statement;                                                   \
  530.         stack_ptr->rightp = FALSE; nodevar = nodevar->nodedata.left; \
  531.         stack_ptr++; stack_count++;                                  \
  532.         goto GENTAG(down);                                           \
  533.       GENTAG(end): ; # fertig                                        \
  534.      }END_DECLTAG                                                    \
  535.     }
  536.   #define AVL_map_preorder(tree,nodevar,statement)  \
  537.     { var reg2 NODE* nodevar = (tree);                               \
  538.       var AVL(AVLID,mapstack) stack; # Ein kleiner Privat-Stack      \
  539.       var reg3 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack \
  540.       var reg1 AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; # stets = &stack[stack_count] \
  541.       BEGIN_DECLTAG                                                  \
  542.      {DECLTAG(down); DECLTAG(up); DECLTAG(end);                      \
  543.       GENTAG(down): # rekursiv absteigen                             \
  544.         if (nodevar == EMPTY) goto GENTAG(up);                       \
  545.         statement;                                                   \
  546.         stack_ptr->node = nodevar;                                   \
  547.         stack_ptr->rightp = FALSE; nodevar = nodevar->nodedata.left; \
  548.         stack_ptr++; stack_count++;                                  \
  549.         goto GENTAG(down);                                           \
  550.       GENTAG(up): # wieder hochsteigen                               \
  551.         if (stack_count == 0) goto GENTAG(end);                      \
  552.         stack_count--; stack_ptr--;                                  \
  553.         if (stack_ptr->rightp) goto GENTAG(up);                      \
  554.         nodevar = stack_ptr->node;                                   \
  555.         stack_ptr->rightp = TRUE; nodevar = nodevar->nodedata.right; \
  556.         stack_ptr++; stack_count++;                                  \
  557.         goto GENTAG(down);                                           \
  558.       GENTAG(end): ; # fertig                                        \
  559.      }END_DECLTAG                                                    \
  560.     }
  561.   #define AVL_map_postorder(tree,nodevar,statement)  \
  562.     { var reg2 NODE* nodevar = (tree);                               \
  563.       var AVL(AVLID,mapstack) stack; # Ein kleiner Privat-Stack      \
  564.       var reg3 uintC stack_count = 0; # Anzahl der Elemente auf dem Stack \
  565.       var reg1 AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; # stets = &stack[stack_count] \
  566.       BEGIN_DECLTAG                                                  \
  567.      {DECLTAG(down); DECLTAG(up); DECLTAG(end);                      \
  568.       GENTAG(down): # rekursiv absteigen                             \
  569.         if (nodevar == EMPTY) goto GENTAG(up);                       \
  570.         stack_ptr->node = nodevar;                                   \
  571.         stack_ptr->rightp = FALSE; nodevar = nodevar->nodedata.left; \
  572.         stack_ptr++; stack_count++;                                  \
  573.         goto GENTAG(down);                                           \
  574.       GENTAG(up): # wieder hochsteigen                               \
  575.         if (stack_count == 0) goto GENTAG(end);                      \
  576.         stack_count--; stack_ptr--;                                  \
  577.         nodevar = stack_ptr->node;                                   \
  578.         if (stack_ptr->rightp) { statement; goto GENTAG(up); }       \
  579.         stack_ptr->rightp = TRUE; nodevar = nodevar->nodedata.right; \
  580.         stack_ptr++; stack_count++;                                  \
  581.         goto GENTAG(down);                                           \
  582.       GENTAG(end): ; # fertig                                        \
  583.      }END_DECLTAG                                                    \
  584.     }
  585.  
  586. # Beispiel zur Anwendung von AVL(AVLID,least) und AVL(AVLID,move):
  587. #   { var NODE* tree = ...;
  588. #     var reg2 KEY limit = ...;
  589. #     # Suche in tree nach dem kleinsten Key >= limit:
  590. #     var AVL(AVLID,stack) stack;
  591. #     var reg1 NODE* bestfit = AVL(AVLID,least)(limit,&tree,&stack);
  592. #     if (bestfit == EMPTY) { error(); }
  593. #     # Nun ist sicher COMPARE(KEYOF(bestfit->nodedata.value),limit) >= 0.
  594. #     ...; KEYOF(bestfit->nodedata.value) -= limit; ...;
  595. #     # gefundenes und modifiziertes Element im AVL-Baum umhängen:
  596. #     AVL(AVLID,move)(&stack);
  597. #   }
  598.  
  599. TYPEDEF struct { uintC count; NODE** path[MAXHEIGHT]; } AVL(AVLID,stack);
  600.  
  601. # Liefert das Element aus einem AVL-Baum, dessen Key möglichst klein, aber
  602. # noch >= ein gegebener Limit ist. (EMPTY, falls alle Elemente < Limit sind.)
  603. # Dazu als Vorbereitung fürs Löschen den Pfad von der Wurzel bis dorthin
  604. # (inclusive, d.h. Ergebnis = stack->path[stack->count-1] ).
  605. #ifndef NO_AVL_LEAST
  606.   local NODE* AVL(AVLID,least) (KEY limit, NODE** tree_ptr, AVL(AVLID,stack) * stack);
  607.   local NODE* AVL(AVLID,least) (limit,tree_ptr,stack)
  608.     var reg5 KEY limit;
  609.     var reg8 NODE** tree_ptr;
  610.     var reg2 AVL(AVLID,stack) * stack; # Ausgabe: Pfad von der Wurzel ab
  611.     { var reg7 NODE* mark = EMPTY;
  612.       var reg6 uintC markdepth = 0;
  613.       var reg3 NODE** nodeplace = tree_ptr;
  614.       var reg4 uintC nodedepth = 0;
  615.       # mark = betrachteter Teilbaum, node = letztes betrachtetes Element darin.
  616.       # markdepth = Stacktiefe bis mark, nodedepth = Stacktiefe bis node.
  617.       # Es gilt markdepth <= nodedepth.
  618.       loop
  619.         { stack->path[nodedepth++] = nodeplace;
  620.          {var reg1 NODE* node = *nodeplace;
  621.           # Alle Elemente mit Key >= Limit liegen entweder im Teilbaum
  622.           # unterhalb von node oder rechts von mark (mark eingeschlossen).
  623.           if (node==EMPTY) break;
  624.           if (COMPARE(KEYOF(node->nodedata.value),limit) < 0)
  625.             { # Alle Elemente unterhalb von node, die >= Limit sind, müssen
  626.               # bereits unterhalb von node->nodedata.right liegen.
  627.               nodeplace = &node->nodedata.right;
  628.             }
  629.             else
  630.             { # Limit <= node <= mark.
  631.               # Ab jetzt nur den Teilbaum unterhalb von node betrachten:
  632.               mark = node; markdepth = nodedepth;
  633.               nodeplace = &node->nodedata.left;
  634.             }
  635.         }}
  636.       # Alle Elemente >= Limit liegen rechts von mark (mark eingeschlossen).
  637.       stack->count = markdepth; return mark;
  638.     }
  639. #endif
  640.  
  641. # Setzt ein Element in einem AVL-Baum um, nachdem sich sein Key verändert hat.
  642. #ifndef NO_AVL_MOVE
  643.   local void AVL(AVLID,move) (AVL(AVLID,stack) * stack);
  644.   local void AVL(AVLID,move) (stack)
  645.     var reg7 AVL(AVLID,stack) * stack; # Ein kleiner Stack
  646.     { var reg4 uintC stack_count = stack->count; # Anzahl der Elemente auf dem Stack
  647.       var reg3 NODE** * stack_ptr = &stack->path[stack_count]; # stets = &stack->path[stack_count]
  648.       # 1. Schritt, vgl. AVL(AVLID,delete) :
  649.       var reg5 NODE** nodeplace_to_delete = stack_ptr[-1];
  650.       var reg6 NODE* node_to_delete = *nodeplace_to_delete; # zu entfernendes Element
  651.       # node_to_delete = *nodeplace_to_delete ist zu entfernen.
  652.       if (node_to_delete->nodedata.left == EMPTY)
  653.         # node_to_delete wird ersetzt durch node_to_delete->nodedata.right.
  654.         { *nodeplace_to_delete = node_to_delete->nodedata.right;
  655.           stack_ptr--; stack_count--; # doch kein rebalance bei *nodeplace_to_delete!
  656.         }
  657.         else
  658.         # node_to_delete wird ersetzt durch das am weitesten rechts gelegenene
  659.         # Element von node_to_delete->nodedata.left.
  660.         { var reg8 NODE** * stack_ptr_to_delete = stack_ptr;
  661.           var reg2 NODE** nodeplace = &node_to_delete->nodedata.left;
  662.           var reg1 NODE* node;
  663.           loop
  664.             { node = *nodeplace;
  665.               if (node->nodedata.right == EMPTY) break;
  666.               *stack_ptr++ = nodeplace; stack_count++;
  667.               nodeplace = &node->nodedata.right;
  668.             }
  669.           *nodeplace = node->nodedata.left;
  670.           # node nimmt die Stellung von node_to_delete ein:
  671.           node->nodedata.left = node_to_delete->nodedata.left;
  672.           node->nodedata.right = node_to_delete->nodedata.right;
  673.           node->nodedata.height = node_to_delete->nodedata.height;
  674.           *nodeplace_to_delete = node; # statt node_to_delete
  675.           # Der Rebalance-Stack (Weg von der Wurzel nach unten) führt jetzt
  676.           # nicht mehr über node_to_delete, sondern über node:
  677.           *stack_ptr_to_delete = &node->nodedata.left; # statt &node_to_delete->nodedata.left
  678.         }
  679.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  680.       # 2. Schritt, vgl. AVL(AVLID,insert) :
  681.      {var reg5 KEY key = KEYOF(node_to_delete->nodedata.value);
  682.       var reg2 NODE** nodeplace = stack->path[0]; # = &tree
  683.       stack_count = 0; stack_ptr = &stack->path[0];
  684.       loop
  685.         { var reg1 NODE* node = *nodeplace;
  686.           if (node == EMPTY) break;
  687.           *stack_ptr++ = nodeplace; stack_count++;
  688.           if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
  689.             # key < KEYOF(node->nodedata.value)  --> im linken Teilbaum einfügen:
  690.             { nodeplace = &node->nodedata.left; }
  691.             else
  692.             # key >= KEYOF(node->nodedata.value)  --> im rechten Teilbaum einfügen:
  693.             { nodeplace = &node->nodedata.right; }
  694.         }
  695.       node_to_delete->nodedata.left = EMPTY;
  696.       node_to_delete->nodedata.right = EMPTY;
  697.       node_to_delete->nodedata.height = 1;
  698.       *nodeplace = node_to_delete;
  699.       AVL(AVLID,rebalance)(stack_ptr,stack_count);
  700.     }}
  701. #endif
  702.  
  703. # Sortiert einen AVL-Baum, nachdem sich die Keys verändert haben, und
  704. # liefert den neuen AVL-Baum.
  705. #ifndef NO_AVL_SORT
  706.   local NODE* AVL(AVLID,sort) (NODE* tree);
  707.   local NODE* AVL(AVLID,sort) (tree)
  708.     var reg5 NODE* tree;
  709.     { var reg4 NODE* new_tree = EMPTY;
  710.       AVL_map_postorder(tree,node, new_tree = AVL(AVLID,insert1)(node,new_tree); );
  711.       return new_tree;
  712.     }
  713. #endif
  714.  
  715. #ifdef DEBUG_AVL
  716. # Gibt einen AVL-Baum aus.
  717. # Benutzt asciz_out() und hex_out().
  718.   local void AVL(AVLID,out) (NODE* tree);
  719.   local void AVL(AVLID,out)(tree)
  720.     var reg1 NODE* tree;
  721.     { if (!(tree==EMPTY))
  722.         { asciz_out("(");
  723.           if (!(tree->nodedata.left==EMPTY))
  724.             { AVL(AVLID,out)(tree->nodedata.left); asciz_out("<"); }
  725.           hex_out(tree);
  726.           if (!(tree->nodedata.right==EMPTY))
  727.             { asciz_out(">"); AVL(AVLID,out)(tree->nodedata.right); }
  728.           asciz_out(")");
  729.     }   }
  730. #endif
  731.  
  732. #ifdef DEBUG_AVL
  733.   # Invarianten eines AVL-Baumes überprüfen:
  734.   local void AVL(AVLID,check) (NODE* tree);
  735.   local void AVL(AVLID,checkleft) (NODE* tree, KEY key);
  736.   local void AVL(AVLID,checkright) (NODE* tree, KEY key);
  737.   local void AVL(AVLID,check) (tree)
  738.     var reg9 NODE* tree;
  739.     { # Überprüfe Regeln 1 und 2:
  740.       AVL_map_postorder(tree,node,
  741.         { var reg2 HEIGHT h = node->nodedata.height;
  742.           var reg3 HEIGHT hl = heightof(node->nodedata.left);
  743.           var reg3 HEIGHT hr = heightof(node->nodedata.right);
  744.           if (!(   ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
  745.                 || ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
  746.              ) )
  747.             abort();
  748.         });
  749.       # Überprüfe Regel 3:
  750.       AVL_map(tree,node,
  751.         { AVL(AVLID,checkleft)(node->nodedata.left,KEYOF(node->nodedata.value));
  752.           AVL(AVLID,checkright)(node->nodedata.right,KEYOF(node->nodedata.value));
  753.         });
  754.     }
  755.   # Überprüfe, ob alle Elemente von tree einen Wert <= key haben:
  756.   local void AVL(AVLID,checkleft) (tree,key)
  757.     var reg9 NODE* tree;
  758.     var reg4 KEY key;
  759.     { AVL_map(tree,node,
  760.         if (!( COMPARE(KEYOF(node->nodedata.value),key) <= 0)) abort();
  761.         );
  762.     }
  763.   # Überprüfe, ob alle Elemente von tree einen Wert >= key haben:
  764.   local void AVL(AVLID,checkright) (tree,key)
  765.     var reg9 NODE* tree;
  766.     var reg4 KEY key;
  767.     { AVL_map(tree,node,
  768.         if (!( COMPARE(KEYOF(node->nodedata.value),key) >= 0)) abort();
  769.         );
  770.     }
  771. #endif
  772.  
  773. #undef heightof
  774. #undef TYPEDEF
  775.  
  776. # ------------------------------------------------------------------------------
  777.  
  778. #endif
  779.  
  780.