Atree data structure is a hierarchical collection of nodes, typically visualized with a root at the top. Trees are typically used for representing relationships, hierarchies, and facilitating efficient data operations.

• Node: The basic unit of a tree that contains data and may link to child nodes.
• Root: The tree's topmost node; no nodes point to the root.
• Parent / Child: Nodes with a direct connection; a parent points to its children.
• Leaf: A node that has no children.
• Edge: A link or reference from one node to another.
• Depth: The level of a node, or its distance from the root.
• Height: Maximum depth of any node in the tree.

1. Hierarchical: Organized in parent-child relationships.
2. Non-Sequential: Non-linear data storage ensures flexible and efficient access patterns.
3. Directed: Nodes are connected unidirectionally.
4. Acyclic: Trees do not have loops or cycles.
5. Diverse Node Roles: Such as root and leaf.

• Binary Tree: Each node has a maximum of two children.
• Binary Search Tree (BST): A binary tree where each node's left subtree has values less than the node and the right subtree has values greater.
• AVL Tree: A BST that self-balances to optimize searches.
• B-Tree: Commonly used in databases to enable efficient access.
• Red-Black Tree: A BST that maintains balance using node coloring.
• Trie: Specifically designed for efficient string operations.

• File Systems: Model directories and files.
• AI and Decision Making: Decision trees help in evaluating possible actions.
• Database Systems: Many databases use trees to index data efficiently.

• Preorder: Root, Left, Right.
• Inorder: Left, Root, Right (specific to binary trees).
• Postorder: Left, Right, Root.

• Level Order: Traverse nodes by depth, moving from left to right.

Here is the Python code:

classNode:def__init__(self,data):self.left=Noneself.right=Noneself.data=data# Create a tree structureroot=Node(1)root.left,root.right=Node(2),Node(3)root.left.left,root.right.right=Node(4),Node(5)# Inorder traversaldefinorder_traversal(node):ifnode:inorder_traversal(node.left)print(node.data,end=' ')inorder_traversal(node.right)# Expected Output: 4 2 1 3 5print("Inorder Traversal: ")inorder_traversal(root)

ABinary Tree is a hierarchical structure where each node has up to two children, termed asleft child andright child. Each node holds a data element and pointers to its left and right children.

• Full Binary Tree: Nodes either have two children or none.
• Complete Binary Tree: Every level, except possibly the last, is completely filled, with nodes skewed to the left.
• Perfect Binary Tree: All internal nodes have two children, and leaves exist on the same level.

• Binary Search Trees: Efficient in lookup, addition, and removal operations.
• Expression Trees: Evaluate mathematical expressions.
• Heap: Backbone of priority queues.
• Trie: Optimized for string searches.

Here is the Python code:

classNode:"""Binary tree node with left and right child."""def__init__(self,data):self.left=Noneself.right=Noneself.data=datadefinsert(self,data):"""Inserts a node into the tree."""ifdata<self.data:ifself.leftisNone:self.left=Node(data)else:self.left.insert(data)elifdata>self.data:ifself.rightisNone:self.right=Node(data)else:self.right.insert(data)defin_order_traversal(self):"""Performs in-order traversal and returns a list of nodes."""nodes= []ifself.left:nodes+=self.left.in_order_traversal()nodes.append(self.data)ifself.right:nodes+=self.right.in_order_traversal()returnnodes# Example usage:# 1. Instantiate the root of the treeroot=Node(50)# 2. Insert nodes (This will implicitly form a Binary Search Tree for simplicity)values_to_insert= [30,70,20,40,60,80]forvalinvalues_to_insert:root.insert(val)# 3. Perform in-order traversalprint(root.in_order_traversal())# Expected Output: [20, 30, 40, 50, 60, 70, 80]

ABinary Heap is a special binary tree that satisfies theHeap Property: parent nodes are ordered relative to their children.

There are two types of binary heaps:

• Min Heap: Parent nodes are less than or equal to their children.
• Max Heap: Parent nodes are greater than or equal to their children.

