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?
geocodezip
3903 gold badges5 silver badges11 bronze badges
-
2Possible duplicate of Which self balancing binary tree would you recommend?Jay Elston– Jay Elston2019年10月22日 18:24:57 +00:00Commented Oct 22, 2019 at 18:24
-
How could it be a possible duplicate? That thread doesn't discuss whether the balanced trees are sorted or not.Jack Avante– Jack Avante2019年10月22日 18:31:23 +00:00Commented Oct 22, 2019 at 18:31
-
What do you mean by "sorted"?Jay Elston– Jay Elston2019年10月22日 18:51:08 +00:00Commented Oct 22, 2019 at 18:51
1 Answer 1
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.
answered Oct 22, 2019 at 18:50
Explore related questions
See similar questions with these tags.