Trees
While you imagine forest, trees are a fundamental data structure in computer science, used to represent hierarchical data.
NoteTrees are a type of graph but with a key distinction: they have no cycles, meaning there's only max one path between any two nodes.
Terminology
Node
A basic unit containing data and one or more pointers.
Edge
Connection between two nodes.
Root
The topmost node of the tree.
- Root has no parent.
- All other nodes are descendants of the root.
- There is always exactly one root node.
Subtree
The portion of the tree rooted at a particular node, consisting of that node together with all of its descendant nodes and the edges connecting them.
- Think of a subtree as a smaller tree growing from a branch of a larger tree.
- It has its own root (the branch) and its own structure (the leaves and branches below it).
Child
A node that is directly connected and one level below another node.
Nodes without children are called leaves.
Parent
A node that has one or more children.
Each node (except the root) has exactly one parent.
ExampleFor instance, here:
- Node A (marked green) is root.
- Nodes B and C are children of node A.
- Node A is parent of B and C
- Nodes D and E are leaves.
- One of the most common tree type is binary tree, a tree where each node has at most 2 children.
- In binary trees we additionally can distinguish:
- Left Child: The node directly connected to the left of a parent node.
- Right Child: The node directly connected to the right of a parent node.
- For instance, in the example above, node D is left child of B and C is right child of A.
Practical Applications of Binary Trees
- Binary Search Trees (BSTs)
- Organize data for efficient searching, insertion, and deletion.
- Left child nodes contain values less than the parent.
- Right child nodes contain values greater than or equal to the parent.
- Expression Trees
- Represent mathematical expressions.
- Operators are stored in parent nodes.
- Operands are stored in leaf nodes.
- Trie
- A specialized tree for fast string searching.
- Decision Trees
- Used in machine learning for decision-making processes.
- Each node represents a decision or condition.
- Consider a binary search tree (BST) used to store integers.
- The root node contains the value 10.
- Its left child contains 5, and its right child contains 15.
- This structure allows efficient searching by comparing values at each node.
When searching in a BST, always start by comparing the target value with the root.
This helps you decide whether to explore the left or right subtree.
ExampleLogical Operations on Trees
While insertion (adding new nodes) and deletion (removing nodes) operation in trees can be not specifically defined, some cases line BST has well defined process:
- Binary Search Tree (BST) Insertion:
- Start at the root.
- Compare the value to be inserted with the current node.
- Move left if the value is smaller, right if larger.
- Repeat until a null position is found, then insert the node.
- Binary Search Tree (BST) deletion:
- Deleting a leaf node:
- Simply remove the node.
- Deleting a leaf node:
