Data Structures in Python (Basic to Advanced)

There are several types of data structures in Python, including:

Lists:

Lists are ordered collections of items that can be of different data types. They are defined using square brackets [] and the items are separated by commas.

For example:

my_list = [1, 2, 3, "apple", "banana"]

You can use the following methods to manipulate list in Python:

.append() to add an item to a list
.insert() to insert an item at a specific index in a list
.remove() to remove an item from a list
.pop() to remove an item from a list and return its value
.sort() to sort a list in ascending or descending order
.reverse() to reverse the order of items in a list

Here is an example of using these methods with a list in Python:

my_list = [1, 3, 5, 7]

# Add an item to the end of the list
my_list.append(9)

# Insert an item at index 1
my_list.insert(1, 2)

# Remove an item from the list
my_list.remove(3)

# Remove an item from the end of the list and return its value
last_item = my_list.pop()

# Sort the list in ascending order
my_list.sort()

# Reverse the order of the items in the list
my_list.reverse()

print(my_list) # Output: [9, 7, 5, 2, 1]

2. Tuples: Tuples are similar to lists, but they are immutable, meaning that once created, the items cannot be modified. They are defined using parentheses () and the items are separated by commas.

For example:

my_tuple = (1, 2, 3, "apple", "banana")

3. Sets: Sets are unordered collections of unique items. They are defined using curly braces {} and the items are separated by commas.

For example:

my_set = {1, 2, 3, "apple", "banana"}

4. Dictionaries: A dictionary is a collection of key-value pairs in Python. It is an unordered data structure that allows you to store and access data efficiently. The keys are used to access the values, and each key must be unique within the dictionary.

You can create a dictionary in Python using curly braces {} and colons : to separate keys and values.

For example:

my_dict = {"name": "John", "age": 30, "city": "New York"}

You can access the values in a dictionary using the keys as indices.

For example:

name = my_dict["name"]
print(name) # Output: "John"

You can also use the get() method to access the values in a dictionary. This method returns the value for the given key, or a default value if the key is not found.

For example:

age = my_dict.get("age", 0)
print(age) # Output: 30

country = my_dict.get("country", "USA")
print(country) # Output: "USA"

You can use the following methods to manipulate dictionaries in Python:

keys(): returns a view object that displays a list of all the keys in the dictionary
values(): returns a view object that displays a list of all the values in the dictionary
items(): returns a view object that displays a list of tuples, where each tuple contains a key-value pair
update(): updates the dictionary with the key-value pairs from another dictionary or an iterable object
pop(): removes the key-value pair for the specified key and returns its value
popitem(): removes the last key-value pair in the dictionary and returns it as a tuple
clear(): removes all the key-value pairs from the dictionary

Here is an example of using these methods with a dictionary in Python:

my_dict = {"name": "John", "age": 30, "city": "New York"}

# Get a list of the keys in the dictionary
keys = my_dict.keys()
print(keys) # Output: dict_keys(["name", "age", "city"])

# Get a list of the values in the dictionary
values = my_dict.values()
print(values) # Output: dict_values(["John", 30, "New York"])

# Get a list of tuples containing the key-value pairs
items = my_dict.items()
print(items) # Output: dict_items([("name", "John"), ("age", 30), ("city", "New York")])

# Update the dictionary with another dictionary
my_dict.update({"country": "USA", "zipcode": 12345})
print(my_dict) # Output: {"name": "John", "age": 30, "city": "New York", "country": "USA", "zipcode": 12345}

# Pop an item from the dictionary
age = my_dict.pop("age")
print(age) # Output: 30

# Pop the last item from the dictionary
last_item = my_dict.popitem()
print(last_item) # Output: ("zipcode", 12345)

# Clear the dictionary
my_dict.clear()
print

5. Stack : A stack is a linear data structure that follows the Last In First Out (LIFO) principle. It is a collection of elements, with two main operations: push and pop. The push operation adds an element to the stack, and the pop operation removes the most recently added element that has not yet been removed.

