When we are inserting into a self-balancing tree, can we also assume it is sorting itself using those same operations? Or rather is there a traversal method that gets us the elements as a sorted list?


Self-balancing trees are required to maintain their structure so that the keys are always sorted (that is, so an inorder traversal of the tree results in all the elements in order). If your rotations are producing a tree that is no longer in order, then your rotations are incorrect. Keys can move "vertically" (children can become parents, and vice-versa), but are always required to maintain their relative position.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.