1. Shape Property: A binary heap is a complete binary tree, which means all its levels are filled except the last one, which is filled from the left.
2. Heap Property: Nodes follow a specific order—either min heap or max heap—relative to their children.

Due to thecomplete binary tree structure, binary heaps are often implemented asarrays, offering both spatial efficiency and cache-friendly access patterns.

• Root Element: Stored at index 0.
• Child-Parent Mapping:
  • Left child:(2*i) + 1
  • Right child:(2*i) + 2
  • Parent:(i-1) / 2

Index:     0 1 2 3 4 5 6 7 8 9 10Elements: 1 3 2 6 5 7 8 9 10 0 4

• Memory Efficiency: No extra pointers needed.
• Cache Locality: Adjacent elements are stored closely, aiding cache efficiency.

• Array Sizing: The array size must be predefined.
• Percolation: Insertions and deletions may require element swapping, adding computational overhead.

Here is the Python code:

classBinaryHeap:def__init__(self,array):self.heap=arraydefget_parent_index(self,index):return (index-1)//2defget_left_child_index(self,index):return (2*index)+1defget_right_child_index(self,index):return (2*index)+2# Example usageheap=BinaryHeap([1,3,2,6,5,7,8,9,10,0,4])parent_index=heap.get_parent_index(4)left_child_index=heap.get_left_child_index(1)print(f"Parent index of node at index 4:{parent_index}")print(f"Left child index of node at index 1:{left_child_index}")

ABinary Search Tree (BST) is a binary tree optimized for quick lookup, insertion, and deletion operations. A BST has the distinct property that each node's left subtree contains values smaller than the node, and its right subtree contains values larger.

• Sorted Elements: Enables efficient searching and range queries.
• Recursive Definition: Each node and its subtrees also form a BST.
• Unique Elements: Generally, BSTs do not allow duplicates, although variations exist.

For any node$N$ in the BST:

$$$$\forall L \in \text{Left-Subtree}(N) & : \text{Value}(L) < \text{Value}(N) \\forall R \in \text{Right-Subtree}(N) & : \text{Value}(R) > \text{Value}(N)$$$$

• Databases: Used for efficient indexing.
• File Systems: Employed in OS for file indexing.
• Text Editors: Powers auto-completion and suggestions.

• Search:$O(\log n)$ in balanced trees;$O(n)$ in skewed trees.
• Insertion: Averages$O(\log n)$; worst case is$O(n)$.
• Deletion: Averages$O(\log n)$; worst case is$O(n)$.

Here is the Python code:

defis_bst(node,min=float('-inf'),max=float('inf')):ifnodeisNone:returnTrueifnotmin<node.value<max:returnFalsereturn (is_bst(node.left,min,node.value)andis_bst(node.right,node.value,max))

AVL Trees, named after their inventors Adelson-Velsky and Landis, are a special type of binary search tree (BST) thatself-balance. This balancing optimizes time complexity for operations like search, insert, and delete to$O(\log n)$.

Each node in an AVL Tree must satisfy the following balance criterion to maintain self-balancing:

$$\text{BalanceFactor}(N) = \text{height}(L) - \text{height}(R) \in {-1, 0, 1}$$

If a node'sBalance Factor deviates from this range, the tree needs rebalancing.

This involves three steps:

1. Evaluate each node's balance factor.
2. Identify the type of imbalance: left-heavy, right-heavy, or requiring double rotation.
3. Perform the necessary rotations to restore balance.

• Left Rotation (LL): Useful when the right subtree is taller.

• Right Rotation (RR): Used for a taller left subtree.

• Left-Right (LR) Rotation: Involves an initially taller left subtree.

• Right-Left (RL) Rotation: Similar to LR but starts with a taller right subtree.

Here is the Python code:

classNode:def__init__(self,key):self.left=Noneself.right=Noneself.key=keyself.height=1defleft_rotate(z):y=z.rightT2=y.lefty.left=zz.right=T2z.height=1+max(get_height(z.left),get_height(z.right))y.height=1+max(get_height(y.left),get_height(y.right))returny

