1

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
  • 378
  • 3
  • 5
  • 10
Jack Avante
  • 149
  • 6
  • 2
    Possible duplicate of [Which self balancing binary tree would you recommend?](https://softwareengineering.stackexchange.com/questions/33036/which-self-balancing-binary-tree-would-you-recommend) – Jay Elston Oct 22 '19 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 Oct 22 '19 at 18:31
  • What do you mean by "sorted"? – Jay Elston Oct 22 '19 at 18:51

1 Answers1

4

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.

TMN
  • 11,313
  • 1
  • 21
  • 31