Tree algorithms are fundamental in computer science and have a variety of applications in areas such as data structures, networking, artificial intelligence, and more. Below are implementations of some essential tree algorithms in Python, including tree traversal, insertion, deletion, and searching. ## <br>1. Binary Search Tree (BST) ### Node Class ```py class Node: def __init__(self, key): self.left = None self.right = None self.val = key ``` ### Insertion in BST ```py def insert(root, key): if root is None: return Node(key) else: if root.val < key: root.right = insert(root.right, key) else: root.left = insert(root.left, key) return root ``` ### Deletion in BST ```py def minValueNode(node): current = node while current.left is not None: current = current.left return current def deleteNode(root, key): if root is None: return root if key < root.val: root.left = deleteNode(root.left, key) elif key > root.val: root.right = deleteNode(root.right, key) else: if root.left is None: return root.right elif root.right is None: return root.left temp = minValueNode(root.right) root.val = temp.val root.right = deleteNode(root.right, temp.val) return root ``` ### Search in BST ```py def search(root, key): if root is None or root.val == key: return root if root.val < key: return search(root.right, key) return search(root.left, key) ``` ### Tree Traversals ```py def inorder(root): if root: inorder(root.left) print(root.val, end=' ') inorder(root.right) def preorder(root): if root: print(root.val, end=' ') preorder(root.left) preorder(root.right) def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.val, end=' ') ``` ## 2. AVL Tree AVL Tree is a self-balancing binary search tree. Below is an implementation of the insertion algorithm which ensures the tree remains balanced. ### AVL Node Class ```py class AVLNode: def __init__(self, key): self.left = None self.right = None self.val = key self.height = 1 ``` ### AVL Tree Class ```py class AVLTree: def insert(self, root, key): if not root: return AVLNode(key) elif key < root.val: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) balance = self.getBalance(root) if balance > 1 and key < root.left.val: return self.rightRotate(root) if balance < -1 and key > root.right.val: return self.leftRotate(root) if balance > 1 and key > root.left.val: root.left = self.leftRotate(root.left) return self.rightRotate(root) if balance < -1 and key < root.right.val: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root def leftRotate(self, z): y = z.right T2 = y.left y.left = z z.right = T2 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y def rightRotate(self, z): y = z.left T3 = y.right y.right = z z.left = T3 z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y def getHeight(self, root): if not root: return 0 return root.height def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right) def preOrder(self, root): if not root: return print("{0} ".format(root.val), end="") self.preOrder(root.left) self.preOrder(root.right) ``` ### Example Usage ```py # BST Example root = Node(50) root = insert(root, 30) root = insert(root, 20) root = insert(root, 40) root = insert(root, 70) root = insert(root, 60) root = insert(root, 80) print("Inorder traversal of the BST:") inorder(root) print("\nDelete 20") root = deleteNode(root, 20) print("Inorder traversal after deleting 20:") inorder(root) print("\nSearch for 30:") result = search(root, 30) if result: print(f"Found: {result.val}") else: print("Not found") # AVL Tree Example avl_tree = AVLTree() root = None keys = [10, 20, 30, 40, 50, 25] for key in keys: root = avl_tree.insert(root, key) print("Preorder traversal of the AVL tree is:") avl_tree.preOrder(root) ``` These implementations cover basic operations for Binary Search Trees (BST) and AVL Trees, ensuring balanced tree structures and efficient data management.