ARed-Black Tree is a self-balancing binary search tree that optimizes both search and insertion/deletion operations. It accomplishes this via a set of rules known asred-black balance, making it well-suited for practical applications.

• Root: Always black.
• Red Nodes: Can only have black children.
• Black Depth: Every path from a node to its descendant leaves contains the same count of black nodes.

These rules ensure abalanced tree, where thelongest path is no more than twice the length of theshortest one.

• Efficiency: Maintains$O(\log n)$ operations even during insertions/deletions.
• Simplicity: Easier to implement than some other self-balancing trees like AVL trees.

Nodes in aRed-Black Tree are visually differentiated by color. Memory-efficient implementations often use a single bit for color, with '1' for red and '0' for black.

• Time Complexity:
  • Search:$O(\log n)$
  • Insert/Delete:$O(\log n)$
• Space Complexity:$O(n)$

Here is the Python code:

classNode:def__init__(self,val,color):self.left=Noneself.right=Noneself.val=valself.color=color# 'R' for red, 'B' for blackclassRedBlackTree:def__init__(self):self.root=Nonedefinsert(self,val):new_node=Node(val,'R')ifnotself.root:self.root=new_nodeself.root.color='B'# Root is always blackelse:self._insert_recursive(self.root,new_node)def_insert_recursive(self,root,node):ifroot.val<node.val:ifnotroot.right:root.right=nodeelse:self._insert_recursive(root.right,node)else:ifnotroot.left:root.left=nodeelse:self._insert_recursive(root.left,node)self._balance(node)def_balance(self,node):# Red-black balancing logic herepass

Balanced search trees, such asAVL Trees andB-Trees - are designed primarily for optimized andfast search operations. However, each tree has distinct core properties and specific applications.

• AVL Trees: These are self-adjusting Binary Search Trees with nodes that can have up to two children. Balancing is achieved through rotations.

• B-Trees: Multi-way trees where nodes can house multiple children, balancing is maintained via key redistribution.

• AVL Trees: Best suited for in-memory operations, optimizing searches in RAM. Their efficiency dwindles in disk storage due to pointer overhead.

• B-Trees: Engineered for disk-based storage, minimizing I/O operations, making them ideal for databases and extensive file systems.

• AVL Trees: Utilize dynamic memory linked via pointers, which can be more memory-intensive.

• B-Trees: Data is stored in disk blocks, optimizing access by reducing disk I/O.

• Both types ensure$O(\log n)$ search time. However, B-Trees often outpace AVL Trees in large datasets due to their multi-way branching.

Here is the Python code:

classNode:def__init__(self,value):self.value=valueself.left=Noneself.right=Noneself.height=1classAVLTree:def__init__(self):self.root=None# Additional methods for insertion, deletion, and balancing.

Here is the Python code:

classBTreeNode:def__init__(self,leaf=False):self.leaf=leafself.keys= []self.child= []# Additional methods for operations.classBTree:def__init__(self,t):self.root=BTreeNode(True)self.t=t# Methods for traversal, search, etc.

TheFenwick Tree, or Binary Indexed Tree$(BIT)$, is an extremely efficient data structure particularly suited forrange queries and point updates in large sequential datasets, like arrays. Its primary strength lies in itsfast update and query operations, presenting unique advantages in specific algorithmic scenarios.

• Sum Query Efficiency: In an array, obtaining the sum of its elements up to index$i$ requires$O(n)$ time. With a BIT, this task is optimized to$O(\log n)$.

• Update Efficiency: While updating an array's element at index$i$ takes$O(1)$, updating the prefix sum data to reflect this change typically needs$O(n)$ time. A BIT aids in achieving a$O(\log n)$ time update for both.

• Range Queries Optimization: A BIT is helpful in scenarios where you need to frequently calculate ranges like$[l, r]$ in sequences that don't change size.

Here is the Python code:

defupdate(bit,idx,val):whileidx<len(bit):bit[idx]+=validx+= (idx&-idx)defget_sum(bit,idx):total=0whileidx>0:total+=bit[idx]idx-= (idx&-idx)returntotaldefconstruct_bit(arr):bit= [0]* (len(arr)+1)fori,valinenumerate(arr):update(bit,i+1,val)returnbit

