3

I don't understand how binary search trees are always defined as "sorted". I get in an array representation of a binary heap you have a fully sorted array. I haven't seen array representations of binary search trees so hard for me to see them as sorted like an array eg [0,1,2,3,4,5] but rather sorted with respect to each node. What is the right way to think about a BST being "sorted" conceptually?

devdropper87
  • 4,025
  • 11
  • 44
  • 70
  • When building a BST, it's common to have lower elements from a `.compareTo()` method be on the left, and higher elements be on the right. In this way it will always be sorted – phflack Nov 11 '15 at 06:12
  • This article *does not* answer your question, but can be interesting to you. http://stackoverflow.com/questions/3158014/sort-bst-in-on-using-constant-memory – Yeldar Kurmangaliyev Nov 11 '15 at 06:24
  • @phflack: More precisely, having "smaller" (whatever your definition of that may be) elements on the left is _the_ way to construct a binary _search_ tree. If you don't have such a structure, it'll just be a generic binary tree. – Aasmund Eldhuset Nov 11 '15 at 07:03
  • @AasmundEldhuset What stops a person from putting smaller elements on the right? All it takes is a sign being flipped – phflack Nov 11 '15 at 14:01
  • @phflack: You could flip your definition of "smaller", but sure, putting them on the right works too as long as you're consistent with it. The reason I commented was that to me, it sounds like your original comment implies that there is another valid way to organize a BST (since you're saying "it's _common_ to have..."), which there isn't (except for the left/right difference, which I'd argue isn't really two different ways because you can redefine "smaller" instead). – Aasmund Eldhuset Nov 11 '15 at 17:52

4 Answers4

16

There are many types of binary search trees. All of them have one thing in common: they satisfy an invariant which enables binary search, namely an order relation by which every element in the tree can be compared to any other element in the tree, in a total preorder.

What does that mean?

Let's consider the typical statement of a BST invariant in a textbook, which states that every node's key is greater than all keys in its left sub-tree, and less than all keys in its right sub-tree. We omit conflict resolution details for keys which compare equal.

What does that BST look like? Here's an example: height-balanced BST

The way I would explain it to a class of three-year-olds, is try to collapse all the nodes to the bottom level of the leaves, just let them fall down. Or, for high-schoolers, draw a line from each node/key projecting them on the x-axis. Once you did that, it's obvious the keys are already in (ascending) order.

Is this imaginary and casual observation analogous to our definition of a sorted sequence? Yes, it is. Since the elements of the BST satisfy a total preorder, an in-order traversal of the BST must produce those elements in order (Ex: prove it).

It is equivalent to state that if we had stored a BST's keys, by an in-order traversal, in an array, the array would be sorted.

Therefore, by way of our initial definition of a BST, the in-order traversal is the intuitive way of thinking of one as "sorted".

Michael Foukarakis
  • 39,737
  • 6
  • 87
  • 123
4

enter image description here

Does this help? It's a binary heap shown as an array

Michael
  • 3,093
  • 7
  • 39
  • 83
  • Thanks yeah that's clear to me, but I'm asking about a binary search tree. How is a binary search tree "sorted"? – devdropper87 Nov 11 '15 at 06:20
  • 1
    Generally binary tree's aren't sorted for you. Ignoring my comment above, you have to sort a binary tree before you can search it because parts of the code involve traversing the left or right subtree based on whether or not the value of the left child is less than the value of the parent node, or if the right child's value is greater than the parent node's. Basically what I'm trying to say is that to use a binary search tree, it needs to be sorted beforehand so they that's why they define it as "sorted" for you. – Michael Nov 11 '15 at 06:30
  • Downvoting because 1) it doesn't answer the question and 2) it's misleading because the array of a heap is almost never sorted - only in very rare cases (like the one you've shown). – Aasmund Eldhuset Nov 11 '15 at 06:33
1

as far as data structures are concerned (arrays, trees, linked lists, etc), "sorted" means that sequentially going through all it's elements you'll find that their values are ordered according to some rule ( >, <, <=, etc).

For arrays, this is easy to picture because it's a linear data structure. But trees are not, however, iterating through a BST you will notice that all the element are ordered accoring to the rule left value <= node value < right value ( or something similar); the very definition of a sorted data structure.

Pandrei
  • 4,843
  • 3
  • 27
  • 44
0

It is not "sorted" in the same sense an array might be sorted (and trees, except for heaps, are rarely represented as arrays anyway), but they have a structure that allows you to easily traverse the elements in sorted order: simply traverse the nodes of the BST with a depth-first search, and output each node's value after you've looked at its left child (if any) but before you look at its right child (if any).

By the way, the array in which a heap is stored is almost always not sorted. The heap itself can also not be said to be "sorted", because it does not have enough structure to be able to readily produce the elements in sorted order without destroying the heap by successively removing the top element. For example, although you do know that the top element is larger than both of its children (or smaller, depending on the heap type), you cannot tell in advance which child is smaller than the other.

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81