qlibc
qlibc copied to clipboard
qtreetbl has right lean child. Is qtreetbl not a llrb?
ut_qrbtree(134)-> "put: 40\n" (BLK:40) | |---L(BLK, null) | |---R(BLK, null) ut_qrbtree(134)-> "put: 30\n" (BLK:40) | |---L(RED:30) | | |---L(BLK, null) | | |---R(BLK, null) | |---R(BLK, null) ut_qrbtree(134)-> "put: 20\n" (BLK:30) | |---L(RED:20) | | |---L(BLK, null) | | |---R(BLK, null) | |---R(RED:40) -- right lean red node. | | |---L(BLK, null) | | |---R(BLK, null)
test code: `TESTCASE(rbtree, ut_qrbtree) { int i; int data[] = { 40, 30, 20, 50, 60, 55, 4, 24, 80, 33, 44, 11 }; int size = ARRAY_CNT(data); qtreetbl_t *qtree = qtreetbl(0);
qtree->set_compare(qtree, qtree_cmp);
for (i = 0; i < ARRAY_CNT(data); i++) {
LOG_DEBUG("put: %d\n", data[i]);
qtree->put_by_obj(qtree, &data[i], sizeof(int), &data[i], sizeof(int));
print_qrbtree(qtree->root, 0, 0);
}
{
for (i = 0; i < size; i++) {
LOG_DEBUG("delete-inorder:%d", data[i]);
qtree->remove_by_obj(qtree, &data[i], sizeof(int));
print_qrbtree(qtree->root, 0, 0);
}
}
qtree->free(qtree);
return 0;
} `