Are partially ordered trees the same as binary trees?

1
votes

I'm a little confused about how partially ordered trees work. Are they kind of the same way as binary trees? Also, what is it best use for?

For example if I inserted 5,6,4,9,3,1,7 into an empty tree, I would get:

      5
     / \
    4   6
  /      \
 3       9
/       /
1      7
2
data-structurestreebinary-tree
Binary trees suggest nothing about order. They are simply trees with two (or less) branches at every node. – River
The example you have presented here is a binary search tree. For more info on them, see my answer below. – River

2 Answers

5
votes

A binary tree is a particular shape of tree. Specifically, a binary tree is a tree where each node can have either 0, 1, or 2 children. Binary trees make no restrictions about what values can be stored in the nodes or how those values relate to one another, so all of the following are valid binary trees:

     1           4             9
    /           / \           / \
   3           2   6         3   6     
  / \         /     \       / \   \
 3   2       1       8     0   2   4

A partially-ordered tree is a tree in which there is a specific set of restrictions on which values can be where in the tree. Specifically, a partially-ordered tree - which, by the way, is often called a heap-ordered tree - is one in which every node's value is greater than all of the values of each of its children. (Sometimes you see this property as requiring that every node's value is less than all of its children's values; that's essentially the same). However, there are no restrictions on how many children each node in a partially-ordered tree can have - the partially-ordered property says where the values can go, but not what the shape of the tree is. For example, here are some partially-ordered trees:

          4            9             3
         /|\          / \             \
        3 2 1        4   5             2
       / \          /|\   \             \
      0   2        3 3 3   3             1

The first two of these trees are partially-ordered trees but not binary trees, while the last is both a partially-ordered tree and a binary tree.

You asked about where you'd use a partially-ordered tree. Many famous and important data structures - binary heaps, binomial heaps, Fibonacci heaps, etc. - are implemented as collections of partially-ordered trees with extra structural properties imposed on them. These can be used to implement fast priority queues, which speed up many famous algorithms like Dijkstra's algorithm for finding shortest paths and Prim's algorithm for finding minimum spanning trees.

Keep in mind that partially-ordered trees are not the same as binary search trees. In your original question, you showed an example of the tree that would be formed by inserting a series of values into an empty binary search tree. While that's right, that's entirely independent of the partially-ordered trees.

Hope this helps!

2
votes

I'm not quite sure what you mean. A binary tree is a tree with a branching factor of two, that is, each node has 0-2 children. So the tree you have here is also a binary tree.

Perhaps you mean a binary search tree (BST) (also, ordered binary tree) which is what you seem to have presented.

BSTs
Ordered by these insert rules, starting at the root:
1: if inserted node is less than a node, check left child
2: if inserted node is greater than a node, check right child
3: if no child is found, insert the number as a node here

Example
So for you example, the first item, 5, would become the root.
Then 6, being greater than 5, would become it's right child.
4, being less, would become it's left child.
9 is greater than 5, so goes right, sees the 6, is still greater and becomes the 6's right child. 3 is less than both 5 and then 4 so it becomes the left child of 4. 1 follows this same path all the way down and becomes the left child of 3. Finally 7 is greater than 5, so it goes right, greater than 6, so it goes right again, but less than 9, and thus becomes it left child.

As you can see the order of insertion matters quite a lot for the structure of a BST.

Advantages
BST's have the advantage that they can be searched with a similar method to binary search allow insertion, lookup, and deletion times of O(log n), which is quite good. So they are best used in situations in which search time is important, and in which frequent insertion/deletion will be required. Additionally they are memory efficient and do not take up any more space than they have items.

Partially Ordered Trees
I'm not familiar with partially ordered trees, but based on some googling, it seems that you are not presenting one here. They seem to be trees in which each parent is strictly greater than its children.