ugurkap / algorithm-implementations Goto Github PK

After deleting a node, some of the nodes seem to have wrong sizes. So, order statistic tree is useless after deleting an element as it is.

So, I have to review what is wrong with delete and transplant functions.

If the tree had only one node, and if you would delete that single node, RBTree:Delete should set the root node to the null pointer. So the suggest modification would be to add the following conditional statement between lines 264 and 265 of OrderStatisticTree.cpp:

if (node == root) {
root = nullptr;
return;
}

p.s. You may wonder why a random person would suddenly try to debug your old code. The reason is that I need to use order statistic trees for my C++ project without access to the GNU policy-based data structures. Yours was one of the few order statistic tree implementations without a major error that I could fine online.

In lines 282 and 291 of OrderStatisticTree.cpp, temp->parent should be changed to temp.