Tree Structures¶
The rite.collections.tree subpackage provides tree-related data structures, including generic trees, binary trees, tries, and nested set representations.
Tree Collections Module¶
Provides tree data structures and hierarchical data management.
Classes:¶
- NestedSetStructure: Hierarchical parent-child relationship manager
- TreeNode: Generic tree node with children
- BinaryTreeNode: Binary tree node implementation
- Trie: Prefix tree for string operations
Classes¶
BinaryTreeNode(value: Any, left: BinaryTreeNode | None = None, right: BinaryTreeNode | None = None)
¶
BinaryTreeNode Class¶
A binary tree node with left and right children.
Parameters¶
value : Any The value stored in this node. left : BinaryTreeNode | None Left child node. right : BinaryTreeNode | None Right child node.
Initialize a binary tree node.
value: The value to store.
left: Left child node.
right: Right child node.
Functions¶
get_height() -> int
¶
Get height of subtree rooted at this node.
int: Height of subtree.
has_left_child() -> bool
¶
Check if node has left child.
bool: True if left child exists.
has_right_child() -> bool
¶
Check if node has right child.
bool: True if right child exists.
inorder_traversal() -> list[BinaryTreeNode]
¶
Perform in-order traversal (left, root, right).
list[Any]: Values in in-order.
is_leaf() -> bool
¶
Check if node is a leaf.
bool: True if node has no children.
postorder_traversal() -> list[BinaryTreeNode]
¶
Perform post-order traversal (left, right, root).
list[Any]: Values in post-order.
preorder_traversal() -> list[BinaryTreeNode]
¶
Perform pre-order traversal (root, left, right).
list[Any]: Values in pre-order.
traverse_inorder() -> list[BinaryTreeNode]
¶
Alias for inorder_traversal for compatibility.
traverse_postorder() -> list[BinaryTreeNode]
¶
Alias for postorder_traversal for compatibility.
traverse_preorder() -> list[BinaryTreeNode]
¶
Alias for preorder_traversal for compatibility.
NestedSetStructure()
¶
Nested Set Structure Class¶
A structure to track items and their hierarchical relationships. Supports multi-level trees with parent/child tracking. Useful for scenarios like recursive publishing, dependency resolution, or graph-like traversal.
Initialize the nested set structure.
Functions¶
add(item: Any, parent: Any | None = None) -> None
¶
Add an item to the structure, optionally specifying a parent.
children(item: Any) -> list[Any]
¶
Return the children of the given item. If the item has no children, returns an empty list.
nested_items() -> list[Any]
¶
Return a nested, flattened list of items (including children) in insertion order. Maintains hierarchy order.
original(item: Any) -> Any
¶
Return the original object stored in the set that equals item,
or item itself if not found. This is useful for matching
back to canonical instances.
parent(item: Any) -> Any | None
¶
Return the parent of the given item, or None if it has no parent.
TreeNode(value: Any, children: list[Self] | None = None)
¶
TreeNode Class¶
A generic tree node that can have multiple children.
Parameters¶
value : Any The value stored in this node. children : list[TreeNode] | None Optional list of child nodes.
Initialize a tree node.
value: The value to store in this node.
children: Optional list of child nodes.
Functions¶
add_child(child: Self) -> None
¶
Add a child node.
child: The child node to add.
get_ancestors() -> list[Self]
¶
Get all ancestor nodes from parent to root.
list[TreeNode]: List of ancestors in order (parent to root).
get_depth() -> int
¶
Get the depth of this node (distance from root).
int: Depth of node (root is 0).
get_height() -> int
¶
Get the height of the subtree rooted at this node.
int: Height of subtree (leaf is 0).
get_siblings() -> list[Self]
¶
Get all sibling nodes (nodes with same parent).
list[TreeNode]: List of sibling nodes.
is_leaf() -> bool
¶
Check if this node is a leaf (has no children).
bool: True if node has no children.
is_root() -> bool
¶
Check if this node is a root (has no parent).
bool: True if node has no parent.
remove_child(child: Self) -> bool
¶
Remove a child node.
child: The child node to remove.
bool: True if child was removed, False if not found.
traverse_levelorder() -> list[Self]
¶
Traverse tree in level-order (breadth-first).
list[TreeNode]: Nodes in level-order.
traverse_postorder() -> list[Self]
¶
Traverse tree in post-order (children, then root).
list[TreeNode]: Nodes in post-order.
traverse_preorder() -> list[Self]
¶
Traverse tree in pre-order (root, then children).
list[TreeNode]: Nodes in pre-order.
Trie()
¶
Trie Class¶
A prefix tree (trie) for efficient string operations like autocomplete, spell checking, and prefix matching.
Initialize an empty trie.
Functions¶
autocomplete(prefix: str) -> list[str]
¶
Return all completions for the given prefix.
delete(word: str) -> bool
¶
Delete a word from the trie.
word: The word to delete.
bool: True if word was deleted, False if not found.
get(word: str) -> Any | None
¶
Get the value associated with a word.
word: The word to look up.
Any | None: Associated value or None if not found.
get_all_words() -> list[str]
¶
Get all words stored in the trie.
list[str]: All words in the trie.
get_words_with_prefix(prefix: str) -> list[str]
¶
Get all words that start with given prefix.
prefix: The prefix to match.
list[str]: List of words with the prefix.
insert(word: str, value: Any | None = None) -> None
¶
Insert a word into the trie.
word: The word to insert.
value: Optional value to associate with the word.
search(word: str) -> bool
¶
Search for an exact word in the trie.
word: The word to search for.
bool: True if word exists in trie.
starts_with(prefix: str) -> bool
¶
Check if any word in trie starts with given prefix.
prefix: The prefix to check.
bool: True if prefix exists in trie.
Modules¶
binary_tree_node
¶
Binary Tree Node¶
Binary tree node with left and right children.
Classes¶
BinaryTreeNode(value: Any, left: BinaryTreeNode | None = None, right: BinaryTreeNode | None = None)
¶
BinaryTreeNode Class¶
A binary tree node with left and right children.
Parameters¶
value : Any The value stored in this node. left : BinaryTreeNode | None Left child node. right : BinaryTreeNode | None Right child node.
Initialize a binary tree node.
value: The value to store.
left: Left child node.
right: Right child node.
Functions¶
get_height() -> int
¶Get height of subtree rooted at this node.
int: Height of subtree.
has_left_child() -> bool
¶Check if node has left child.
bool: True if left child exists.
has_right_child() -> bool
¶Check if node has right child.
bool: True if right child exists.
inorder_traversal() -> list[BinaryTreeNode]
¶Perform in-order traversal (left, root, right).
list[Any]: Values in in-order.
is_leaf() -> bool
¶Check if node is a leaf.
bool: True if node has no children.
postorder_traversal() -> list[BinaryTreeNode]
¶Perform post-order traversal (left, right, root).
list[Any]: Values in post-order.
preorder_traversal() -> list[BinaryTreeNode]
¶Perform pre-order traversal (root, left, right).
list[Any]: Values in pre-order.
traverse_inorder() -> list[BinaryTreeNode]
¶Alias for inorder_traversal for compatibility.
traverse_postorder() -> list[BinaryTreeNode]
¶Alias for postorder_traversal for compatibility.
traverse_preorder() -> list[BinaryTreeNode]
¶Alias for preorder_traversal for compatibility.
nested_set
¶
Nested Set Structure Module¶
This module provides a NestedSetStructure class that allows for the
management of hierarchical relationships between items. It supports
adding items with parent-child relationships, retrieving children and parents,
and provides a way to retrieve all items in a nested, flattened order.
Classes¶
NestedSetStructure()
¶
Nested Set Structure Class¶
A structure to track items and their hierarchical relationships. Supports multi-level trees with parent/child tracking. Useful for scenarios like recursive publishing, dependency resolution, or graph-like traversal.
Initialize the nested set structure.
Functions¶
add(item: Any, parent: Any | None = None) -> None
¶Add an item to the structure, optionally specifying a parent.
children(item: Any) -> list[Any]
¶Return the children of the given item. If the item has no children, returns an empty list.
nested_items() -> list[Any]
¶Return a nested, flattened list of items (including children) in insertion order. Maintains hierarchy order.
original(item: Any) -> Any
¶Return the original object stored in the set that equals item,
or item itself if not found. This is useful for matching
back to canonical instances.
parent(item: Any) -> Any | None
¶Return the parent of the given item, or None if it has no parent.
tree_node
¶
Tree Node¶
Generic tree node implementation with children and parent tracking.
Classes¶
TreeNode(value: Any, children: list[Self] | None = None)
¶
TreeNode Class¶
A generic tree node that can have multiple children.
Parameters¶
value : Any The value stored in this node. children : list[TreeNode] | None Optional list of child nodes.
Initialize a tree node.
value: The value to store in this node.
children: Optional list of child nodes.
Functions¶
add_child(child: Self) -> None
¶Add a child node.
child: The child node to add.
get_ancestors() -> list[Self]
¶Get all ancestor nodes from parent to root.
list[TreeNode]: List of ancestors in order (parent to root).
get_depth() -> int
¶Get the depth of this node (distance from root).
int: Depth of node (root is 0).
get_height() -> int
¶Get the height of the subtree rooted at this node.
int: Height of subtree (leaf is 0).
get_siblings() -> list[Self]
¶Get all sibling nodes (nodes with same parent).
list[TreeNode]: List of sibling nodes.
is_leaf() -> bool
¶Check if this node is a leaf (has no children).
bool: True if node has no children.
is_root() -> bool
¶Check if this node is a root (has no parent).
bool: True if node has no parent.
remove_child(child: Self) -> bool
¶Remove a child node.
child: The child node to remove.
bool: True if child was removed, False if not found.
traverse_levelorder() -> list[Self]
¶Traverse tree in level-order (breadth-first).
list[TreeNode]: Nodes in level-order.
traverse_postorder() -> list[Self]
¶Traverse tree in post-order (children, then root).
list[TreeNode]: Nodes in post-order.
traverse_preorder() -> list[Self]
¶Traverse tree in pre-order (root, then children).
list[TreeNode]: Nodes in pre-order.
trie
¶
Trie (Prefix Tree)¶
A trie data structure for efficient string prefix operations.
Classes¶
Trie()
¶
Trie Class¶
A prefix tree (trie) for efficient string operations like autocomplete, spell checking, and prefix matching.
Initialize an empty trie.
Functions¶
autocomplete(prefix: str) -> list[str]
¶Return all completions for the given prefix.
delete(word: str) -> bool
¶Delete a word from the trie.
word: The word to delete.
bool: True if word was deleted, False if not found.
get(word: str) -> Any | None
¶Get the value associated with a word.
word: The word to look up.
Any | None: Associated value or None if not found.
get_all_words() -> list[str]
¶Get all words stored in the trie.
list[str]: All words in the trie.
get_words_with_prefix(prefix: str) -> list[str]
¶Get all words that start with given prefix.
prefix: The prefix to match.
list[str]: List of words with the prefix.
insert(word: str, value: Any | None = None) -> None
¶Insert a word into the trie.
word: The word to insert.
value: Optional value to associate with the word.
search(word: str) -> bool
¶Search for an exact word in the trie.
word: The word to search for.
bool: True if word exists in trie.
starts_with(prefix: str) -> bool
¶Check if any word in trie starts with given prefix.
prefix: The prefix to check.
bool: True if prefix exists in trie.
options: show_root_heading: true show_source: false heading_level: 2