class Graphlb::DataStructures::TreeNode

Overview

TreeNode Class Description

This class models the nodes for an N-ary tree data structure. The nodes are named, and have a place-holder for the node data (i.e., content of the node). The node names are required to be unique amongst the sibling/peer nodes. Note that the name is implicitly used as an ID within the data structure).

The node's content is not required to be unique across different nodes in the tree, and can be +nil+ as well.

The class provides various methods to navigate the tree, traverse the structure, modify contents of the node, change position of the node in the tree, and to make structural changes to the tree.

A node can have any number of child nodes attached to it and hence can be used to create N-ary trees. Access to the child nodes can be made in order (with the conventional left to right access), or randomly.

The node also provides direct access to its parent node as well as other superior parents in the path to root of the tree. In addition, a node can also access its sibling nodes, if present.

Direct Known Subclasses

Defined in:

graphlb/data_structures/tree.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(name, content = nil) #

Creates a new node with a name and optional content. The node name is expected to be unique within the tree.

The content can be of type Int32, and defaults to +nil+.

@param [Object] name Name of the node. Conventional usage is to pass a String

@param [Object] content Content of the node.

@raise [ArgumentError] Raised if the node name is empty.


[View source]

Instance Method Detail

def <<(child) #

Convenience synonym for {TreeNode#add} method.

This method allows an easy mechanism to add node hierarchies to the tree on a given path via chaining the method calls to successive child nodes.

@example Add a child and grand-child to the root root << child << grand_child

@param [TreeNode] child the child node to add.

@return [TreeNode] The added child node.


[View source]
def [](name_or_index, num_as_name = false) #

Returns the requested node from the set of immediate children.

  • If the +name+ argument is an Integer, then the in-sequence array of children is accessed using the argument as the index (zero-based). However, if the second optional +num_as_name+ argument is +true+, then the +name+ is used literally as a name, and NOT as an index
  • If the +name+ argument is NOT an Integer, then it is taken to be the name of the child node to be returned.

If a non-+Integer+ +name+ is passed, and the +num_as_name+ parameter is also +true+, then a warning is thrown (as this is a redundant use of the +num_as_name+ flag.)

@param [String|Number] name_or_index Name of the child, or its positional index in the array of child nodes.

@param [Boolean] num_as_name Whether to treat the +Integer+ +name+ argument as an actual name, and NOT as an index to the children array.

@return [TreeNode] the requested child node. If the index in not in range, or the name is not present, then a +nil+ is returned.

@raise [Error] Raised if the +name_or_index+ argument is +nil+.


[View source]
def add(child, at_index = -1) #

Adds the specified child node to this node.

This method can also be used for grafting a subtree into this node's tree, if the specified child node is the root of a subtree (i.e., has child nodes under it).

this node becomes parent of the node passed in as the argument, and the child is added as the last child ("right most") in the current set of children of this node

@param [TreeNode] child The child node to add.

@param [optional, Number] at_index The optional position where the node is

                               to be inserted.

@return [TreeNode] The added child node.

@raise [Error] This exception is raised if another child node with

            the same name exists, or if an invalid insertion
            position is specified.

@raise [Error] This exception is raised if a +nil+ node is passed

            as the argument.

[View source]
def children : Array(Graphlb::DataStructures::TreeNode) #

Method oveloading of the children method

An array of all the immediate children of this node. The child nodes are ordered "left-to-right" in the returned array.

@return [Array<TreeNode>] An array of the child nodes.


[View source]
def children(&block) #

An array of all the immediate children of this node. The child nodes are ordered "left-to-right" in the returned array.

@param [object] block

@yieldparam child [TreeNode] Each child node.

@return [TreeNode] This node


[View source]
def content : Int32? #

Content of this node. Can be +nil+. Note that there is no uniqueness constraint related to this attribute.


[View source]
def content=(content : Int32?) #

Content of this node. Can be +nil+. Note that there is no uniqueness constraint related to this attribute.


[View source]
def each(&block) #

Traverses each node (including this node) of the (sub)tree rooted at this node by yielding the nodes to the specified block.

The traversal is depth-first and from left-to-right in pre-ordered sequence.

@param [Object] block @yieldparam node [TreeNode] Each node.

@return [TreeNode] this node


[View source]
def each #

Traverses each node (including this node) of the (sub)tree rooted at this node

@return [Enumerator] an enumerator on this tree


[View source]
def each_leaf #

Method oveloading of the each_leaf method without block parameter

@return [Array<TreeNode>] An array of the leaf nodes


[View source]
def each_leaf(&block) #

Yields every leaf node of the (sub)tree rooted at this node to the specified block.

May yield this node as well if this is a leaf node. Leaf traversal is depth-first and left-to-right.

@param [Object] block @yieldparam node [TreeNode] Each leaf node.

@return [TreeNode] this node,


[View source]
def first_sibling #

First sibling of this node. If this is the root node, then returns itself.

'First' sibling is defined as follows:

First sibling:: The left-most child of this node's parent, which may be this node itself

@return [TreeNode] The first sibling node.


[View source]
def has_children? #

Returns true if the this node has any child node.

@return [Boolean] +true+ if child nodes exist.


[View source]
def has_content? #

Returns true if this node has content.

@return [Boolean] +true+ if the node has content.


[View source]
def in_degree #

The incoming edge-count of this node.

In-degree is defined as: In-degree:: Number of edges arriving at the node (0 for root, 1 for all other nodes)

  • In-degree = 0 for a root or orphaned node
  • In-degree = 1 for a node which has a parent

@return [Integer] The in-degree of this node.


[View source]
def insertion_range #

Return a range of valid insertion positions. Used in the #add method.


[View source]
def is_first_sibling? #

Returns true if this node is the first sibling at its level.

@return [Boolean] true if this is the first sibling.


[View source]
def is_last_sibling? #

Returns true if this node is the last sibling at its level.

@return [Boolean] +true+ if this is the last sibling.


[View source]
def is_leaf? #

Returns true if this node is a leaf - i.e., one without any children.

@return [Boolean] +true+ if this is a leaf node.


[View source]
def is_only_child? #

Returns true if this node is the only child of its parent.

As a special case, a root node will always return +true+.

@return [Boolean] +true+ if this is the only child of its parent.


[View source]
def is_root? #

Returns true if this is a root node. Note that orphaned children will also be reported as root nodes.

@return [Boolean] +true+ if this is a root node.


[View source]
def lam(node, prefix) #

Helper function for print_tree method to print the tree with given root


[View source]
def last_sibling #

Last sibling of this node. If this is the root node, then returns itself.

'Last' sibling is defined as follows:

Last sibling:: The right-most child of this node's parent, which may be this node itself

@return [TreeNode] The last sibling node.


[View source]
def name : String #

Name of this node. Expected to be unique within the tree.

Note that the name attribute really functions as an ID within the tree structure, and hence the uniqueness constraint is required.


[View source]
def next_sibling #

Next sibling for this node. The next node is defined as the node to right of this node.

Will return +nil+ if no subsequent node is present, or if this is a root node.

@return [treeNode] the next sibling node, if present.


[View source]
def node_depth #

Depth of this node in its tree. Depth of a node is defined as:

Depth:: Length of the node's path to its root. Depth of a root node is zero.

@return [Integer] Depth of this node.


[View source]
def node_height #

Height of the (sub)tree from this node. Height of a node is defined as:

Height:: Length of the longest downward path to a leaf from the node.

  • Height from a root node is height of the entire tree.
  • The height of a leaf node is zero.

@return [Integer] Height of the node.


[View source]
def out_degree #

The outgoing edge-count of this node.

Out-degree is defined as: Out-degree:: Number of edges leaving the node (zero for leafs)

@return [Integer] The out-degree of this node.


[View source]
def parent : TreeNode? #

Parent of this node. Will be +nil+ for a root node.


[View source]
def parent=(parent) #

Method to set the parent node for this node. This method should NOT be invoked by client code.

@param [TreeNode] parent The parent node.

@return [TreeNode] The parent node.


[View source]
def parentage #

An array of ancestors of this node in reversed order (the first element is the immediate parent of this node).

Returns +nil+ if this is a root node.

@return [Array<TreeNode>] An array of ancestors of this node @return [nil] if this is a root node.


[View source]
def previous_sibling #

Previous sibling of this node. Previous node is defined to be the node to left of this node.

Will return +nil+ if no predecessor node is present, or if this is a root node.

@return [treeNode] the previous sibling node, if present.


[View source]
def print_tree(level = self.node_depth, max_depth = nil) #

Pretty prints the (sub)tree rooted at this node.

@param [Integer] level The indentation level (4 spaces) to start with. @param [Integer] max_depth optional maximum depth at which the printing

                       with stop.

[View source]
def remove!(child) #

Removes the specified child node from this node.

This method can also be used for pruning a sub-tree, in cases where the removed child node is the root of the sub-tree to be pruned.

The removed child node is orphaned but accessible if an alternate reference exists. If accessible via an alternate reference, the removed child will report itself as a root node for its sub-tree.

@param [TreeNode] child The child node to remove.

@return [TreeNode] The removed child node, or +nil+ if a +nil+ was passed in as argument.


[View source]
def remove_from_parent! #

Removes this node from its parent. This node becomes the new root for its subtree.

If this is the root node, then does nothing.

@return [TreeNode] +self+ (the removed node) if the operation is

                           successful, +nil+ otherwise.

[View source]
def rename(new_name) #

Renames the node and updates the parent's reference to it

@param [Object] new_name Name of the node. Conventional usage is to pass a

                     String (Integer names may cause *surprises*)

@return [Object] The old name


[View source]
def replace!(old_child, new_child) #

Replaces the specified child node with another child node on this node.

@param [TreeNode] old_child The child node to be replaced. @param [TreeNode] new_child The child node to be replaced with.

@return [TreeNode] The removed child node


[View source]
def replace_with(node) #

Replaces the node with another node

@param [TreeNode] node The node to replace this node with

@return [TreeNode] The replaced child node


[View source]
def root #

Root node for the (sub)tree to which this node belongs. A root node's root is itself.

@return [TreeNode] Root of the (sub)tree.


[View source]
def set_as_root! #

Method to set this node as a root node.

@return +nil+.


[View source]
def siblings #

An array of siblings for this node. This node is excluded.

@return [Array<TreeNode>] Array of siblings of this node. Will

                       return an empty array for *root*

[View source]