jupyter/binary_tree.ipynb
{
"cells": [
{
"cell_type": "code",
"id": "initial_id",
"metadata": {
"collapsed": true,
"ExecuteTime": {
"end_time": "2024-10-30T05:06:20.776812Z",
"start_time": "2024-10-30T05:06:20.674515Z"
}
},
"source": [
"from typing import Optional, List\n",
"\n",
"\n",
"class BinaryTree:\n",
" class _Node:\n",
" \"\"\"\n",
" Represents a node in a binary tree.\n",
"\n",
" Attributes:\n",
" value (int): The value stored in the node.\n",
" left (Optional[BinaryTree._Node]): The left child of the node.\n",
" right (Optional[BinaryTree._Node]): The right child of the node.\n",
" key (int): The key of the node, same as value.\n",
" \"\"\"\n",
"\n",
" def __init__(self, value: int) -> None:\n",
" self.value: int = value\n",
" self.left: Optional[BinaryTree._Node] = None\n",
" self.right: Optional[BinaryTree._Node] = None\n",
" self.key: int = value\n",
"\n",
" class _AVLNode:\n",
" \"\"\"\n",
" Represents a node in an AVL tree.\n",
"\n",
" Attributes:\n",
" key (int): The key stored in the node.\n",
" left (Optional[BinaryTree._AVLNode]): The left child of the node.\n",
" right (Optional[BinaryTree._AVLNode]): The right child of the node.\n",
" height (int): The height of the node.\n",
" \"\"\"\n",
"\n",
" def __init__(self, key: int) -> None:\n",
" self.key: int = key\n",
" self.left: Optional[BinaryTree._AVLNode] = None\n",
" self.right: Optional[BinaryTree._AVLNode] = None\n",
" self.height: int = 1\n",
"\n",
" class _RBNode:\n",
" \"\"\"\n",
" Represents a node in a Red-Black tree.\n",
"\n",
" Attributes:\n",
" data (Optional[int]): The data stored in the node.\n",
" color (str): The color of the node, either \"red\" or \"black\".\n",
" left (Optional[BinaryTree._RBNode]): The left child of the node.\n",
" right (Optional[BinaryTree._RBNode]): The right child of the node.\n",
" parent (Optional[BinaryTree._RBNode]): The parent of the node.\n",
" \"\"\"\n",
"\n",
" def __init__(self, data: Optional[int], color: str = \"red\") -> None:\n",
" self.data: Optional[int] = data\n",
" self.color: str = color\n",
" self.left: Optional[BinaryTree._RBNode] = None\n",
" self.right: Optional[BinaryTree._RBNode] = None\n",
" self.parent: Optional[BinaryTree._RBNode] = None\n",
"\n",
" class _BPlusTreeNode:\n",
" \"\"\"\n",
" Represents a node in a B+ tree.\n",
"\n",
" Attributes:\n",
" is_leaf (bool): Indicates if the node is a leaf.\n",
" keys (List[int]): The keys stored in the node.\n",
" children (List[BinaryTree._BPlusTreeNode]): The children of the node.\n",
" \"\"\"\n",
"\n",
" def __init__(self, is_leaf: bool = False) -> None:\n",
" self.is_leaf: bool = is_leaf\n",
" self.keys: List[int] = []\n",
" self.children: List[BinaryTree._BPlusTreeNode] = []\n",
"\n",
" class AVL:\n",
" @classmethod\n",
" def insert(cls, root, key: int):\n",
" \"\"\"\n",
" Inserts a key into the AVL tree and balances the tree if necessary.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The root of the AVL tree.\n",
" key (int): The key to insert.\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The new root of the AVL tree.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode) and root is not None:\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" if not root:\n",
" return BinaryTree._AVLNode(key)\n",
" if key < root.key:\n",
" root.left = cls.insert(root.left, key)\n",
" else:\n",
" root.right = cls.insert(root.right, key)\n",
"\n",
" root.height = 1 + max(\n",
" cls._Get.height(root.left), cls._Get.height(root.right)\n",
" )\n",
" balance = cls._Get.balance(root)\n",
"\n",
" if balance > 1:\n",
" if key < root.left.key:\n",
" return cls.__right_rotate(root)\n",
" root.left = cls.__left_rotate(root.left)\n",
" return cls.__right_rotate(root)\n",
" if balance < -1:\n",
" if key > root.right.key:\n",
" return cls.__left_rotate(root)\n",
" root.right = cls.__right_rotate(root.right)\n",
" return cls.__left_rotate(root)\n",
"\n",
" return root\n",
"\n",
" @classmethod\n",
" def delete(cls, root, key: int):\n",
" \"\"\"\n",
" Deletes a key from the AVL tree and balances the tree if necessary.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The root of the AVL tree.\n",
" key (int): The key to delete.\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The new root of the AVL tree.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode):\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" if not root:\n",
" return root\n",
" if key < root.key:\n",
" root.left = cls.delete(root.left, key)\n",
" elif key > root.key:\n",
" root.right = cls.delete(root.right, key)\n",
" else:\n",
" if not root.left:\n",
" return root.right\n",
" if not root.right:\n",
" return root.left\n",
"\n",
" temp = cls.__min_value_node(root.right)\n",
" root.key = temp.key\n",
" root.right = cls.delete(root.right, temp.key)\n",
"\n",
" root.height = 1 + max(\n",
" cls._Get.height(root.left), cls._Get.height(root.right)\n",
" )\n",
" balance = cls._Get.balance(root)\n",
"\n",
" if balance > 1:\n",
" if cls._Get.balance(root.left) >= 0:\n",
" return cls.__right_rotate(root)\n",
" root.left = cls.__left_rotate(root.left)\n",
" return cls.__right_rotate(root)\n",
" if balance < -1:\n",
" if cls._Get.balance(root.right) <= 0:\n",
" return cls.__left_rotate(root)\n",
" root.right = cls.__right_rotate(root.right)\n",
" return cls.__left_rotate(root)\n",
"\n",
" return root\n",
"\n",
" @classmethod\n",
" def __rotate(cls, z, direction: str):\n",
" \"\"\"\n",
" Rotates the subtree rooted at z in the specified direction.\n",
"\n",
" Args:\n",
" z (BinaryTree._AVLNode): The root of the subtree to rotate.\n",
" direction (str): The direction to rotate ('left' or 'right').\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The new root of the rotated subtree.\n",
" \"\"\"\n",
" if not isinstance(z, BinaryTree._AVLNode):\n",
" raise TypeError(\"Z must be an instance of BinaryTree._AVLNode\")\n",
" y = getattr(z, direction)\n",
" setattr(\n",
" z,\n",
" direction,\n",
" getattr(y, \"left\" if direction == \"right\" else \"right\"),\n",
" )\n",
" setattr(y, \"left\" if direction == \"right\" else \"right\", z)\n",
" z.height = 1 + max(cls._Get.height(z.left), cls._Get.height(z.right))\n",
" y.height = 1 + max(cls._Get.height(y.left), cls._Get.height(y.right))\n",
" return y\n",
"\n",
" @classmethod\n",
" def __left_rotate(cls, z):\n",
" \"\"\"\n",
" Performs a left rotation on the subtree rooted at z.\n",
"\n",
" Args:\n",
" z (BinaryTree._AVLNode): The root of the subtree to rotate.\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The new root of the rotated subtree.\n",
" \"\"\"\n",
" if not isinstance(z, BinaryTree._AVLNode):\n",
" raise TypeError(\"Z must be an instance of BinaryTree._AVLNode\")\n",
" return cls.__rotate(z, \"right\")\n",
"\n",
" @classmethod\n",
" def __right_rotate(cls, z):\n",
" \"\"\"\n",
" Performs a right rotation on the subtree rooted at z.\n",
"\n",
" Args:\n",
" z (BinaryTree._AVLNode): The root of the subtree to rotate.\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The new root of the rotated subtree.\n",
" \"\"\"\n",
" if not isinstance(z, BinaryTree._AVLNode):\n",
" raise TypeError(\"Z must be an instance of BinaryTree._AVLNode\")\n",
" return cls.__rotate(z, \"left\")\n",
"\n",
" @classmethod\n",
" def pre_order(cls, root) -> str:\n",
" \"\"\"\n",
" Returns a string representation of the pre-order traversal of the AVL tree.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The root of the AVL tree.\n",
"\n",
" Returns:\n",
" str: The pre-order traversal of the AVL tree.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode):\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" result: List[str] = []\n",
" cls._pre_order_helper(root, result)\n",
" return \" \".join(result)\n",
"\n",
" @classmethod\n",
" def _pre_order_helper(cls, root, result: List[str]) -> None:\n",
" \"\"\"\n",
" Helper function for pre-order traversal.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The root of the AVL tree.\n",
" result (List[str]): The list to store the traversal result.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode) and root is not None:\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" if root:\n",
" result.append(str(root.key))\n",
" cls._pre_order_helper(root.left, result)\n",
" cls._pre_order_helper(root.right, result)\n",
"\n",
" @classmethod\n",
" def __min_value_node(cls, root):\n",
" \"\"\"\n",
" Finds the node with the minimum key in the subtree rooted at root.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The root of the subtree.\n",
"\n",
" Returns:\n",
" BinaryTree._AVLNode: The node with the minimum key.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode):\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" while root.left:\n",
" root = root.left\n",
" return root\n",
"\n",
" class _Get:\n",
" @staticmethod\n",
" def height(root) -> int:\n",
" \"\"\"\n",
" Returns the height of the node.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The node to get the height of.\n",
"\n",
" Returns:\n",
" int: The height of the node.\n",
" \"\"\"\n",
" if (\n",
" not isinstance(root, BinaryTree._AVLNode)\n",
" and root is not None\n",
" ):\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" return root.height if root else 0\n",
"\n",
" @classmethod\n",
" def balance(cls, root):\n",
" \"\"\"\n",
" Returns the balance factor of the node.\n",
"\n",
" Args:\n",
" root (BinaryTree._AVLNode): The node to get the balance factor of.\n",
"\n",
" Returns:\n",
" int: The balance factor of the node.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._AVLNode):\n",
" raise TypeError(\n",
" \"Root must be an instance of BinaryTree._AVLNode\"\n",
" )\n",
" return cls.height(root.left) - cls.height(root.right) if root else 0\n",
"\n",
" class Degenerate:\n",
" \"\"\"\n",
" Represents a degenerate (linked list-like) binary tree.\n",
" \"\"\"\n",
"\n",
" @classmethod\n",
" def __init__(cls) -> None:\n",
" \"\"\"\n",
" Initializes the Degenerate tree with an empty root.\n",
" \"\"\"\n",
" cls.root: Optional[BinaryTree._Node] = None\n",
"\n",
" @classmethod\n",
" def insert(cls, key: int) -> None:\n",
" \"\"\"\n",
" Inserts a key into the degenerate tree.\n",
"\n",
" Args:\n",
" key (int): The key to insert.\n",
" \"\"\"\n",
" if not cls.root:\n",
" cls.root = BinaryTree._Node(key)\n",
" else:\n",
" current = cls.root\n",
" while current.right:\n",
" current = current.right\n",
" current.right = BinaryTree._Node(key)\n",
"\n",
" @classmethod\n",
" def search(cls, key: int) -> bool:\n",
" \"\"\"\n",
" Searches for a key in the degenerate tree.\n",
"\n",
" Args:\n",
" key (int): The key to search for.\n",
"\n",
" Returns:\n",
" bool: True if the key is found, False otherwise.\n",
" \"\"\"\n",
" current = cls.root\n",
" while current:\n",
" if current.key == key:\n",
" return True\n",
" current = current.right\n",
" return False\n",
"\n",
" @classmethod\n",
" def delete(cls, key: int) -> None:\n",
" \"\"\"\n",
" Deletes a key from the degenerate tree.\n",
"\n",
" Args:\n",
" key (int): The key to delete.\n",
" \"\"\"\n",
" if not cls.root:\n",
" return\n",
" if cls.root.key == key:\n",
" cls.root = cls.root.right\n",
" return\n",
" current = cls.root\n",
" while current.right:\n",
" if current.right.key == key:\n",
" current.right = current.right.right\n",
" return\n",
" current = current.right\n",
"\n",
" @classmethod\n",
" def traverse(cls) -> str:\n",
" \"\"\"\n",
" Traverses the degenerate tree and returns a string representation.\n",
"\n",
" Returns:\n",
" str: A string representation of the tree.\n",
" \"\"\"\n",
" result: List[str] = []\n",
" current = cls.root\n",
" while current:\n",
" result.append(str(current.key))\n",
" current = current.right\n",
" result.append(\"None\")\n",
" return \" -> \".join(result)\n",
"\n",
" class Perfect:\n",
" \"\"\"\n",
" Represents a perfect binary tree.\n",
" \"\"\"\n",
"\n",
" @classmethod\n",
" def __init__(cls, height: int) -> None:\n",
" \"\"\"\n",
" Initializes the Perfect binary tree with a given height.\n",
"\n",
" Args:\n",
" height (int): The height of the perfect binary tree.\n",
" \"\"\"\n",
" cls.height: int = height\n",
" cls.nodes: List[Optional[BinaryTree._Node]] = [None] * (\n",
" 2 ** height - 1\n",
" )\n",
"\n",
" @classmethod\n",
" def create(cls) -> None:\n",
" \"\"\"\n",
" Creates the perfect binary tree.\n",
" \"\"\"\n",
" cls.__create(0)\n",
"\n",
" @classmethod\n",
" def __create(cls, index: int) -> None:\n",
" \"\"\"\n",
" Recursively creates nodes for the perfect binary tree.\n",
"\n",
" Args:\n",
" index (int): The current index in the nodes list.\n",
" \"\"\"\n",
" if index < len(cls.nodes):\n",
" cls.__create(2 * index + 1)\n",
" cls.nodes[index] = BinaryTree._Node(index)\n",
" cls.__create(2 * index + 2)\n",
"\n",
" @classmethod\n",
" def return_tree(cls) -> str:\n",
" \"\"\"\n",
" Returns a string representation of the perfect binary tree.\n",
"\n",
" Returns:\n",
" str: The string representation of the tree.\n",
" \"\"\"\n",
" levels: List[List[Optional[BinaryTree._Node]]] = []\n",
" cls.__print_tree(0, 0, levels)\n",
" return cls.__format_tree(levels)\n",
"\n",
" @staticmethod\n",
" def __format_tree(levels) -> str:\n",
" \"\"\"\n",
" Formats the levels of the tree into a string.\n",
"\n",
" Args:\n",
" levels (list): The levels of the tree.\n",
"\n",
" Returns:\n",
" str: The formatted string representation of the tree.\n",
" \"\"\"\n",
" if not isinstance(levels, list) or not all(\n",
" isinstance(level, list) for level in levels\n",
" ):\n",
" raise TypeError(\n",
" \"levels must be an instance of BinaryTree._Node\"\n",
" )\n",
" if not levels:\n",
" return \"\"\n",
" tree_str = \"\"\n",
" max_width = len(\n",
" \" \".join(str(node.value) if node else \"None\" for node in levels[-1])\n",
" )\n",
" for level in levels:\n",
" level_str = \" \".join(\n",
" str(node.value) if node else \"None\" for node in level\n",
" )\n",
" tree_str += level_str.center(max_width) + \"\\n\"\n",
" return tree_str.replace(\"None\", \" \")\n",
"\n",
" @classmethod\n",
" def return_list(cls) -> List[Optional[int]]:\n",
" \"\"\"\n",
" Returns a list of node values in the perfect binary tree.\n",
"\n",
" Returns:\n",
" list[Optional[int]]: The list of node values.\n",
" \"\"\"\n",
" return [node.value if node else None for node in cls.nodes]\n",
"\n",
" @classmethod\n",
" def __print_tree(cls, index: int, level: int, levels) -> None:\n",
" \"\"\"\n",
" Recursively prints the tree levels.\n",
"\n",
" Args:\n",
" index (int): The current index in the nodes list.\n",
" level (int): The current level in the tree.\n",
" levels (list): The list to store the levels of the tree.\n",
" \"\"\"\n",
" if index < len(cls.nodes):\n",
" if len(levels) == level:\n",
" levels.append([])\n",
" levels[level].append(cls.nodes[index])\n",
" cls.__print_tree(2 * index + 1, level + 1, levels)\n",
" cls.__print_tree(2 * index + 2, level + 1, levels)\n",
"\n",
" class RedBlackTree:\n",
" \"\"\"\n",
" Represents a Red-Black Tree.\n",
" \"\"\"\n",
"\n",
" @classmethod\n",
" def __init__(cls) -> None:\n",
" \"\"\"\n",
" Initializes the Red-Black Tree with a NIL node.\n",
" \"\"\"\n",
" cls.NIL: BinaryTree._RBNode = BinaryTree._RBNode(\n",
" data=None, color=\"black\"\n",
" )\n",
" cls.root: BinaryTree._RBNode = cls.NIL\n",
"\n",
" @classmethod\n",
" def insert(cls, key: int) -> None:\n",
" \"\"\"\n",
" Inserts a new node with the given key into the Red-Black Tree.\n",
"\n",
" Args:\n",
" key (int): The key to insert.\n",
" \"\"\"\n",
" new_node = BinaryTree._RBNode(key)\n",
" new_node.left = cls.NIL\n",
" new_node.right = cls.NIL\n",
" parent: Optional[BinaryTree._RBNode] = None\n",
" current: BinaryTree._RBNode = cls.root\n",
"\n",
" while current != cls.NIL:\n",
" parent = current\n",
" if new_node.data < current.data:\n",
" current = current.left\n",
" else:\n",
" current = current.right\n",
"\n",
" new_node.parent = parent\n",
" if not parent:\n",
" cls.root = new_node\n",
" elif new_node.data < parent.data:\n",
" parent.left = new_node\n",
" else:\n",
" parent.right = new_node\n",
"\n",
" new_node.color = \"red\"\n",
" cls.insert_fixup(new_node)\n",
"\n",
" @classmethod\n",
" def insert_fixup(cls, node) -> None:\n",
" \"\"\"\n",
" Fixes the Red-Black Tree after insertion to maintain its properties.\n",
"\n",
" Args:\n",
" node (BinaryTree._RBNode): The node to fix up.\n",
" \"\"\"\n",
" if not isinstance(node, BinaryTree._RBNode):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._RBNode\"\n",
" )\n",
" while node != cls.root and node.parent.color == \"red\":\n",
" if node.parent == node.parent.parent.left:\n",
" uncle = node.parent.parent.right\n",
" if uncle.color == \"red\":\n",
" node.parent.color = \"black\"\n",
" uncle.color = \"black\"\n",
" node.parent.parent.color = \"red\"\n",
" node = node.parent.parent\n",
" else:\n",
" if node == node.parent.right:\n",
" node = node.parent\n",
" cls.left_rotate(node)\n",
" node.parent.color = \"black\"\n",
" node.parent.parent.color = \"red\"\n",
" cls.right_rotate(node.parent.parent)\n",
" else:\n",
" uncle = node.parent.parent.left\n",
" if uncle.color == \"red\":\n",
" node.parent.color = \"black\"\n",
" uncle.color = \"black\"\n",
" node.parent.parent.color = \"red\"\n",
" node = node.parent.parent\n",
" else:\n",
" if node == node.parent.left:\n",
" node = node.parent\n",
" cls.right_rotate(node)\n",
" node.parent.color = \"black\"\n",
" node.parent.parent.color = \"red\"\n",
" cls.left_rotate(node.parent.parent)\n",
" cls.root.color = \"black\"\n",
"\n",
" @classmethod\n",
" def rotate(cls, node, direction: str) -> None:\n",
" \"\"\"\n",
" Rotates the subtree rooted at the given node in the specified direction.\n",
"\n",
" Args:\n",
" node (BinaryTree._RBNode): The root of the subtree to rotate.\n",
" direction (str): The direction to rotate ('left' or 'right').\n",
" \"\"\"\n",
" if not isinstance(node, BinaryTree._RBNode):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._RBNode\"\n",
" )\n",
" opposite = \"left\" if direction == \"right\" else \"right\"\n",
" child = getattr(node, direction)\n",
" setattr(node, direction, getattr(child, opposite))\n",
" if getattr(child, opposite) != cls.NIL:\n",
" getattr(child, opposite).parent = node\n",
" child.parent = node.parent\n",
" if not node.parent:\n",
" cls.root = child\n",
" elif node == getattr(node.parent, opposite):\n",
" setattr(node.parent, opposite, child)\n",
" else:\n",
" setattr(node.parent, direction, child)\n",
" setattr(child, opposite, node)\n",
" node.parent = child\n",
"\n",
" @classmethod\n",
" def left_rotate(cls, x) -> None:\n",
" \"\"\"\n",
" Performs a left rotation on the subtree rooted at the given node.\n",
"\n",
" Args:\n",
" x (BinaryTree._RBNode): The root of the subtree to rotate.\n",
" \"\"\"\n",
" if not isinstance(x, BinaryTree._RBNode):\n",
" raise TypeError(\"x must be an instance of BinaryTree._RBNode\")\n",
" cls.rotate(x, \"right\")\n",
"\n",
" @classmethod\n",
" def right_rotate(cls, y) -> None:\n",
" \"\"\"\n",
" Performs a right rotation on the subtree rooted at the given node.\n",
"\n",
" Args:\n",
" y (BinaryTree._RBNode): The root of the subtree to rotate.\n",
" \"\"\"\n",
" if not isinstance(y, BinaryTree._RBNode):\n",
" raise TypeError(\"y must be an instance of BinaryTree._RBNode\")\n",
" cls.rotate(y, \"left\")\n",
"\n",
" @classmethod\n",
" def __repr__(cls) -> str:\n",
" \"\"\"\n",
" Returns a string representation of the Red-Black Tree.\n",
"\n",
" Returns:\n",
" str: A string representation of the tree.\n",
" \"\"\"\n",
"\n",
" def recurse(node: BinaryTree._RBNode) -> List[Optional[int]]:\n",
" if node == cls.NIL:\n",
" return []\n",
" return recurse(node.left) + [node.data] + recurse(node.right)\n",
"\n",
" return str(recurse(cls.root))\n",
"\n",
" class BPlusTree:\n",
" \"\"\"\n",
" Represents a B+ Tree.\n",
"\n",
" Attributes:\n",
" root (BinaryTree._BPlusTreeNode): The root node of the B+ tree.\n",
" t (int): The minimum degree of the B+ tree.\n",
" \"\"\"\n",
"\n",
" @classmethod\n",
" def __init__(cls, t: int = 3) -> None:\n",
" \"\"\"\n",
" Initializes the B+ tree with a given minimum degree.\n",
"\n",
" Args:\n",
" t (int): The minimum degree of the B+ tree. Default is 3.\n",
" \"\"\"\n",
" cls.root: BinaryTree._BPlusTreeNode = (\n",
" BinaryTree._BPlusTreeNode(is_leaf=True)\n",
" )\n",
" cls.t: int = t\n",
"\n",
" @classmethod\n",
" def insert(cls, key: int) -> None:\n",
" \"\"\"\n",
" Inserts a key into the B+ tree.\n",
"\n",
" Args:\n",
" key (int): The key to insert.\n",
" \"\"\"\n",
" root = cls.root\n",
" if len(root.keys) == (2 * cls.t) - 1:\n",
" temp = BinaryTree._BPlusTreeNode()\n",
" cls.root = temp\n",
" temp.children.append(root)\n",
" cls.split_child(temp, 0)\n",
" cls.insert_non_full(temp, key)\n",
" else:\n",
" cls.insert_non_full(root, key)\n",
"\n",
" @classmethod\n",
" def insert_non_full(cls, node, key: int) -> None:\n",
" \"\"\"\n",
" Inserts a key into a non-full node of the B+ tree.\n",
"\n",
" Args:\n",
" node (BinaryTree._BPlusTreeNode): The node to insert the key into.\n",
" key (int): The key to insert.\n",
" \"\"\"\n",
" if not isinstance(node, BinaryTree._BPlusTreeNode):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._BPlusTreeNode\"\n",
" )\n",
" if node.is_leaf:\n",
" node.keys.append(key)\n",
" node.keys.sort()\n",
" else:\n",
" i = len(node.keys) - 1\n",
" while i >= 0 and key < node.keys[i]:\n",
" i -= 1\n",
" i += 1\n",
" if len(node.children[i].keys) == (2 * cls.t) - 1:\n",
" cls.split_child(node, i)\n",
" if key > node.keys[i]:\n",
" i += 1\n",
" cls.insert_non_full(node.children[i], key)\n",
"\n",
" @classmethod\n",
" def split_child(cls, node, i: int) -> None:\n",
" \"\"\"\n",
" Splits a child node of the B+ tree.\n",
"\n",
" Args:\n",
" node (BinaryTree._BPlusTreeNode): The node whose child is to be split.\n",
" i (int): The index of the child to split.\n",
" \"\"\"\n",
" if not isinstance(node, BinaryTree._BPlusTreeNode):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._BPlusTreeNode\"\n",
" )\n",
" t = cls.t\n",
" y = node.children[i]\n",
" z = BinaryTree._BPlusTreeNode(is_leaf=y.is_leaf)\n",
" node.children.insert(i + 1, z)\n",
" node.keys.insert(i, y.keys[t - 1])\n",
" z.keys = y.keys[t: (2 * t) - 1]\n",
" y.keys = y.keys[0: t - 1]\n",
" if not y.is_leaf:\n",
" z.children = y.children[t: (2 * t)]\n",
" y.children = y.children[0:t]\n",
"\n",
" @classmethod\n",
" def search(cls, key: int, node=None) -> bool:\n",
" \"\"\"\n",
" Searches for a key in the B+ tree.\n",
"\n",
" Args:\n",
" key (int): The key to search for.\n",
" node (BinaryTree._BPlusTreeNode, optional): The node to start the search from. Defaults to None.\n",
"\n",
" Returns:\n",
" bool: True if the key is found, False otherwise.\n",
" \"\"\"\n",
" if (\n",
" not isinstance(node, BinaryTree._BPlusTreeNode)\n",
" and node is not None\n",
" ):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._BPlusTreeNode\"\n",
" )\n",
" if not node:\n",
" node = cls.root\n",
" i = 0\n",
" while i < len(node.keys) and key > node.keys[i]:\n",
" i += 1\n",
" if i < len(node.keys) and key == node.keys[i]:\n",
" return True\n",
" if node.is_leaf:\n",
" return False\n",
" return cls.search(key, node.children[i])\n",
"\n",
" @classmethod\n",
" def traverse(cls, node=None, level: int = 0) -> List[str]:\n",
" \"\"\"\n",
" Traverses the B+ tree and returns a list of strings representing the keys at each level.\n",
"\n",
" Args:\n",
" node (BinaryTree._BPlusTreeNode, optional): The node to start the traversal from. Defaults to None.\n",
" level (int): The current level in the tree. Defaults to 0.\n",
"\n",
" Returns:\n",
" List[str]: A list of strings representing the keys at each level.\n",
" \"\"\"\n",
" if (\n",
" not isinstance(node, BinaryTree._BPlusTreeNode)\n",
" and node is not None\n",
" ):\n",
" raise TypeError(\n",
" \"node must be an instance of BinaryTree._BPlusTreeNode\"\n",
" )\n",
" if not node:\n",
" node = cls.root\n",
" result = [f\"Level {level}: \" + \" \".join(str(key) for key in node.keys)]\n",
" if not node.is_leaf:\n",
" for child in node.children:\n",
" result.extend(cls.traverse(child, level + 1))\n",
" return result\n",
"\n",
" class SegmentTree:\n",
" \"\"\"\n",
" Represents a Segment Tree.\n",
"\n",
" Attributes:\n",
" n (int): The size of the input data.\n",
" tree (List[int]): The segment tree represented as a list.\n",
" \"\"\"\n",
"\n",
" @classmethod\n",
" def __init__(cls, data: List[int]) -> None:\n",
" \"\"\"\n",
" Initializes the Segment Tree with the given data.\n",
"\n",
" Args:\n",
" data (List[int]): The input data to build the segment tree from.\n",
" \"\"\"\n",
" cls.n: int = len(data)\n",
" cls.tree: List[int] = [0] * (2 * cls.n)\n",
" cls.__build(data)\n",
"\n",
" @classmethod\n",
" def __build(cls, data: List[int]) -> None:\n",
" \"\"\"\n",
" Builds the segment tree from the given data.\n",
"\n",
" Args:\n",
" data (List[int]): The input data to build the segment tree from.\n",
" \"\"\"\n",
" for i in range(cls.n):\n",
" cls.tree[cls.n + i] = data[i]\n",
" for i in range(cls.n - 1, 0, -1):\n",
" cls.tree[i] = cls.tree[i * 2] + cls.tree[i * 2 + 1]\n",
"\n",
" @classmethod\n",
" def update(cls, pos: int, value: int) -> None:\n",
" \"\"\"\n",
" Updates the value at the given position in the segment tree.\n",
"\n",
" Args:\n",
" pos (int): The position to update.\n",
" value (int): The new value to set.\n",
" \"\"\"\n",
" pos += cls.n\n",
" cls.tree[pos] = value\n",
" while pos > 1:\n",
" pos //= 2\n",
" cls.tree[pos] = cls.tree[2 * pos] + cls.tree[2 * pos + 1]\n",
"\n",
" @classmethod\n",
" def query(cls, left: int, right: int) -> int:\n",
" \"\"\"\n",
" Queries the sum of the values in the given range [left, right] in the segment tree.\n",
"\n",
" Args:\n",
" left (int): The left index of the range.\n",
" right (int): The right index of the range.\n",
"\n",
" Returns:\n",
" int: The sum of the values in the given range.\n",
" \"\"\"\n",
" left += cls.n\n",
" right += cls.n\n",
" sum_query = 0\n",
" while left <= right:\n",
" if left % 2 == 1:\n",
" sum_query += cls.tree[left]\n",
" left += 1\n",
" if right % 2 == 0:\n",
" sum_query += cls.tree[right]\n",
" right -= 1\n",
" left //= 2\n",
" right //= 2\n",
" return sum_query\n",
"\n",
" class Default:\n",
" def insert(self, root, key: int):\n",
" \"\"\"\n",
" Inserts a key into the binary tree.\n",
"\n",
" Args:\n",
" root (BinaryTree._Node): The root node of the binary tree.\n",
" key (int): The key to insert.\n",
"\n",
" Returns:\n",
" BinaryTree._Node: The new root of the binary tree.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._Node) and root is not None:\n",
" raise TypeError(\"root must be an instance of BinaryTree._Node\")\n",
" if root is None:\n",
" return BinaryTree._Node(key)\n",
" if key < root.value:\n",
" root.left = self.insert(root.left, key)\n",
" else:\n",
" root.right = self.insert(root.right, key)\n",
" return root\n",
"\n",
" def inorder_traversal(self, root, sorted_list: List[int]) -> None:\n",
" \"\"\"\n",
" Performs an inorder traversal of the binary tree and appends the values to the sorted list.\n",
"\n",
" Args:\n",
" root (BinaryTree._Node): The root node of the binary tree.\n",
" sorted_list (List[int]): The list to append the values to.\n",
" \"\"\"\n",
" if not isinstance(root, BinaryTree._Node) and root is not None:\n",
" raise TypeError(\"root must be an instance of BinaryTree._Node\")\n",
" if root:\n",
" self.inorder_traversal(root.left, sorted_list)\n",
" sorted_list.append(root.value)\n",
" self.inorder_traversal(root.right, sorted_list)\n",
"\n",
" def tree_sort(self, arr: List[int]) -> List[int]:\n",
" \"\"\"\n",
" Sorts a list of integers using the tree sort algorithm.\n",
"\n",
" Args:\n",
" arr (List[int]): The list of integers to sort.\n",
"\n",
" Returns:\n",
" List[int]: The sorted list of integers.\n",
" \"\"\"\n",
" if not arr:\n",
" return arr\n",
" root = BinaryTree._Node(arr[0])\n",
" for value in arr[1:]:\n",
" self.insert(root, value)\n",
" sorted_list: List[int] = []\n",
" self.inorder_traversal(root, sorted_list)\n",
" return sorted_list\n"
],
"outputs": [],
"execution_count": 1
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 5
}