Tree based DSA (II) (Data Structures & Algorithms)

Title: Tree Based Data Structures and Algorithms (Python) - Part II

Why This Matters

In this tutorial, we will delve deeper into tree-based data structures and algorithms using Python. Understanding these concepts is crucial for tackling complex problems, optimizing code efficiency, and preparing for coding interviews and competitive programming contests. Real-world applications include parsing HTML documents, compiling computer programs, and implementing databases.

Prerequisites

To follow this tutorial, you should have a good understanding of:

1. Python basics (variables, functions, loops, lists)
2. Recursion
3. Basic data structures (arrays, stacks, queues)

Core Concept

Definition and Types of Trees

A tree is a hierarchical data structure consisting of nodes connected by edges, where each node has at most one incoming edge (the root), and every other node has exactly one incoming edge and zero or more outgoing edges. The nodes can store data, while the edges represent relationships between nodes.

There are several types of trees, including:

1. Binary Tree: A tree where each node has at most two children (left and right).
2. Full Binary Tree: A binary tree in which every node except possibly the leaves has two children.
3. Perfect Binary Tree: A full binary tree in which all internal nodes have exactly two children, and all leaves are at the same depth.
4. Complete Binary Tree: A binary tree in which, apart from possibly one (or both) ends, every level is completely filled, and all nodes are as far left as possible.
5. Balanced Binary Tree: A binary search tree where the difference between heights of left and right subtrees for each node is not more than 1.
6. Binary Search Tree (BST): A binary tree data structure in which the key of every node is greater than or equal to the keys of its left child and less than or equal to the keys of its right child, providing efficient search, insertion, and deletion operations.
7. AVL Tree: A self-balancing binary search tree that maintains a balance factor for each node to ensure that the height difference between subtrees is not more than 1.
8. B-Tree: A multi-level index data structure used in databases, file systems, and other applications to efficiently store large amounts of sorted data.
9. B+ Tree: An extension of the B-tree with a larger number of children per node and an additional level (the leaf level) that stores keys directly.
10. Red-Black Tree: A self-balancing binary search tree that uses color bits to maintain balance, allowing for faster insertion, deletion, and searching compared to AVL trees.

Traversal Methods

There are four common methods for traversing a tree:

1. Inorder (Left-Root-Right): Visit the left subtree, then the current node, and finally the right subtree. This method is used for in-place sorting of the nodes' data.
2. Preorder (Root-Left-Right): Visit the current node first, then traverse its left and right subtrees recursively. This method is useful for constructing expressions from a tree, as it visits the operators before their operands.
3. Postorder (Left-Right-Root): Traverse the left and right subtrees recursively, and finally visit the current node. This method is used for tasks such as tree pruning or generating the reverse Polish notation of an expression.
4. Level Order: Traverse each level of the tree from left to right before moving to the next level. This method is useful for applications like breadth-first search (BFS) and printing the tree in a specific format.

Worked Example

Let's implement an AVL Tree using Python. We will focus on insertion, deletion, and rotation operations to maintain balance.

class Node:
def __init__(self, key):
self.key = key
self.height = 1
self.left = None
self.right = None

class AVLTree:
def __init__(self):
self.root = None

def get_height(self, node):
if not node:
return 0
return node.height

def get_balance_factor(self, node):
if not node or (not node.left and not node.right):
return 0
return self.get_height(node.left) - self.get_height(node.right)

def rotate_right(self, A, B):
C = B.left
B.left = C.right
C.right = B
B.parent = C
if C.right:
C.right.parent = B
self.update_height(B)
self.update_height(C)
return C

def rotate_left(self, A, B):
C = B.right
B.right = C.left
C.left = B
B.parent = C
if C.left:
C.left.parent = B
self.update_height(B)
self.update_height(C)
return C