Here is an example of how you can implement a stack in Python using a list:

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

To use this stack, you can create an instance of the Stack class and use its methods to manipulate the stack.

For example:

stack = Stack()

# Push some values to the stack
stack.push(1)
stack.push(2)
stack.push(3)

# Pop an item from the stack
item = stack.pop()
print(item) # Output: 3

# Peek at the top item of the stack
top_item = stack.peek()
print(top_item) # Output: 2

# Check if the stack is empty
is_empty = stack.is_empty()
print(is_empty) # Output: False

# Check the size of the stack
size = stack.size()
print(size) # Output: 2

6. Queue : A queue is a linear data structure that follows the First In First Out (FIFO) principle. It is a collection of elements, with two main operations: enqueue and dequeue. The enqueue operation adds an element to the end of the queue, and the dequeue operation removes the element from the front of the queue.

Here is an example of how you can implement a queue in Python using a list:

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)

    def peek(self):
        return self.items[0]

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

To use this queue, you can create an instance of the Queue class and use its methods to manipulate the queue.

For example:

queue = Queue()

# Enqueue some values to the queue
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

# Dequeue an item from the queue
item = queue.dequeue()
print(item) # Output: 1

# Peek at the front item of the queue
front_item = queue.peek()
print(front_item) # Output: 2

# Check if the queue is empty
is_empty = queue.is_empty()
print(is_empty) # Output: False

# Check the size of the queue
size = queue.size()
print(size) # Output: 2

7. Linked List : A linked list is a linear data structure that consists of a group of nodes, where each node contains a value and a pointer to the next node in the list. It is an efficient data structure for inserting and deleting elements, but it is not as efficient for accessing and searching elements.