To calculate the sum from index$1$ to$7$, the call is:get_sum(bit, 7) - get_sum(bit, 0). This subtractions helps in avoiding the extra point.

Segment Trees are variant binary search trees optimized for fastrange queries on an interval of a known array.

• Root Node: Covers the entire array or range.
• Functionality: Can efficiently handle range operations like find-sum, find-max, and find-min.
• Internal Nodes: Divide the array into two equal segments.
• Leaves: Represent individual array elements.
• Building the Tree: Done in top-down manner.
• Complexity: Suitable for queries with$O(\log n)$ complexity over large inputs.
• Operations: Can perform range updates in$O(\log n)$ time.

Here is the Python code:

classSegmentTree:def__init__(self,arr):self.tree= [None]* (4*len(arr))self.build_tree(arr,0,len(arr)-1,0)defbuild_tree(self,arr,start,end,pos):ifstart==end:self.tree[pos]=arr[start]returnmid= (start+end)//2self.build_tree(arr,start,mid,2*pos+1)self.build_tree(arr,mid+1,end,2*pos+2)self.tree[pos]=self.tree[2*pos+1]+self.tree[2*pos+2]defrange_sum(self,q_start,q_end,start=0,end=None,pos=0):ifendisNone:end=len(self.tree)//4-1ifq_end<startorq_start>end:return0ifq_start<=startandq_end>=end:returnself.tree[pos]mid= (start+end)//2returnself.range_sum(q_start,q_end,start,mid,2*pos+1)+self.range_sum(q_start,q_end,mid+1,end,2*pos+2)# Example usagearr= [1,3,5,7,9,11]st=SegmentTree(arr)print(st.range_sum(1,3))# Output: 15 (5 + 7 + 3)

TheSplay Tree, a form of self-adjusting binary search tree, reshapes itself to optimize performance based on recent data access patterns. It achieves this through "splaying" operations.

Thesplay operation aims to move a target node$x$ to the root position via a sequence of tree and node manipulations to increase efficiency.

The process generally involves:

• Zig Step: If the node is a direct child of the root, it's rotated up.

• Zig-Zig Step: If both the node and its parent are left or right children, they're both moved up.

• Zig-Zag Step: If one is a left child, and the other a right child, a double rotation brings both up.

The splay sequence also ensures that descendants of$x$ remain children of$x$ after the splay operation.

• Pros:

  • Trees can adapt to access patterns, making it an ideal data structure for both search and insert operations in practice.
  • It can outperform other tree structures in some cases due to its adaptive nature.

• Cons:

  • The splay operation is complex and can be time-consuming.
  • Splay trees do not guarantee the best time complexity for search operations, which can be an issue in performance-critical applications where a consistent time is required.

• Average Time Complexity:

  • Search:$O(\log{n})$ on average.
  • Insertion andDeletion:$O(\log{n})$ on average.

Here is the Python code:

classNode:def__init__(self,key):self.left=self.right=Noneself.key=keyclassSplayTree:def__init__(self):self.root=Nonedefsplay(self,key):ifself.rootisNoneorkey==self.root.key:return# No need to splaydummy=Node(None)# Create a dummy nodeleft,right,self.root.left,self.root.right=dummy,dummy,dummy,dummywhileTrue:ifkey<self.root.key:ifself.root.leftisNoneorkey<self.root.left.key:breakself.root.left,self.root,right.left=right.left,self.root.left,self.rootright,self.root=self.root,rightifkey>self.root.key:ifself.root.rightisNoneorkey>self.root.right.key:breakself.root.right,self.root,left.right=left.right,self.root.right,self.rootleft,self.root=self.root,leftleft.right,right.left=self.root.left,self.root.rightself.root.left,self.root.right=left,rightself.root=dummy.right# Splay the node with key 6splayTree=SplayTree()splayTree.root=Node(10)splayTree.root.left=Node(5)splayTree.root.left.left=Node(3)splayTree.root.left.right=Node(7)splayTree.root.right=Node(15)splayTree.splay(6)

