qlibc icon indicating copy to clipboard operation
qlibc copied to clipboard

qtreetbl has right lean child. Is qtreetbl not a llrb?

Open youtubezou opened this issue 5 years ago • 0 comments

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;

} `

youtubezou avatar Dec 31 '19 07:12 youtubezou