Trees are hierarchical data structures that consist of nodes with a parent-child relationship. They have a wide range of applications in areas such as databases, file systems, search algorithms, and memory management. Let’s dive into the different types of tree data structures, including Binary Trees, Binary Search Trees (BSTs), AVL Trees, and B-Trees.
Binary Trees
A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left and right children. Binary Trees are used in various applications, including expression parsing, hierarchical data modeling, and search algorithms.
Properties of Binary Trees:
Each node has at most two children.
- Height: The length of the longest path from the root to a leaf node.
- Full Binary Tree: Every node has either 0 or 2 children.
- Complete Binary Tree: All levels, except possibly the last, are fully filled, and all nodes are as far left as possible.
- Perfect Binary Tree: All internal nodes have exactly two children, and all leaf nodes are at the same level.
Code Example: Basic Binary Tree Structure in Python
class TreeNode:
def __init__(self, value: int):
self.value = value
self.left = None
self.right = None
# Example of creating a binary tree
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(20)
Binary Search Trees (BSTs)
A Binary Search Tree (BST) is a type of binary tree with an additional constraint:
BST Property:
For each node, all nodes in the left subtree contain values less than the node’s value, and all nodes in the right subtree contain values greater than the node’s value.
This property makes BSTs efficient for searching, insertion, and deletion operations, with an average time complexity of O(log n). However, if the tree becomes unbalanced (like a linked list), the time complexity can degrade to O(n).
Operations in a BST:
- Insertion: Insert nodes while maintaining the BST property.
- Search: Traverse left or right based on the value to be found.
- Deletion: Delete nodes while adjusting subtrees to maintain the BST property.
Code Example: Binary Search Tree Insertion and Search
class TreeNode:
def __init__(self, value: int):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value: int) -> None:
self.root = self._insert_recursive(self.root, value)
def _insert_recursive(self, node: TreeNode, value: int) -> TreeNode:
if not node:
return TreeNode(value)
if value < node.value:
node.left = self._insert_recursive(node.left, value)
else:
node.right = self._insert_recursive(node.right, value)
return node
def search(self, value: int) -> bool:
return self._search_recursive(self.root, value)
def _search_recursive(self, node: TreeNode, value: int) -> bool:
if not node:
return False
if value == node.value:
return True
elif value < node.value:
return self._search_recursive(node.left, value)
else:
return self._search_recursive(node.right, value)
AVL Trees
An AVL Tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node (balance factor) is at most 1. AVL trees automatically maintain this balance property after each insertion or deletion by performing rotations.
Properties of AVL Trees:
- Balance Factor: For each node, the difference between the heights of the left and right subtrees is at most 1.
- Rotations: AVL trees use left rotations and right rotations (and combinations like left-right and right-left rotations) to rebalance the tree after insertion or deletion.
Code Example: AVL Tree Insertion (with Basic Rotation)
class TreeNode:
def __init__(self, value: int):
self.value = value
self.left = None
self.right = None
self.height = 1 # Height of the node for balance factor calculation
class AVLTree:
def insert(self, root: TreeNode, value: int) -> TreeNode:
# Step 1: Perform standard BST insertion
if not root:
return TreeNode(value)
if value < root.value:
root.left = self.insert(root.left, value)
else:
root.right = self.insert(root.right, value)
# Step 2: Update height of this ancestor node
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
# Step 3: Get balance factor to check if unbalanced
balance = self.get_balance(root)
# Step 4: Perform rotations to balance the tree
# Left-Left Case
if balance > 1 and value < root.left.value:
return self.right_rotate(root)
# Right-Right Case
if balance < -1 and value > root.right.value:
return self.left_rotate(root)
# Left-Right Case
if balance > 1 and value > root.left.value:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right-Left Case
if balance < -1 and value < root.right.value:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def left_rotate(self, z: TreeNode) -> TreeNode:
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def right_rotate(self, z: TreeNode) -> TreeNode:
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def get_height(self, node: TreeNode) -> int:
return node.height if node else 0
def get_balance(self, node: TreeNode) -> int:
return self.get_height(node.left) - self.get_height(node.right) if node else 0
Explanation of Rotations
- Left Rotation: Used when a right-heavy imbalance occurs.
- Right Rotation: Used when a left-heavy imbalance occurs.
- Left-Right and Right-Left Rotations: Combination of two rotations for balancing more complex cases.
B-Trees
A B-Tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in O(log n) time. B-Trees are commonly used in databases and file systems due to their efficient disk usage and balanced structure.
Properties of B-Trees:
- Order of the Tree (m): Defines the maximum number of children each node can have.
- Node Structure: Each node can contain multiple keys, and the number of children is one more than the number of keys.
- Balanced: B-Trees are kept balanced by ensuring all leaf nodes are at the same depth.
- Split and Merge: Nodes may be split or merged during insertions and deletions to maintain balance.
Code Example: Basic B-Tree Node Structure
The following code demonstrates the basic structure of B-Tree nodes and insertion logic.
class BTreeNode:
def __init__(self, t: int, leaf: bool):
self.t = t # Minimum degree (defines the range for the number of keys)
self.leaf = leaf # True if node is a leaf, otherwise False
self.keys = [] # List of keys in the node
self.children = [] # List of child pointers
def insert_non_full(self, key):
i = len(self.keys) - 1
if self.leaf:
# Insert new key in leaf node
self.keys.append(0) # Append a dummy value for shifting
while i >= 0 and key < self.keys[i]:
self.keys[i + 1] = self.keys[i]
i -= 1
self.keys[i + 1] = key
else:
# Find the child to insert the key
while i >= 0 and key < self.keys[i]:
i -= 1
i += 1
# Split the child if full
if len(self.children[i].keys) == 2 * self.t - 1:
self.split_child(i, self.children[i])
if key > self.keys[i]:
i += 1
self.children[i].insert_non_full(key)
def split_child(self, i, y):
t = self.t
z = BTreeNode(y.t, y.leaf)
self.children.insert(i + 1, z)
self.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t:(2 * t - 1)]
y.keys = y.keys[0:(t - 1)]
if not y.leaf:
z.children = y.children[t:(2 * t)]
y.children = y.children[0:t]
Explanation
Insertion: Insert keys in a non-full node or split nodes when full.
- Split Operation: Ensures the node doesn’t exceed the maximum number of keys by splitting it into two nodes.
Advantages of B-Trees:
- Ideal for storage systems that read/write large blocks of data.
- Keeps data balanced, ensuring O(log n) access time.