Ternary Trees, a type of multiway tree, were traditionally used for disk storage. They can be visualized as full or complete. Modern applications are more algorithmic than storage based. While not as common as binary trees, they are rich in learning opportunities.

Eachnode in a ternary tree typically has threechildren:

• Left
• Middle
• Right

This organizational layout is especially effective for representing certain types of data or solving specific problems. For instance, ternary trees are optimal when dealing with scenarios that have three distinct outcomes at a decision point.

Here is the Python code:

classTernaryNode:def__init__(self,data,left=None,middle=None,right=None):self.data=dataself.left=leftself.middle=middleself.right=right

TheLazy Segment Tree supplements the standard Segment Tree by allowing delayed updates, making it best suited for the Range Update and Point Query type tasks. It ismore efficient in such scenarios, especially when dealing with a large number of updates.

The Lazy Segment Tree keeps track of pending updates on a range of elements using a separate array or data structure.

When a range update is issued, rather than carrying out the immediate actions for all elements in that range, the tree schedules the update to be executed when required.

The next time an element within that range is accessed (such as during a range query or point update), the tree first ensures that any pending updates get propagated to the concerned range. This propagation mechanism avoids redundant update operations, achieving time complexity of$O(\log n)$ for range updates, range queries, and point updates.

Here is the Python code:

classLazySegmentTree:def__init__(self,arr):self.size=len(arr)self.tree= [0]* (4*self.size)self.lazy= [0]* (4*self.size)self.construct_tree(arr,0,self.size-1,0)defupdate_range(self,start,end,value):self.update_range_util(0,0,self.size-1,start,end,value)defrange_query(self,start,end):returnself.range_query_util(0,0,self.size-1,start,end)# Implement the rest of the methodsdefconstruct_tree(self,arr,start,end,pos):ifstart==end:self.tree[pos]=arr[start]else:mid= (start+end)//2self.tree[pos]=self.construct_tree(arr,start,mid,2*pos+1)+self.construct_tree(arr,mid+1,end,2*pos+2)returnself.tree[pos]defupdate_range_util(self,pos,start,end,range_start,range_end,value):ifself.lazy[pos]!=0:self.tree[pos]+= (end-start+1)*self.lazy[pos]ifstart!=end:self.lazy[2*pos+1]+=self.lazy[pos]self.lazy[2*pos+2]+=self.lazy[pos]self.lazy[pos]=0ifstart>endorstart>range_endorend<range_start:returnifstart>=range_startandend<=range_end:self.tree[pos]+= (end-start+1)*valueifstart!=end:self.lazy[2*pos+1]+=valueself.lazy[2*pos+2]+=valuereturnmid= (start+end)//2self.update_range_util(2*pos+1,start,mid,range_start,range_end,value)self.update_range_util(2*pos+2,mid+1,end,range_start,range_end,value)self.tree[pos]=self.tree[2*pos+1]+self.tree[2*pos+2]defrange_query_util(self,pos,start,end,range_start,range_end):ifself.lazy[pos]:self.tree[pos]+= (end-start+1)*self.lazy[pos]ifstart!=end:self.lazy[2*pos+1]+=self.lazy[pos]self.lazy[2*pos+2]+=self.lazy[pos]self.lazy[pos]=0ifstart>endorstart>range_endorend<range_start:return0ifstart>=range_startandend<=range_end:returnself.tree[pos]mid= (start+end)//2returnself.range_query_util(2*pos+1,start,mid,range_start,range_end)+self.range_query_util(2*pos+2,mid+1,end,range_start,range_end)

ATreap, also known as aCartesian Tree, is a specializedbinary search tree that maintains a dual structure, inheriting characteristics from both aBinary Search Tree (BST) and aHeap.

