1
$\begingroup$

Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the leaves of t1. In particular, some values can be removed and some can be duplicated.

I'm looking for a minimal set of somewhat "natural" operations on binary trees that can be composed to transform a tree into any of its derivable trees.

By natural I mean operations which are local to the root of the tree or its vicinity, happen in constant time, and can be somewhat visualized.

For instance, swapping the left and right subtree of the root of performing AVL like rotations would qualify as natural operations.

$\endgroup$
  • 1
    $\begingroup$ Is a tree with a hundred nodes all labeled "2" considered to be "derivable" from a single node labeled "2"? (Strictly speaking this fits the definition given.) $\endgroup$ – Daniel McLaury Feb 13 at 13:45
  • 1
    $\begingroup$ Another question: does "delete the root node, provided there's no left subtree" count as a "natural" operation? If not, can you give an example of a "natural" operation that deletes a node? $\endgroup$ – Daniel McLaury Feb 13 at 13:54
  • $\begingroup$ Yes, 100 labelled 2 is derivable. Yes, delete the root node provides there's no left subtree is "natural" $\endgroup$ – Arthur B Feb 13 at 17:51
1
$\begingroup$

It looks like the following set of four operations is sufficient. They are also minimal / necessary in the sense that no single operation can be removed from the set.

  • right rotation at the root:

        .            .
       / \          / \
      .  z    =>   x   .
     / \              / \
    x   y            y   z
    
  • duplicating the tree

  • deleting the left branch
  • flipping the right grandchildren

By way of illustration (and a form of proof outline), I've written up a Haskell implementation. Given a definition of a Tree structure and a TreeOp tree operation type:

data Tree a = Node (Tree a) (Tree a) | Leaf a
type TreeOp a = Tree a -> Maybe (Tree a)

the primitive operations would be defined as:

rotateR, dup, deleteL, flipR :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

We can define derived operations to flip the root's children (duplicate the tree, flip the right grandchildren, and delete the left branch):

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

Similarly, we can define an operation to duplicate the right branch:

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

as well as the symmetric variants of all the above operations:

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

Finally, it will be helpful to have an operation for "interleaving" the grandchildren like so:

        ..           ..
       /  \         /  \
      .    .       .    .
     / \  / \     / \  / \
     w x  y z     w y  x z

The best implementation I could come up with was:

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

With interleave, it's easy to define operations to rotate the left and right subtrees of the root independently:

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

Using a helper to apply an operation repeatedly until it no longer works:

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

we can turn any tree into an in-order traversal "cons-list-like" normal form:

toList :: Tree a -> Tree a
toList 
  = untilDone rotateR 
    >>> untilDone (untilDone rotateRL >>> rotateL)
    >>> untilDone rotateR

meaning that, for any tree t whose in-order traversal of leaves is, say, [1,2,3,4,5], the result of toList t will be:

Node (Leaf 1) (Node (Leaf 2) (Node (Leaf 3) (Node (Leaf 4) (Leaf 5))))

Now, this normal form is just a zipper under the rotateL and rotateR operations -- we can rotateR it to any point in the list, with the "rest" of the list elements on the right branch in normal form, and the preceding elements on the left branch in an "inverted" normal form (with leaves on the right branches instead of the left).

Applying interleave to such a zipper will swap adjacent elements at the zipper's cursor in the general case, though the following function also handles the corner cases where interleave fails because the left or right branch is just a leaf:

swapLeaves :: TreeOp a
swapLeaves = interleave 
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

Here, orTry isn't a separate operation -- it's just a conditional control structure that handles the case where a generalized operation fails because, say, the left branch is only a leaf instead of a larger inverted cons list:

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

We can also duplicate the element to the left of the cursor with:

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLR) 
  `orTry` dupL

This doesn't handle two corner cases: we can duplicate the rightmost element (i.e., duplicate an element to the right of the cursor) with a swapLeaves >=> dupLeaf => swapLeaves => rotateR => swapLeaves combination, and if the tree is a lone leaf, we can just duplicate it with dup.

We can delete the element to the left of the cursor with:

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

