+ *pl = l;
+
+ if( *pl != AATREE_PTR_NIL )
+ aatree_get_node( tree, *pl )->parent = p;
+}
+
+static aatree_ptr aatree_del( aatree *tree, aatree_ptr x )
+{
+ /* Simulate what we would have created on the tail,
+ * we work along the tail in order, doing the same as the regular
+ * implementation. This only works because we have parent pointers. */
+
+ aatree_ptr it = x,
+ up[32];
+
+ int count = 1, dir = 0;
+
+ aatree_node *search = aatree_get_node( tree, x );
+ while(1)
+ if( search->parent == AATREE_PTR_NIL ) break;
+ else
+ {
+ search = aatree_get_node( tree, search->parent );
+ count ++;
+ }
+
+ int top=0;
+ while(1)
+ {
+ int index = count - (++top);
+
+ up[ index ] = it;
+ aatree_node *itnode = aatree_get_node( tree, it );
+ if( itnode->parent == AATREE_PTR_NIL )
+ break;
+ else
+ it = itnode->parent;
+ }
+
+ aatree_ptr _ptrswap_src = AATREE_PTR_NIL,
+ _ptrswap_dst = AATREE_PTR_NIL;
+
+ aatree_node *pxnode = aatree_get_node( tree, x );
+ aatree_ptr root = up[ count-1 ];
+ if( pxnode->left == AATREE_PTR_NIL || pxnode->right == AATREE_PTR_NIL )
+ {
+ if( --top != 0 )
+ {
+ aatree_node *pnode = aatree_get_node( tree, up[top-1] ),
+ *parent = aatree_get_node( tree, pxnode->parent );
+
+ aatree_ptr next = pxnode->left == AATREE_PTR_NIL?
+ pxnode->right:
+ pxnode->left;
+
+ if( parent->left == x ) pnode->left = next;
+ else pnode->right = next;
+
+ if( next != AATREE_PTR_NIL )
+ {
+ aatree_node *pnext = aatree_get_node( tree, next );
+ pnext->parent = up[top-1];
+ }
+ }
+ else
+ {
+ if( pxnode->right != AATREE_PTR_NIL ) root = pxnode->right;
+ else if( pxnode->left != AATREE_PTR_NIL ) root = pxnode->left;
+ else return AATREE_PTR_NIL;
+
+ aatree_node *newroot = aatree_get_node( tree, root );
+ newroot->parent = AATREE_PTR_NIL;
+ }
+ }
+ else
+ {
+ aatree_ptr heir = pxnode->right,
+ prev = x;
+
+ aatree_node *pheir = aatree_get_node( tree, heir );
+
+ while( pheir->left != AATREE_PTR_NIL )
+ {
+ up[top++] = prev = heir;
+ heir = pheir->left;
+ pheir = aatree_get_node( tree, heir );
+ }
+
+ _ptrswap_dst = heir;
+ _ptrswap_src = x;
+
+ aatree_node *pprev = aatree_get_node( tree, prev );
+
+ if( prev == x )
+ aatree_link_down( tree, prev, &pprev->right, pheir->right );
+ else
+ aatree_link_down( tree, prev, &pprev->left, pheir->right );
+ }
+
+ while( --top >= 0 )
+ {
+ if( top != 0 )
+ {
+ aatree_node *above = aatree_get_node( tree, up[top-1] );
+ dir = above->right == up[top];
+ }
+
+ aatree_recount( tree, up[top] );
+ aatree_node *pntop = aatree_get_node( tree, up[top] );
+ if( pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL ){}
+ else
+ {
+ aatree_node
+ *pnl = aatree_get_node( tree, pntop->left ),
+ *pnr = aatree_get_node( tree, pntop->right );
+
+ if( pnl->level < pntop->level-1 || pnr->level < pntop->level-1 )
+ {
+ if( pnr->level > --pntop->level )
+ pnr->level = pntop->level;
+
+ up[top] = aatree_skew( tree, up[top] );
+
+ aatree_node *ut = aatree_get_node( tree, up[top] );
+ ut->right = aatree_skew( tree, ut->right );
+
+ aatree_node *utr = aatree_get_node( tree, ut->right );
+ utr->right = aatree_skew( tree, utr->right );
+
+ up[top] = aatree_split( tree, up[top] );
+ ut = aatree_get_node( tree, up[top] );
+
+ ut->right = aatree_split( tree, ut->right );
+ }
+ }
+
+ if( top != 0 )
+ {
+ aatree_node *ut1 = aatree_get_node( tree, up[top-1] );
+
+ if( dir == 1 )
+ aatree_link_down( tree, up[top-1], &ut1->right, up[top] );
+ else
+ aatree_link_down( tree, up[top-1], &ut1->left, up[top] );
+ }
+ else
+ {
+ root = up[top];
+ aatree_get_node( tree, root )->parent = AATREE_PTR_NIL;
+ }
+ }
+
+ if( _ptrswap_dst != AATREE_PTR_NIL )
+ {
+ /* Copy everything except data from _src to _dst, relink.
+ * This is a bit of a messy addon, since the algorithm is originally
+ * based around moving the actual data(key) around, but we have the
+ * requirement that data can't move, so everything is done normally but
+ * the pointers are just swapped afterwards.
+ */
+
+ aatree_node *pdst = aatree_get_node( tree, _ptrswap_dst ),
+ *psrc = aatree_get_node( tree, _ptrswap_src );
+
+ pdst->count = psrc->count;
+ pdst->level = psrc->level;
+ pdst->left = psrc->left;
+ pdst->right = psrc->right;
+ pdst->parent = psrc->parent;
+
+ if( pdst->parent != AATREE_PTR_NIL )
+ {
+ aatree_node *parent = aatree_get_node( tree, pdst->parent );
+
+ if( parent->left == _ptrswap_src )
+ parent->left = _ptrswap_dst;
+ else if( parent->right == _ptrswap_src )
+ parent->right = _ptrswap_dst;
+ }
+ else
+ {
+ root = _ptrswap_dst;
+ }
+
+ if( pdst->left != AATREE_PTR_NIL )
+ aatree_get_node( tree, pdst->left )->parent = _ptrswap_dst;
+ if( pdst->right != AATREE_PTR_NIL )
+ aatree_get_node( tree, pdst->right )->parent = _ptrswap_dst;
+ }
+
+ return root;