[C] Rotacja w drzewie AVL

Czy mógłbym prosić o zerknięcie na kod poniżej?

Jest to procedura wykonująca lewą rotację w drzewie AVL. Działa w 80% przypadków...

Na razie testowałem ją na zwykłym drzewie, nie sprawdzając jeszcze wag. Zawsze lepiej, jak spojrzy ktoś z boku. Byłbym wdzięczny za pomoc.

void rotLeft(binTreeNode **subTreeRoot) {               /* performs left rotation for a given subtree */
  binTreeNode *tmp = *subTreeRoot;                     /* saving address of old root */
  if ((*subTreeRoot) -> right != NULL) {               /* (0) rotation can be done if root subtree exists */
    *subTreeRoot = (*subTreeRoot) -> right;             /* (1) right son is set as new root */
    (*subTreeRoot) -> parent = tmp -> parent;          /* proper parent setting */
    tmp -> right = (*subTreeRoot) -> left;             /* (2) right son of old root points to left son of new root */
    tmp -> right -> parent = tmp;                      /* proper parent setting */
    (*subTreeRoot) -> left = tmp;                       /* (3) left son of new root points to old root */
    (*subTreeRoot) -> left -> parent = (*subTreeRoot); /* proper parent setting */
  }
  /*  x <- subTreeRoot  x                                             z <- subTreeRoot
     / \               / \                                           / \
    y   z             y   z <- subTreeRoot  x   z <- subTreeRoot    x   b
       / \               / \               / \ / \                 / \
      a   b             a   b             y   a   b               y   a
      
       (0)               (1)                   (2)                     (3)            */
}

A w tych pozostałych 20% przypadków co się dzieje?

W pozostałych przypadkach Wwysypuje się na tmp -> right -> parent = tmp; (segmentation fault)

Funkcję testuję w następujący sposób (dopiero ją napisałem, więc nie są to testy przy konkretnych zastosowaniach, raczej sprawdzenie poprawności): generuję drzewo i zapuszczam dla root'a.

Przed i po rotacji sprawdzam poprawność wskaźników w drzewie za pomocą funkcji coherent. Zaraz po utworzeniu drzewa zwraca 1, po rotacji też - chyba, że się na tej rotacji wysypie (to jest te 20%).

int properPointers(binTreeNode *item) {
	int dec = 1;

	if (item -> parent != NULL)			/* check parent pointers */
		dec = dec && ( (item -> parent -> left == item) || (item -> parent -> right == item) );

	if (item -> left != NULL)				/* check pointers in left subtree */
		dec = dec && properPointers(item -> left);

	if (item -> right != NULL)				/* check pointers in right subtree */
		dec = dec && properPointers(item -> right);

	return dec;
}


int coherent(binTreeNode *root) {
	return ( (root -> parent == NULL) && properPointers(root) );
}

Może Cię to naprowadzi:

static void rotate_left(avl_node_t** p, avl_node_t* y, avl_node_t* z) {
	assert(p != NULL);
	assert(y != NULL);
	assert(*p != NULL);
	assert(z != NULL);
	
	y->right = z->left;
	z->left = y;
	
	if(*p == y) {
		*p = z;
	} else if((*p)->left == y) {
		(*p)->left = z;
	} else {
		(*p)->right = z;
	}
}

static void rotate_right(avl_node_t** p, avl_node_t* y, avl_node_t* z) {
	assert(p != NULL);
	assert(y != NULL);
	assert(*p != NULL);
	assert(z != NULL);
	
	y->left = z->right;
	z->right = y;
	
	if(*p == y) {
		*p = z;
	} else if((*p)->left == y) {
		(*p)->left = z;
	} else {
		(*p)->right = z;
	}
}

A całe drzewo tak: http://pastebin.4programmers.net/4112
Tylko nie pytaj mnie o co tu chodzi bo pisałem to pół roku temu ;)

Skoro na
tmp -> right -> parent = tmp;

to pewnie tmp->right to NULL.

Tak, to była przyczyna, sprawdzałem przy pomocy assert. Wygląda na to, że działa. Chyba że ktoś widzi jeszcze jakieś błędy - ale wydaje mi się, że generalnie funkcja pomyślana i zaimplementowana jest prawidłowo. Teraz ma postać następującą:

void rotLeft(binTreeNode **subTreeRoot) {      /* performs left rotation for a given subtree */
  binTreeNode *tmp = *subTreeRoot;             /* saving address of old root */

  if ((*subTreeRoot) -> right != NULL) {       /* (0) rotation can be done if root subtree exists */
    *subTreeRoot = (*subTreeRoot) -> right;    /* (1) right son is set as new root */
    (*subTreeRoot) -> parent = tmp -> parent;  /* proper parent setting */
    tmp -> right = (*subTreeRoot) -> left;     /* (2) right son of old root points to left son of new root */
    if (tmp -> right != NULL)
      tmp -> right -> parent = tmp;            /* proper parent setting */
    (*subTreeRoot) -> left = tmp;              /* (3) left son of new root points to old root */
    (*subTreeRoot) -> left -> parent = (*subTreeRoot); /* proper parent setting */
  }
  /*                                         tmp
tmp -> x <- subTreeRoot  x <- tmp             |                                z <- subTreeRoot
      / \               / \                   v                               / \
     y   z             y   z <- subTreeRoot   x    z <- subTreeRoot   tmp -> x   b
        / \               / \                 / \ / \                       / \
       a   b             a   b               y   a   b                     y   a

       (0)               (1)                   (2)                          (3)         */
}

Dobra, pochwalę się swoim kodem :]

http://phpfi.com/324491

u mnie d to u ciebie x
u mnie x to u ciebie z

dodatkowo mam poprawianie wag, strasznie dużo ifów, ale dzięki temu rotacja podwójna wygląda mniej więcej tak:

int LR(node *d){
  a = R(d->right);
  b = L(d);
  return a || b;
}

dodatkowo funkcja zwraca wartość oznaczającą, czy drzewo zmniejszyło się - przydaje się to do usuwania elementów.

Możesz se porównać ;]