Return to Answer

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy. [Foo's answer gives probably much easier analysis; I just wanted to show the combinatorial "look" at the linear orders.]

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy. [Foo's answer gives probably much easier analysis; I just wanted to show the combinatorial "look" at the linear orders.]

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy.

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy. [Foo's answer gives probably much easier analysis; I just wanted to show the combinatorial "look" at the linear orders.]

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees. The problem is to create an order isomorphism between them.

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy.

The Stern-Brocot tree gives a representation of (Q⁺,<) as infinite binary search tree. One can create another infinite binary search tree with 0 on top, positive rationals on right and negative ones on left. This gives a representation of (Q,<) as an infinite binary search tree. If we remove 0, then we get a sum of two trees ("two trees side by side"). The problem is to create an order isomorphism between the tree corresponding to (Q,<) and sum of two trees corresponding to (Q-{0},<).

These two trees can be merged into one as follows: let root(T), left(T), right(T) be the root, left subtree and right subtree of a tree T. The merge is defined recursively by:

                                root(T1)
merge(T1,T2) =                 /       \
                          left(T1)   root(T2)
                                      /    \
               merge(right(T1),left(T2))   right(T2)

(to be precise, this definition is coinductive)

The Stern-Brocot tree is Euclidean algorithm inside, so complexity aspect you seem to be interested in should be easy.