Trees in Data Structure
A basic nonlinear data structure in Python computing, trees provide a hierarchical method of data organisation and access. They are essential for putting algorithms into practice considerably more quickly than linear structures like linked lists or array-based lists. Along with the speedy searching capabilities of an ordered array, trees offer benefits like quick insertion and deletion, much like a linked list. They are widely used in systems like file directories, databases, and websites due to their inherent organisation.
Tree Terminology
Several essential words are used to comprehend trees, frequently with comparisons to actual trees or familial relationships:
Node: The fundamental building block of a tree, frequently shown in diagrams as circles. Nodes in object-oriented programming are usually objects that stand in for entities, like data structures or records.
Edge: An “edge” in data structures connects nodes or vertices. Edges are pairwise connections between vertices in graphs, which can be directed or undirected. Endpoints, or vertices joined by an edge, are adjacent. If a vertex is an endpoint, an edge is “incident” to it.
Root: The “root” is the top node in tree data structures. As trees have only one root node, it is unique because it has no parent. All other tree nodes are offspring of the root and can only be reached by edges (links). Tree diagrams usually show the root at the top and following generations or levels branching downwards, like a botanical tree or family tree.
Parent: A “parent” node in tree data structures has one or more “children” nodes below it. Except for the “root,” every node in a tree has one parent node. Like family trees, this hierarchical relationship places ancestors at the top and descendants below. Some tree implementations express “edges,” or links between nodes, by references to a node’s offspring or, less often, to its parent.
Child: Any node connected by an edge from its parent is a “child” in tree data structures. Children, or branches, are nodes right below a node. Nodes can have children.
Descendant: A descendant of u in tree data structures is any node v whose ancestor is u. Descendants are nodes below a node in the tree hierarchy. The subtree of a node includes all of its descendants, including the node itself. In a binary search tree, left descendants of a node A have key values less than A, whereas right descendants have key values larger than or equal to A.
Ancestor: An “ancestor” in tree data structures is any node higher in the hierarchy than a given node. Often derived from family trees. A node u is an ancestor of another node v if it is v or v’s parent node. A file system tree shows “cs252/” as an ancestor of “papers/”.
Sibling: Data structure trees describe siblings as two nodes with a common parent. This phrase is typically tied to real-life family connections, making it relatable. A tree’s root node has no parents and no siblings. If a node is its parent’s only child, it may not have siblings. In binary trees, p’s sibling is the “other” child of p’s parent.
Leaf Node (External Node): An external node that has no children is called a leaf node. There is only one way to get at the root. Leaf Nodes, sometimes called External Nodes, are essential to tree data structures. Leaf nodes have no children. A tree has one root node, but many leaf nodes. Internal nodes have children.
Internal Node: Internal nodes, also known as non-leaf nodes, are essential to a tree data structure’s connections to other nodes. Internal nodes have at least one child. They vary from leaf nodes, which have no offspring.
Subtree:Tree data architectures define a subtree as any node other than the root and its descendants. Like a family, a node’s subtree has all its descendants. Besides its root, a tree’s elements might create an ordered collection of smaller trees, called subtrees.
Level (or Depth): The number of generations that a node is from the root is indicated by its level. Children of a Level 0 root are at Level 1, grandchildren are at Level 2, and so forth. The number of ancestors of a node p, minus p itself, is its depth.
Key: A node’s key is a data field that is usually utilised for tasks like searching. Although integers are frequently used for example brevity, keys can be any ordered data type.
Traversing: Traversing is the process of going to each node in a tree in a predetermined order. Pre-order, in-order, and post-order traversals are common types.
Unbalanced Tree: A tree that has much more left-handed offspring than right-handed offspring, or the opposite, is said to be unbalanced. In an imbalanced tree, especially a binary search tree, the nodes are not evenly distributed on both sides of the root. The root or other node has far more offspring on its left or right side than on the other.
Binary Trees
A binary tree is a specific type of tree in which there are no more than two children per node. Multiway trees are more generic trees that have more than two children.
Binary Search Trees (BSTs)
The binary search tree (BST), an ordered binary tree intended for effective searching, is a particularly significant form. The ordering of a BST is its defining characteristic:
- Each node in A’s left subtree has a lower key than A.
- All nodes in the right subtree of a node A have key values greater than (or equal to) A’s key.
This ordering makes finding, adding, and removing nodes, which should require O(log N) time (N being the number of objects), very efficient. For this to be effective, the tree needs to be somewhat balanced. In the worst situation, an unbalanced tree may degenerate into a linked list-like structure, which would result in O(N) performance for these operations. To preserve this logarithmic efficiency, specialised balanced search trees such as Red-Black and AVL trees are available.
Representing Trees in Python
There are two primary methods for representing trees in memory:
Linked Structure: The most popular strategy. References (points) in each node that point to their offspring are used to connect the nodes, which are stored in disparate memory locations. The element and references to its parent, left child, and right child are normally stored in a node. The reference would be None if there were no parent or child. The tree itself monitors its size and maintains a reference to its root node.
Array-Based Representation: In an array, nodes are kept in designated locations. This technique is employed for certain sorts of trees, such as piles, but is less frequent for generic trees.
Class (Internal Representation)
Every element in the tree would be represented by an internal __Node class, which is frequently preceded by double underscores to indicate that it is not public. Typically, it includes:
- key: The number that is used to search and arrange the node.
- data: The real details connected to the key.
- leftChild: A reference to the node for the left child, or None in the absence of a left child.
- rightChild: A reference to the node for the right child (or None if there isn’t one).
- A reference to the parent node, or none if it’s the root, is called parent.
- For debugging, a str() function to show node contents may be introduced.
Class
This class offers methods for working with the tree structure and controls its general structure. It would contain a root node reference. Important functions consist of:
Finding a Node: The procedure begins from the root in order to locate a node with a particular key. It contrasts the key of the current node with the target key:
- The node is located if they are equivalent.
- The left subtree searches recursively if the target key is less than the current node key.
- The right subtree is searched if the target key is larger.
- The key is absent from the tree if a None reference an empty subtree is found.
Inserting a Node: Insertion uses a comparable comparison-based methodology:
- When the tree is empty, the new node becomes root.
- No? Start at the root and navigate the tree. Compare the new node’s key to the old one:
Go to the left child if they are smaller. - Go to the appropriate kid if they are greater (or equal, depending on implementation).
- Continue until the new node finds an empty space (a None reference).
Traversing the Tree:Traversing a tree involves visiting all its nodes in a predetermined order. This operation can be used to review all records for specified actions (e.g., discovering auto components from a country), but it may not be as common as finding, inserting, or deleting nodes.
- In ascending key order, in-order traversal visits left, current, and right subtrees. Because it sorts things, it is helpful for binary search trees.
- In pre-order traversal, the current node is visited first, then its left and right subtrees. useful for indenting hierarchical structures or cloning trees.
- The post-order traversal traverses the left, right, and current subtrees. aids expression tree evaluation and removal.
Because trees are recursive, traversals are often recursive. They can be implemented iteratively on a stack.
Balanced trees, especially binary search trees, are good for discovering, adding, and removing ordered data. They address several computing problems due to their hierarchical nature and specific traversal techniquecs.
Example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, value):
if not self.root:
self.root = Node(value)
else:
self._insert_recursive(self.root, value)
def _insert_recursive(self, current, value):
if value < current.value:
if current.left:
self._insert_recursive(current.left, value)
else:
current.left = Node(value)
else:
if current.right:
self._insert_recursive(current.right, value)
else:
current.right = Node(value)
def inorder_traversal(self, node, result):
if node:
self.inorder_traversal(node.left, result)
result.append(node.value)
self.inorder_traversal(node.right, result)
return result
# Example usage
bt = BinaryTree()
bt.insert(10)
bt.insert(5)
bt.insert(15)
print("Inorder Traversal:", bt.inorder_traversal(bt.root, []))Output:
Inorder Traversal: [5, 10, 15]