def double_rotation(self, A, B):
if self.get_balance_factor(B) == -1 and self.get_balance_factor(B.left) == 1:
C = B.left.right
self.rotate_left(A, B.left)
B.left = C
self.rotate_right(A, B)
elif self.get_balance_factor(B) == -1 and self.get_balance_factor(B.left) == -1:
C = B.left.left
self.rotate_right(A, B.left.left)
B1 = B.left
self.rotate_left(A, B1)
B.left = C
self.rotate_right(A, B)
return A.root

def insert(self, root, key):
if not root:
return Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
root.left.parent = root
balance_factor = self.get_balance_factor(root)
if balance_factor > 1 and key < root.left.key:
return self.rotate_right(None, root)
elif balance_factor > 1 and key >= root.left.key:
root.left = self.rotate_left(None, root.left)
root = self.rotate_right(None, root)
else:
root.right = self.insert(root.right, key)
root.right.parent = root
balance_factor = self.get_balance_factor(root)
if balance_factor < -1 and key > root.right.key:
return self.rotate_left(None, root)
elif balance_factor < -1 and key <= root.right.key:
root.right = self.rotate_right(None, root.right)
root = self.rotate_left(None, root)
self.update_height(root)
return root

def update_height(self, node):
if not node:
return None
height_left = self.get_height(node.left)
height_right = self.get_height(node.right)
node.height = max(height_left, height_right) + 1

def delete(self, root, key):
if not root:
return root
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
balance_factor = self.get_balance_factor(root)
if balance_factor > 1 and self.get_balance_factor(root.left) >= 0:
root.left = self.rotate_left(None, root.left)
balance_factor = self.get_balance_factor(root)
if balance_factor > 1 and self.get_balance_factor(root.left) < 0:
root.left = self.rotate_right(None, root.left.left)
root = self.rotate_left(None, root)
else:
if not root.left:
temp = root.right
root = None
return temp
elif not root.right:
temp = root.left
root = None
return temp
temp = self.find_min(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
balance_factor = self.get_balance_factor(root)
if balance_factor < -1 and self.get_balance_factor(root.right) >= 0:
root.right = self.rotate_right(None, root.right)
balance_factor = self.get_balance_factor(root)
if balance_factor < -1 and self.get_balance_factor(root.right) > 0:
root.right = self.rotate_left(None, root.right.left)
root = self.rotate_right(None, root)
if root is not None:
self.update_height(root)
return root

def find_min(self, node):
current = node
while current.left is not None:
current = current.left
return current

Common Mistakes

1. Neglecting to update the height of a node after insertion or deletion. This can lead to incorrect balance factors and unbalanced trees.
2. Failing to properly handle the case where a node has no children during deletion, resulting in an unbalanced tree.
3. Not accounting for the possibility of double rotations when re-balancing the tree after insertion or deletion.
4. Incorrectly implementing the rotation functions (rotate_left, rotate_right) or forgetting to update parent pointers during rotations.
5. Misunderstanding the balance factor calculation and not adjusting it accordingly after insertion or deletion.

Practice Questions

1. Implement a preorder traversal function for AVL trees.
2. Write a function to check if a given binary tree is an AVL tree.
3. Implement the delete operation in a BST and convert it into an AVL tree by re-balancing as needed.
4. Given two sorted arrays, create a balanced binary search tree using their elements.
5. Implement the level order traversal for AVL trees.

FAQ

Q: Why are AVL trees more efficient than regular BSTs?

A: AVL trees maintain balance, which guarantees that the height of the tree is logarithmic in the number of nodes, making search, insertion, and deletion operations faster compared to regular BSTs.

Q: What are the time complexities for the main operations in an AVL tree?

A. Search: O(log n)

B. Insert: O(log n)

C. Delete: O(log n)

Q: Can I implement other types of self-balancing binary search trees (like Red-Black Trees or Splay Trees) using Python?

A: Yes, you can implement other self-balancing binary search trees in Python by following similar principles and adjusting the re-balancing rules as needed.