• BST Order: Every node satisfies the order:$\text{node.left} &lt; \text{node} &lt; \text{node.right}$ based on a specific attribute. Traditionally, it's the node's numerical key-value that is used for this ordering.
• Heap Priority: Each node conforms to the "parent" property, where its heap priority is determined by an attribute independent of the BST order. This attribute is often referred to as the node's "priority".

Thepriority attribute of a Treap node acts as a "tether" or a link that ensures the tree's structure conforms to both BST and heap properties. When nodes are inserted or their keys are updated in a Treap, their priorities are adjusted to maintain both of these properties simultaneously.

When a new node is inserted into the Treap, both BST and heap properties are simultaneously maintained by adjusting the node'spriority based on its key.

1. The node is first inserted based on the BST property (overriding its priority if necessary).
2. Then, it "percolates" up the tree based on its priority to regain the heap characteristic.

Deletion, as always, is a two-step process:

1. Locate the node to be deleted.
2. Replace it with either the left or right child to keep the BST property. The replacement is specifically chosen to preserve the overall priority order of the tree.

• Time Complexity: All primary operations such as Insert, Delete, and Search take$\mathcal{O}(\log n)$ expected time.
• Space Complexity: The structure preserves both BST and heap requirements with each node carrying two data attributes (key and priority).

ABalanced Tree ensures that theBalance Factor—the height difference between left and right subtrees of any node—doesn't exceed one. This property guarantees efficient$O(\log n)$ time complexity forsearch,insertion, anddeletion operations.

• Height Difference: Each node's subtrees differ in height by at most one.
• Recursive Balance: Both subtrees of every node are balanced.

• Efficiency: Avoids the$O(n)$ degradation seen in unbalanced trees.
• Predictability: Provides stable performance, essential for real-time applications.

Thebalanced tree maintains$O(\log n)$ height, while theunbalanced tree could degenerate into a linked list with$O(n)$ height.

Here is the Python code:

classNode:def__init__(self,data):self.data=dataself.left=Noneself.right=Nonedefis_balanced(root):ifrootisNone:returnTrueleft_height=get_height(root.left)right_height=get_height(root.right)returnabs(left_height-right_height)<=1andis_balanced(root.left)andis_balanced(root.right)defget_height(node):ifnodeisNone:return0return1+max(get_height(node.left),get_height(node.right))

TheBinary Search Tree (BST) is a versatile data structure that offers many benefits but also comes with limitations.

1. Quick Search Operations: A balanced BST can perform search operations in$O(\log n)$ time, making it much faster than linear structures like arrays and linked lists.

2. Dynamic Allocation: Unlike arrays that require pre-defined sizes, BSTs are dynamic in nature, adapting to data as it comes in. This results in better space utilization.

3. Space Efficiency: With$O(n)$ space requirements, BSTs are often more memory-efficient than other structures like hash tables, especially in memory-sensitive applications.

4. Versatile Operations: Beyond simple insertions and deletions, BSTs excel in:

   • Range queries
   • Nearest smaller or larger element searches
   • Different types of tree traversals (in-order, pre-order, post-order)

5. Inherent Sorting: BSTs naturally keep their elements sorted, making them ideal for tasks that require efficient and frequent sorting.

6. Predictable Efficiency: Unlike hash tables, which can have unpredictable worst-case scenarios, a balanced BST maintains consistent$O(\log n)$ performance.

7. Practical Utility: BSTs find applications in:

   • Database indexing for quick data retrieval
   • Efficient file searching in operating systems
   • Task scheduling based on priorities

1. Limited Direct Access: While operations likeinsert,delete, andlookup are efficient, direct access to elements by index can be slow, taking$O(n)$ time in unbalanced trees.

2. Risk of Imbalance: If not managed carefully, a BST can become unbalanced, resembling a linked list and losing its efficiency advantages.

3. Memory Costs: Each node in a BST requires additional memory for two child pointers, which could be a concern in memory-constrained environments.

4. Complex Self-Balancing Algorithms: While self-balancing trees like AVL or Red-Black trees mitigate the risk of imbalance, they are more complex to implement.

5. Lack of Global Optimum: BSTs do not readily provide access to the smallest or largest element, unlike data structures like heaps.