Here is an example of how you can implement a linked list in Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = new_node

    def prepend(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def delete_by_value(self, value):
        if self.head is None:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        current_node = self.head
        while current_node.next is not None:
            if current_node.next.value == value:
                current_node.next = current_node.next.next
                return
            current_node = current_node.next

    def delete_by_index(self, index):
        if self.head is None:
            return
        if index == 0:
            self.head = self.head.next
            return
        current_index = 0
        current_node = self.head
        while current_node.next is not None:
            if current_index == index - 1:
                current_node.next = current_node.next.next
                return
            current_node = current_node.next
            current_index += 1

    def find(self, value):
        if self.head is None:
            return None
        current_node = self.head
        while current_node is not None:
            if current_node.value == value:
                return current_node
            current_node = current_node.next
        return None

To use this linked list, you can create an instance of the LinkedList class and use its methods to manipulate the list.

For example:

linked_list = LinkedList()

# Append some values to the list
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

# Prepend a value to the list
linked_list.prepend(0)

# Delete a value by its index
linked_list.delete_by_index(2)

# Delete a value by its value
linked_list.delete_by_value(2)

# Find a value in the list
node = linked_list.find(1)
if node is not None:
    print(node.value) # Output: 1

8. Doubly-LinkedList: A doubly-linked list is a linear data structure that consists of a group of nodes, where each node contains a value and pointers to the previous and next nodes in the list. It allows for efficient insertion and deletion of elements, as well as the ability to move forward and backward through the list.

Here is an example of how you can implement a doubly-linked list in Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    def prepend(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

    def delete(self, node):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        if node == self.head:
            self.head = node.next
            self.head.prev = None
            return
        if node == self.tail:
            self.tail = node.prev
            self.tail.next = None
            return
        node.prev.next = node.next
        node.next.prev = node.prev

    def find(self, value):
        if self.head is None:
            return None
        current_node = self.head
        while current_node is not None:
            if current_node.value == value:
                return current_node
            current_node = current_node.next
        return None

To use this doubly-linked list, you can create an instance of the DoublyLinkedList class and use its methods to manipulate the list.

For example:

linked_list = DoublyLinkedList()

# Append some values to the list
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

9. Tree : A tree is a non-linear data structure that consists of a set of nodes organized in a hierarchical structure. Each node in a tree has a value and a list of references to its child nodes. The node at the top of the tree is called the root, and the nodes without children are called leaf nodes.

Here is an example of how you can implement a tree in Python using a list of lists:

class Tree:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, value):
        self.children.append(Tree(value))

    def __repr__(self):
        return "Tree({})".format(self.value)

To use this tree, you can create an instance of the Tree class and use its add_child() method to add child nodes to the tree.

For example:

tree = Tree(1)
tree.add_child(2)
tree.add_child(3)
tree.add_child(4)
tree.children[0].add_child(5)
tree.children[0].add_child(6)
tree.children[1].add_child(7)

print(tree)
# Output: Tree(1)
#         |
#         |-- Tree(2)
#         |    |
#         |    |-- Tree(5)
#         |    |-- Tree(6)
#

We can also implement Tree without using list . Here is an example of how you can implement a tree in Python without using a list:

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return "Tree({})".format(self.value)

root = Tree(1, Tree(2, Tree(4), Tree(5)), Tree(3, Tree(6), Tree(7)))

print(root)
# Output: Tree(1)
#         |
#         |-- Tree(2)
#         |    |
#         |    |-- Tree(4)
#         |    |-- Tree(5)
#         |
#         |-- Tree(3)
#              |
#              |-- Tree(6)
#              |-- Tree(7)

In this implementation, each node in the tree has a value and pointers to its left and right child nodes. The left and right arguments are optional and default to None. This allows you to create a tree by recursively constructing nodes and linking them together.

10 . Graph : A graph is a non-linear data structure that consists of a set of nodes (also called vertices) and a set of edges that connect the nodes. The edges can be directed (arrows) or undirected, and the graph can be weighted (values assigned to the edges) or unweighted.

There are two main ways to represent a graph in Python:

Adjacency Matrix: This is a two-dimensional matrix that represents the edges in the graph. The rows and columns of the matrix represent the nodes in the graph, and the cells contain either a 1 (if there is an edge between the nodes) or a 0 (if there is no edge).
Adjacency List: This is a list of lists, where each sublist represents the neighbors (adjacent nodes) of a node in the graph.

Here is an example of how you can implement a graph using an adjacency matrix in Python:

class Graph:
    def __init__(self, num_vertices, directed=False):
        self.num_vertices = num_vertices
        self.directed = directed
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]

    def add_edge(self, v1, v2, weight=1):
        if v1 >= self.num_vertices or v2 >= self.num_vertices or v1 < 0 or v2 < 0:
            raise ValueError("Vertices out of bounds")
        if weight < 1:
            raise ValueError("An edge cannot have weight less than 1")
        self.matrix[v1][v2] = weight
        if not self.directed:
            self.matrix[v2][v1] = weight

Here is an example of how you can implement a graph using an adjacency list in Python:

class Graph:
    def __init__(self, num_vertices, directed=False):
        self.num_vertices = num_vertices
        self.directed = directed
        self.graph = [[] for _ in range(num_vertices)]

    def add_edge(self, v1, v2, weight=1):
        if v1 >= self.num_vertices or v2 >= self.num_vertices or v1 < 0 or v2 < 0:
            raise ValueError("Vertices out of bounds")
        if weight < 1:
            raise ValueError("An edge cannot have weight less than 1")
        self.graph[v1].append((v2, weight))
        if not self.directed:
            self.graph[v2].append((v1, weight))

To use this graph, you can create an instance of the Graph class and use its add_edge() method to add edges between the nodes. The directed argument specifies whether the graph is directed or undirected.

For example:

graph = Graph(5, directed=True)

# Add some edges to the graph
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 4)

11. Heap: A heap is a binary tree that has a specific structure, either a min-heap or a max-heap. In a min-heap, the value of each node is greater than or equal to the value of its children, and in a max-heap, the value of each node is less than or equal to the value of its children.

