A tree is a hierarchical data structure consisting of nodes connected by edges. Each node can have zero or more child nodes, except for the root node which has no parent. Binary trees, where each node has at most two children, are a common type.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
A graph is a collection of vertices (nodes) and edges that connect these vertices. Graphs can be directed or undirected. They are used to represent relationships between objects.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
A heap is a specialized tree - based data structure that satisfies the heap property. In a min - heap, the value of each node is less than or equal to the values of its children. Heaps are often used for priority queues.
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))
A hash table is a data structure that uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. In Python, dictionaries are a built - in implementation of hash tables.
hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
print(hash_table['apple'])
As shown in the previous code examples, we can create trees by defining node classes and connecting them, graphs as dictionaries, heaps using the heapq
module, and hash tables as Python dictionaries.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value < self.value:
if self.left is None:
self.left = TreeNode(value)
else:
self.left.insert(value)
else:
if self.right is None:
self.right = TreeNode(value)
else:
self.right.insert(value)
root = TreeNode(5)
root.insert(3)
root.insert(7)
graph = {'A': ['B']}
graph['B'] = []
graph['A'].append('C')
graph['C'] = ['A']
heappush
to insert and heappop
to delete the smallest element.import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappop(heap)
del
keyword to delete.hash_table = {'apple': 1}
hash_table['banana'] = 2
del hash_table['apple']
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(self):
result = []
if self.left:
result.extend(self.left.inorder_traversal())
result.append(self.value)
if self.right:
result.extend(self.right.inorder_traversal())
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(root.inorder_traversal())
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
print(vertex)
visited.add(vertex)
stack.extend(graph[vertex])
dfs(graph, 'A')
heapq
module in Python instead of implementing a heap from scratch for better performance.class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if value < self.value:
if self.left is None:
self.left = TreeNode(value)
else:
self.left.insert(value)
elif value > self.value:
if self.right is None:
self.right = TreeNode(value)
else:
self.right.insert(value)
else:
print(f"Value {value} already exists in the tree.")
root = TreeNode(5)
root.insert(5)
graph = {'A': ['B']}
vertex = 'C'
if vertex in graph:
graph[vertex].append('D')
else:
print(f"Vertex {vertex} does not exist in the graph.")
import heapq
heap = []
if heap:
heapq.heappop(heap)
else:
print("Heap is empty.")
get
method to avoid key - error exceptions.hash_table = {'apple': 1}
value = hash_table.get('banana', 'Key not found')
print(value)
Advanced data structures in Python offer powerful tools for solving complex problems efficiently. By understanding the fundamental concepts, usage methods, common practices, and best practices, developers can make informed decisions about which data structure to use for a given task. Whether it’s representing hierarchical data with trees, modeling relationships with graphs, managing priorities with heaps, or performing fast lookups with hash tables, these data structures are essential for building high - performance applications.
heapq
module and dictionaries