Binary Search Tree
------ ------ ----

Preface
-------

A binary tree is a tree each of whose nodes has at
most two children, with these children, if they
exist, being labeled `left' and `right'.

A binary search tree is a binary tree in which each
node has a label such that:

    (1) Any left child of a node, and all its
	descendants, have labels less than the
	label of the node.

    (2) Any right child of a node, and all its
	descendent's, have labels greater than the
	label of the node.

The height of a tree node is the number of nodes
in the shortest path from the node to the root.
The height of a tree is the maximum height of any
node in the tree.

The maximum time needed to find a tree node given its
label in a binary search tree is proportional to the
height of the tree.  A tree is said to be `balanced' if
its height is approximately the base 2 logarithm of the
number of nodes in the tree.  Therefore balanced binary
search trees are good for storing data that is to be
frequently searched.

Balancing a binary search tree is often done using two
rotations that change a piece of the tree as follows:


	    b			a
	   / \      ----->     / \
	  a   C               A   b
	 / \        <-----       / \
	A   B                   B   C

In these diagrams, `a' and `b' are nodes, and `A', `B',
and `C' are optional nodes.  `A', `B', and `C' can be
thought of as pointers that might be NULL.  The left-to-
right rotation changes the piece of tree on the left to
the piece of tree on the right, and the right-to-left
rotation changes the piece on the right to the piece on
the left.

The rotations preserve the property of being a binary
search tree: i.e. if a piece of a binary search tree is
rotated, the resulting tree is also a binary search
tree.

Problem
-------

You are to implement a `binary search tree machine'
that stores a binary search tree and a pointer to a
current node in the tree.  You are to input and execute
operations for this machine, including: create a new
tree, make a new left or right node for the current
node, and move the current node pointer to the left or
right child or to the parent of the current node.

There is also an operation to output (print) the
subtree rooted at the current node, and to perform a
left-to-right rotation on the subtree rooted at the
current node.  There is NO right-to-left rotation
operation (to save you coding time).

Input
-----

The input consists of a sequence of commands, where each
command consists of an operator character possibly
followed by an integer.  The integers are node labels.

The commands are described below.  In this description,
# denotes an integer which is part of a command and is
used as the label of a node.  The situations that are
indicated to be erroneous are guaranteed not to appear
in the input: you need not check for them.

  N #	Create a new tree with one node, the root node,
	labeled with #.  The new root node becomes the
	current node.

  L #	Make a new node that becomes the left child of
	the current node.  The new node is given the
	label #, and becomes the current node.

	It is an error if the current node already has
	a left child.

  R #	Make a new node that becomes the right child of
	the current node.  The new node is given the
	label #, and becomes the current node.

	It is an error if the current node already has
	a right child.

  p     Make the parent of the current node be the new
	current node.

	It is an error if the current node has no
	parent.

  l     Make the left child of the current node be the
	new current node.

	It is an error if the current node has no left
	child.

  r     Make the right child of the current node be the
	new current node.

	It is an error if the current node has no right
	child.

  o	Output (print) the subtree rooted at the current
	node on a single line.  See below for format.

  b	Output (print) a single blank line (containing
	NO SPACE or TAB characters).

  >     Perform a left-to-right rotation (see above) on
	the subtree rooted at the current node.  The
	new root of this subtree becomes the new current
	node.

	It is an error if the current node has no left
	child.

Whitespace, meaning any combination of SPACEs, TABs, and
NEW LINEs, may separate commands, but is NOT required.
Similarly whitespace may separate a command operator
character from an integer node label following it, but
the whitespace is NOT required.  Input ends with an end
of file.

Output
------

A subtree is printed as:

    (<left subtree if any><label><right subtree if any>)

That is, a left parenthesis, followed by the printout of
the subtree rooted at the left child if there is a left
child, followed by the label, followed by the printout
of the subtree rooted at the right child if there is a
right child, followed by a right parenthesis.

The `o' command outputs a single line.  There must be
no SPACE or TAB characters in ANY output line.  The
output must be PRECISELY as described.


Example Input
------- -----

N 0
o
L -2 L -3 ppo
lR -1 ppo
R 2 L 1 ppo
rR 3 ppo

b

N 5 R 6 R 7 R 8 pppo

b

N 0
  L -2
    L -3 p
    R -1 pp
  R 2
    L 1 p
    R 3 pp
o
>o
ro
>o
po


Example Output
------- ------

(0)
(((-3)-2)0)
(((-3)-2(-1))0)
(((-3)-2(-1))0((1)2))
(((-3)-2(-1))0((1)2(3)))

(5(6(7(8))))

(((-3)-2(-1))0((1)2(3)))
((-3)-2((-1)0((1)2(3))))
((-1)0((1)2(3)))
(-1(0((1)2(3))))
((-3)-2(-1(0((1)2(3)))))



File:	   tsearch.txt
Author:	   Bob Walton <walton@deas.harvard.edu>
Date:	   Fri Apr 28 04:39:14 EDT 2006

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.

RCS Info (may not be true date or author):

    $Author: hc3 $
    $Date: 2006/04/28 08:40:10 $
    $RCSfile: tsearch.txt,v $
    $Revision: 1.4 $