Here is an example of how you can implement a min-heap in Python:

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)

    def pop(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return min_value

    def _bubble_up(self, index):
        if index == 0:
            return
        parent = (index - 1) // 2
        if self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._bubble_up(parent)

    def _bubble_down(self, index):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._bubble_down(smallest)

To use this min-heap, you can create an instance of the MinHeap class and use its push() and pop() methods to add and remove elements from the heap.

For example:

heap = MinHeap()
# Add some values to the heap
heap.push(5)
heap.push(2)
heap.push(3)

12. Priority-Queue : A priority queue is a queue that orders elements based on a priority. Elements with a higher priority are dequeued before elements with a lower priority.

One way to implement a priority queue in Python is to use a heap data structure.

13. Trie : A trie (also called a prefix tree) is a tree-like data structure that is used to store a set of strings. It is space-efficient and has fast insertion, deletion, and search times.

To implement a trie in Python, you can use a dictionary to represent the edges between nodes. Each node in the trie will be a dictionary, with keys being the characters in the string and values being the child nodes.

Here is an example of how you can implement a trie in Python:

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        curr_node = self.root
        for ch in word:
            if ch not in curr_node:
                curr_node[ch] = {}
            curr_node = curr_node[ch]
        curr_node['*'] = True  # Mark the end of the word

    def search(self, word):
        curr_node = self.root
        for ch in word:
            if ch not in curr_node:
                return False
            curr_node = curr_node[ch]
        return '*' in curr_node

To use this trie, you can create an instance of the Trie class and use its insert() and search() methods to add and search for strings in the trie.

For example:

trie = Trie()

# Insert some words into the trie
trie.insert('cat')
trie.insert('car')
trie.insert('cab')
trie.insert('bat')

# Search for some words in the trie
print(trie.search('cat'))  # Output: True
print(trie.search('car'))  # Output: True
print(trie.search('cab'))  # Output: True
print(trie.search('bat'))  # Output: True
print(trie.search('ca'))   # Output: False
print(trie.search('ba'))   # Output: False

14. Hash Table : A hash table is a data structure that uses a hash function to map keys to indices in an array. It is used to implement associative arrays and is efficient for inserting, deleting, and searching for elements.

To implement a hash table in Python, you can use a list to store the values and a dictionary to store the keys and their corresponding indices in the list.

Here is an example of how you can implement a hash table in Python:

class HashTable:
    def __init__(self):
        self.values = []
        self.keys = {}

    def put(self, key, value):
        if key in self.keys:
            self.values[self.keys[key]] = value
        else:
            self.keys[key] = len(self.values)
            self.values.append(value)

    def get(self, key):
        if key in self.keys:
            return self.values[self.keys[key]]
        return None

To use this hash table, you can create an instance of the HashTable class and use its put() and get() methods to add and retrieve elements from the table.

For example:

table = HashTable()

# Add some elements to the table
table.put('cat', 'feline')
table.put('dog', 'canine')
table.put('bird', 'avian')

# Retrieve some elements from the table
print(table.get('cat'))  # Output: 'feline'
print(table.get('dog'))  # Output: 'canine'
print(table.get('bird')) # Output: 'avian'
print(table.get('fish')) # Output: None

15. Bloom filter : A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set. It is space-efficient and has fast insertion and membership testing times, but it may produce false positives (i.e., it may say that an element is a member of the set when it is not).

To implement a Bloom filter in Python, you can use a bit array to store the elements and several hash functions to map the elements to indices in the array.

Here is an example of how you can implement a Bloom filter in Python:

import math
import hashlib

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = [0] * size

    def add(self, string):
        for seed in range(self.hash_count):
            result = int(hashlib.sha1(string.encode('utf-8') + str(seed).encode('utf-8')).hexdigest(), 16) % self.size
            self.bit_array[result] = 1

    def check(self, string):
        for seed in range(self.hash_count):
            result = int(hashlib.sha1(string.encode('utf-8') + str(seed).encode('utf-8')).hexdigest(), 16) % self.size
            if self.bit_array[result] == 0:
                return False
        return True

To use this Bloom filter, you can create an instance of the BloomFilter class and use its add() and check() methods to add elements to the filter and check for membership.

For example:

filter = BloomFilter(100, 3)

# Add some elements to the filter
filter.add('cat')
filter.add('dog')
filter.add('bird')

# Check for membership in the filter
print(filter.check('cat'))  # Output: True
print(filter.check('dog'))  # Output: True
print(filter.check('bird')) # Output: True
print(filter.check('fish')) # Output: False (may be a false positive)

16. AVL Tree : An AVL tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree that maintains the height balance property: the height of the left and right subtrees of any node differ by at most 1. This property allows the tree to remain balanced, which means that the tree has a height that is logarithmic in the number of nodes, resulting in fast search, insertion, and deletion times.

To implement an AVL tree, you can use a class to represent the nodes in the tree. Each node will have a value, a left child, a right child, and a height. The height of a node is the number of edges in the longest path from the node to a leaf.

To insert a new value into the tree, you can use a recursive function that starts at the root of the tree and compares the value to the value of the current node. If the value is less than the current node’s value, it will be inserted into the left subtree; otherwise, it will be inserted into the right subtree. After the value has been inserted, the function will update the height of the node and check the balance of the tree. If the tree is unbalanced, the function will perform a rotation to restore the balance.

To delete a value from the tree, you can use a recursive function that starts at the root of the tree and searches for the value to delete. If the value is not found, the function will return without doing anything. If the value is found, the function will remove the node and update the height of the parent node. If the tree is unbalanced after the deletion, the function will perform a rotation to restore the balance.

The AVL tree has several operations that you can perform, such as searching for a value, inserting a new value, deleting a value, and finding the minimum or maximum value in the tree. It is a useful data structure for storing and searching for elements, and it is widely used in various applications.

There are four rotation techniques that you can use to maintain the balance of an AVL tree: left rotation, right rotation, left-right rotation, and right-left rotation.

Left rotation:

This rotation is used to balance a tree when the right subtree of a node is taller than the left subtree by more than 1.
To perform a left rotation, you can follow these steps:

Set the right child of the node as the new root of the subtree.
Set the left child of the new root as the right child of the node.
Set the node as the left child of the new root.
Update the heights of the node and the new root.

Right rotation:

This rotation is used to balance a tree when the left subtree of a node is taller than the right subtree by more than 1.
To perform a right rotation, you can follow these steps:

Set the left child of the node as the new root of the subtree.
Set the right child of the new root as the left child of the node.
Set the node as the right child of the new root.
Update the heights of the node and the new root.

Left-right rotation:

This rotation is used to balance a tree when the left subtree of a node is taller than the right subtree by more than 1, and the right subtree of the left child is taller than the left subtree.
To perform a left-right rotation, you can follow these steps:

Perform a left rotation on the left child of the node.
Perform a right rotation on the node.

Right-left rotation:

This rotation is used to balance a tree when the right subtree of a node is taller than the left subtree by more than 1, and the left subtree of the right child is taller than the right subtree.
To perform a right-left rotation, you can follow these steps:

Perform a right rotation on the right child of the node.
Perform a left rotation on the node.

These rotation techniques are used to restore the balance of the tree after an insertion or deletion operation. By performing the appropriate rotation, you can ensure that the height balance

Python Code for AVL Tree

class treeNode(object):
 def __init__(self, value):
  self.value = value
  self.left = None
  self.right = None
  self.height = 1

class AVLTree(object):

 def insert(self, root, key):
 
  if not root:
   return treeNode(key)
  elif key < root.value:
   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))

  b = self.getBal(root)

  if b > 1 and key < root.left.value:
   return self.right_Rotate(root)

  if b < -1 and key > root.right.value:
   return self.left_Rotate(root)

  if b > 1 and key > root.left.value:
   root.left = self.left_Rotate(root.left)
   return self.right_Rotate(root)

  if b < -1 and key < root.right.value:
   root.right = self.right_Rotate(root.right)
   return self.left_Rotate(root)

  return root

 def left_Rotate(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 right_Rotate(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 getBal(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.value), end="")
  self.preOrder(root.left)
  self.preOrder(root.right)

Tree = AVLTree()
root = None

root = Tree.insert(root, 1)
root = Tree.insert(root, 2)
root = Tree.insert(root, 3)
root = Tree.insert(root, 4)
root = Tree.insert(root, 5)
root = Tree.insert(root, 6)

# Preorder Traversal
print("Preorder traversal of the",
 "constructed AVL tree is")
Tree.preOrder(root)
print()

17. Red-Black Tree :

A red-black tree is a self-balancing binary search tree that uses color to maintain the balance of the tree. It is a type of balanced binary search tree, which means that it has a height that is logarithmic in the number of nodes, resulting in fast search, insertion, and deletion times.

A red-black tree has the following properties:

Each node is either red or black.
The root and leaf nodes are always black.
If a node is red, both of its children must be black.
Every path from the root to a leaf must contain the same number of black nodes.

To implement a red-black tree, you can use a class to represent the nodes in the tree. Each node will have a value, a left child, a right child, a parent, and a color.

To insert a new value into the tree, you can use a recursive function that starts at the root of the tree and compares the value to the value of the current node. If the value is less than the current node’s value, it will be inserted into the left subtree; otherwise, it will be inserted into the right subtree. After the value has been inserted, the function will check for violations of the red-black tree properties and fix them if necessary.

To delete a value from the tree, you can use a recursive function that starts at the root of the tree and searches for the value to delete. If the value is not found, the function will return without doing anything. If the value is found, the function will remove the node and fix any violations of the red-black tree properties.

The red-black tree has several operations that you can perform, such as searching for a value, inserting a new value, deleting a value, and finding the minimum or maximum value in the tree. It is a useful data structure for storing and searching for elements, and it is widely used in various applications.

Python Code for Red-Black Tree

# Define Node
class Node():
    def __init__(self,val):
        self.val = val                                   # Value of Node
        self.parent = None                               # Parent of Node
        self.left = None                                 # Left Child of Node
        self.right = None                                # Right Child of Node
        self.color = 1                                   # Red Node as new node is always inserted as Red Node

# Define R-B Tree
class RBTree():
    def __init__(self):
        self.NULL = Node ( 0 )
        self.NULL.color = 0
        self.NULL.left = None
        self.NULL.right = None
        self.root = self.NULL


    # Insert New Node
    def insertNode(self, key):
        node = Node(key)
        node.parent = None
        node.val = key
        node.left = self.NULL
        node.right = self.NULL
        node.color = 1                                   # Set root colour as Red

        y = None
        x = self.root

        while x != self.NULL :                           # Find position for new node
            y = x
            if node.val < x.val :
                x = x.left
            else :
                x = x.right

        node.parent = y                                  # Set parent of Node as y
        if y == None :                                   # If parent i.e, is none then it is root node
            self.root = node
        elif node.val < y.val :                          # Check if it is right Node or Left Node by checking the value
            y.left = node
        else :
            y.right = node

        if node.parent == None :                         # Root node is always Black
            node.color = 0
            return

        if node.parent.parent == None :                  # If parent of node is Root Node
            return

        self.fixInsert ( node )                          # Else call for Fix Up


    def minimum(self, node):
        while node.left != self.NULL:
            node = node.left
        return node


    # Code for left rotate
    def LR ( self , x ) :
        y = x.right                                      # Y = Right child of x
        x.right = y.left                                 # Change right child of x to left child of y
        if y.left != self.NULL :
            y.left.parent = x

        y.parent = x.parent                              # Change parent of y as parent of x
        if x.parent == None :                            # If parent of x == None ie. root node
            self.root = y                                # Set y as root
        elif x == x.parent.left :
            x.parent.left = y
        else :
            x.parent.right = y
        y.left = x
        x.parent = y


    # Code for right rotate
    def RR ( self , x ) :
        y = x.left                                       # Y = Left child of x
        x.left = y.right                                 # Change left child of x to right child of y
        if y.right != self.NULL :
            y.right.parent = x

        y.parent = x.parent                              # Change parent of y as parent of x
        if x.parent == None :                            # If x is root node
            self.root = y                                # Set y as root
        elif x == x.parent.right :
            x.parent.right = y
        else :
            x.parent.left = y
        y.right = x
        x.parent = y


    # Fix Up Insertion
    def fixInsert(self, k):
        while k.parent.color == 1:                        # While parent is red
            if k.parent == k.parent.parent.right:         # if parent is right child of its parent
                u = k.parent.parent.left                  # Left child of grandparent
                if u.color == 1:                          # if color of left child of grandparent i.e, uncle node is red
                    u.color = 0                           # Set both children of grandparent node as black
                    k.parent.color = 0
                    k.parent.parent.color = 1             # Set grandparent node as Red
                    k = k.parent.parent                   # Repeat the algo with Parent node to check conflicts
                else:
                    if k == k.parent.left:                # If k is left child of it's parent
                        k = k.parent
                        self.RR(k)                        # Call for right rotation
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.LR(k.parent.parent)
            else:                                         # if parent is left child of its parent
                u = k.parent.parent.right                 # Right child of grandparent
                if u.color == 1:                          # if color of right child of grandparent i.e, uncle node is red
                    u.color = 0                           # Set color of childs as black
                    k.parent.color = 0
                    k.parent.parent.color = 1             # set color of grandparent as Red
                    k = k.parent.parent                   # Repeat algo on grandparent to remove conflicts
                else:
                    if k == k.parent.right:               # if k is right child of its parent
                        k = k.parent
                        self.LR(k)                        # Call left rotate on parent of k
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.RR(k.parent.parent)              # Call right rotate on grandparent
            if k == self.root:                            # If k reaches root then break
                break
        self.root.color = 0                               # Set color of root as black


    # Function to fix issues after deletion
    def fixDelete ( self , x ) :
        while x != self.root and x.color == 0 :           # Repeat until x reaches nodes and color of x is black
            if x == x.parent.left :                       # If x is left child of its parent
                s = x.parent.right                        # Sibling of x
                if s.color == 1 :                         # if sibling is red
                    s.color = 0                           # Set its color to black
                    x.parent.color = 1                    # Make its parent red
                    self.LR ( x.parent )                  # Call for left rotate on parent of x
                    s = x.parent.right
                # If both the child are black
                if s.left.color == 0 and s.right.color == 0 :
                    s.color = 1                           # Set color of s as red
                    x = x.parent
                else :
                    if s.right.color == 0 :               # If right child of s is black
                        s.left.color = 0                  # set left child of s as black
                        s.color = 1                       # set color of s as red
                        self.RR ( s )                     # call right rotation on x
                        s = x.parent.right

                    s.color = x.parent.color
                    x.parent.color = 0                    # Set parent of x as black
                    s.right.color = 0
                    self.LR ( x.parent )                  # call left rotation on parent of x
                    x = self.root
            else :                                        # If x is right child of its parent
                s = x.parent.left                         # Sibling of x
                if s.color == 1 :                         # if sibling is red
                    s.color = 0                           # Set its color to black
                    x.parent.color = 1                    # Make its parent red
                    self.RR ( x.parent )                  # Call for right rotate on parent of x
                    s = x.parent.left

                if s.right.color == 0 and s.right.color == 0 :
                    s.color = 1
                    x = x.parent
                else :
                    if s.left.color == 0 :                # If left child of s is black
                        s.right.color = 0                 # set right child of s as black
                        s.color = 1
                        self.LR ( s )                     # call left rotation on x
                        s = x.parent.left

                    s.color = x.parent.color
                    x.parent.color = 0
                    s.left.color = 0
                    self.RR ( x.parent )
                    x = self.root
        x.color = 0


    # Function to transplant nodes
    def __rb_transplant ( self , u , v ) :
        if u.parent == None :
            self.root = v
        elif u == u.parent.left :
            u.parent.left = v
        else :
            u.parent.right = v
        v.parent = u.parent


    # Function to handle deletion
    def delete_node_helper ( self , node , key ) :
        z = self.NULL
        while node != self.NULL :                          # Search for the node having that value/ key and store it in 'z'
            if node.val == key :
                z = node

            if node.val <= key :
                node = node.right
            else :
                node = node.left

        if z == self.NULL :                                # If Kwy is not present then deletion not possible so return
            print ( "Value not present in Tree !!" )
            return

        y = z
        y_original_color = y.color                          # Store the color of z- node
        if z.left == self.NULL :                            # If left child of z is NULL
            x = z.right                                     # Assign right child of z to x
            self.__rb_transplant ( z , z.right )            # Transplant Node to be deleted with x
        elif (z.right == self.NULL) :                       # If right child of z is NULL
            x = z.left                                      # Assign left child of z to x
            self.__rb_transplant ( z , z.left )             # Transplant Node to be deleted with x
        else :                                              # If z has both the child nodes
            y = self.minimum ( z.right )                    # Find minimum of the right sub tree
            y_original_color = y.color                      # Store color of y
            x = y.right
            if y.parent == z :                              # If y is child of z
                x.parent = y                                # Set parent of x as y
            else :
                self.__rb_transplant ( y , y.right )
                y.right = z.right
                y.right.parent = y

            self.__rb_transplant ( z , y )
            y.left = z.left
            y.left.parent = y
            y.color = z.color
        if y_original_color == 0 :                          # If color is black then fixing is needed
            self.fixDelete ( x )


    # Deletion of node
    def delete_node ( self , val ) :
        self.delete_node_helper ( self.root , val )         # Call for deletion


    # Function to print
    def __printCall ( self , node , indent , last ) :
        if node != self.NULL :
            print(indent, end=' ')
            if last :
                print ("R----",end= ' ')
                indent += "     "
            else :
                print("L----",end=' ')
                indent += "|    "

            s_color = "RED" if node.color == 1 else "BLACK"
            print ( str ( node.val ) + "(" + s_color + ")" )
            self.__printCall ( node.left , indent , False )
            self.__printCall ( node.right , indent , True )

    # Function to call print
    def print_tree ( self ) :
        self.__printCall ( self.root , "" , True )


if __name__ == "__main__":
    bst = RBTree()

    bst.insertNode(10)
    bst.insertNode(20)
    bst.insertNode(30)
    bst.insertNode(5)
    bst.insertNode(4)
    bst.insertNode(2)

    bst.print_tree()

    print("\nAfter deleting an element")
    bst.delete_node(2)
    bst.print_tree()

# source: favtutor.com

18. B-tree : A B-tree is a self-balancing tree data structure that is used to store large amounts of data in a structured way. It is commonly used in file systems and databases to improve the performance of insert, delete, and search operations.

A B-tree has the following properties:

It is a multiway tree, meaning that each node can have more than two children.
The tree is balanced, meaning that the length of the path from the root to any leaf is approximately the same for all leaves.
All leaves are at the same depth.
The keys stored in the tree are stored in a sorted order, with the smallest key at the leftmost leaf and the largest key at the rightmost leaf.

To implement a B-tree in Python, you can use a class to represent the nodes in the tree. Each node will have a list of keys and a list of child nodes.

Python Blogs

Search This Blog