inverting/rotating n-ary trees


  • Winner of the 2016 Presidential Election

    Okay, so for some reason or another (some post here mentioned it) I looked up what "inverting a binary tree" means. I haven't actually read anything beyond the definition of the challenge yet, which was this one from here:

    The inverse of an empty tree is the empty tree. The inverse of a tree with root rr, and subtrees right and left, is a tree with root rr, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

    So given that challenge, I though to myself "isn't inverting a well-designed binary tree O(1)?" Then I expanded a bit, and thinking of inversion as rotation and/or change in direction, I came up with something like:

    Given an n-ary tree with the following structure:

    public partial class Node<T>
    {
    	public T value
    	public Node<T> parent { get; set; }
    	public Node<T>[] children { get; }
    	
    	// Root element has null parent
    	public Node(int dimensions)
    	{
    		this.parent = null;
    		this.children = new Node<T>[dimensions];
    	}
    
    	public Node(Node<T> parent, int dimensions)
    	{
    		this.parent = parent;
    		this.children = new Node<T>[dimensions];
        }
    }
    
    public partial class NAryTree<T> where T : IComparable
    {
    	public int dimensions { get; }
    	private Node<T> root { get; set; }
    	
    	public NAryTree(int dimensions)
    	{
    		this.dimensions = dimensions;
    		this.root = null;
    	}
    }
    

    Then one can treat inversion of the tree as a property of how one navigates the children array of each Node<T> (which is treated like a loop), and formulate the tree operations to account for the rotation in use. Only two properties need to be added:

    • offset, with 0 being the default, and
    • direction, represented as ±1.

    These two properties can be combined into one property as a signed integer, or kept separate.

    For example, iterating through a children array would look like:

    		for (int i = 0; i < dimensions; i++)
    		{
    			int index = (offset + direction * i) % dimensions;
    			if (node.children[index] != null)
    			{
    				DoSomething(node.children[index]);
    			}
    		}
    

    (Note: I'm assuming % works as expected. Vary as necessary.)

    Because only these two properties need to change, inversions of such n-ary trees are O(1).


    Now why is this in "Coding Help"? Because I want to know if :arrow_up: is right or if I'm missing something. All the solutions I've seen on a quick Google search do the "switch every Node<T>'s children around" approach.


  • Discourse touched me in a no-no place

    @Dreikin said in inverting/rotating n-ary trees:

    Because I want to know if is right or if I'm missing something.

    Why are you exposing the list of children as an array? If you just exposed a way to iterate over them, you would be able to lock the complexity away inside.


  • Winner of the 2016 Presidential Election

    @dkf said in inverting/rotating n-ary trees:

    @Dreikin said in inverting/rotating n-ary trees:

    Because I want to know if is right or if I'm missing something.

    Why are you exposing the list of children as an array? If you just exposed a way to iterate over them, you would be able to lock the complexity away inside.

    Laziness, more-or-less. In this model, the nodes aren't (supposed) to be publicly accessible (despite the access modifier) and instead only worked with through the Tree class. I probably should have made them an inner class of the Tree given that, I guess.


  • Winner of the 2016 Presidential Election

    Thinking about it, any arbitrary reordering of the axes ought to be O(n) where n is the number of dimensions:

    public partial class NAryTree<T> where T : IComparable
    {
    	class Node
    	{
    		public T value
    		public Node parent { get; set; }
    		public Node[] children { get; }
    
    		// Root element has null parent
    		public Node(int dimensions)
    		{
    			this.parent = null;
    			this.children = new Node[dimensions];
    		}
    
    		public Node(Node parent, int dimensions)
    		{
    			this.parent = parent;
    			this.children = new Node[dimensions];
    		}
    	}
    	
    	public int dimensions { get; }
    	private Node root { get; set; }
    	private int[] ordering { get; set; }
    
    	public NAryTree(int dimensions)
    	{
    		this.dimensions = dimensions;
    		this.root = null;
    		this.ordering = new int[dimensions];
    		for (int i = 0; i < dimensions; i++)
    		{
    			ordering[i] = i;
    		}
    	}
    
    	private void PrintChildren(Node node)
    	{
    		foreach (var index in ordering)
    		{
    			PrintNode(node.children[index]);
    		}
    	}
    
    	private void PrintNode(Node node)
    	{
    		Console.WriteLine(node.value);
    	}
    }
    

    (I'm assuming insertion and balancing and other similar operations where the user of the tree doesn't see evidence of the ordering don't bother with the reordered index - they just treat it like normal. Rotations/Inversions are just views on the tree - they shouldn't affect the internal structure of it.)


Log in to reply
 

Looks like your connection to What the Daily WTF? was lost, please wait while we try to reconnect.