and the last element with a swapLeaves >=> deleteLeaf combination`.

I think it's clear that with there operations to swap, duplicate, and delete leaves together with rotations through the zipper, we can turn any in-order cons list into any other in-order cons list constructed from a subset of its elements.

And, since toList uses only reversible operations, it follows that we can reconstruct the final tree from its in-order cons list, so I think that probably completes the proof that these operations are sufficient.

To establish that they're "minimal" / necessary, we need to show that dropping any one of the primitive operations would make it impossible to handle some case. It's easy to see that dup and deleteL are necessary, as they're the only operations that can add or remove leaves, respectively. With the exception of rotateL, all the other operations preserve the binary tree property of "perfection" or "perfect balance" (i.e., the property of having all leaves at the same level), so rotateR is necessary to create an unbalanced tree from a perfectly balanced one. And finally, flipR is necessary as no remaining operations can change the in-order traversal of a tree's leaves (oops -- actually, this isn't convincing, since dup and deleteL can do this; I'll need to think about this one).

Anyway, here's the full code to play with:

{-# OPTIONS_GHC -Wall #-}
import Data.Maybe (fromJust)
import Control.Monad
import Control.Applicative
import Control.Arrow ((>>>))
data Tree a = Node (Tree a) (Tree a) | Leaf a
data Side = L | R
type TreeOp a = Tree a -> Maybe (Tree a)

rotateR, dup, deleteL, flipR, interleave :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRR >>> rotateL)
    >>> untilDone rotateR

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLL)
  `orTry` dupL `orTry` dup

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

pprint :: (Show a) => Tree a -> IO ()
pprint = putStrLn . unlines . pshow
pshow :: (Show a) => Tree a -> [String]
pshow t = case t of
  Leaf x -> [center 5 $ show x]
  Node x y -> bar ++ xy'
    where x' = pshow x
          y' = pshow y
          xy' = hjoin x' y'
          lft = width x' `div` 2
          rgt = width y' `div` 2
          rest = width xy' - lft - rgt
          bar = [ justify lft rgt $  '.' : replicate (rest - 2) '-' ++ "."
                , justify lft rgt $  '|' : spaces (rest - 2) ++ "|" ]
  where
    spaces = (`replicate` ' ')
    justify l r str = spaces l ++ str ++ spaces r
    width = length . head
    center n str = justify l (l+u) str
      where (l, u) = (n - length str) `divMod` 2
    hjoin x y = go x y
      where wx = width x
            wy = width y
            go (l:ls) (r:rs) = (l ++ r) : go ls rs
            go [] rs = map (spaces wx ++) rs
            go ls [] = map (++ spaces wy) ls

t1, t2 :: Tree Int
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))
t2 = Node t1 (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)))

main :: IO ()
main = do
  pprint t1
  pprint . fromJust $ interleave t1
  pprint . fromJust $ toList >>> rotateR >=> rotateR $ t1
$\endgroup$
0
$\begingroup$

I don't have a proof but I would consider these operations:

  • tree rotations (as in AVL trees / red-black trees)
  • removing a leaf
  • duplication: replacing a leaf $x$ by a node having two leaf children $x$
  • swapping: if a node has two leaf subtrees, swap them

My conjecture is: using tree rotations you can transform the tree into any other tree which has the same leaves, taken according to the in-order visit. E.g. the tree $(1,(2,3))$ can be rotated into $((1,2),3)$, which has the same in-order visit $1,2,3$.

If that holds, we need swaps (at least on the leaves, if not of general subtrees) so to generate all the possible leaves permutations. Alternatively, we could also take any subset of the permutation group which generates the whole group: one might check out an abstract algebra book to find a few example.

After that, leaf removal and duplication can be added so to get the wanted relation.

Again, this needs to be proved carefully -- the above one is only an intuition.

$\endgroup$
  • $\begingroup$ It doesn't seem like the operations you're defining are local to the root $\endgroup$ – Arthur B Feb 14 at 22:01
  • $\begingroup$ @ArthurB Ah, right. I only read that as "local". I think one might work only on the root by using something similar to "zippers" in functional programming, if you allow the root to have 3 pointers (left child, parent, right child). Essentially, a zipper allows one to "move" around the tree by making the node you visit the new root. This uses only root-local moves. $\endgroup$ – chi Feb 14 at 22:12
  • $\begingroup$ I agree that something like a zipper is probably part of the solution, but the constraint is to work with a binary tree. $\endgroup$ – Arthur B Feb 16 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.