Python for AI 106

Acknowledgement: This post is based mainly on Dr. Vinh Dinh Nguyen’s presentation and slides and partly on on TA, STA, and peers’ responses from the course AIO2025 offered by AI VIETNAM.

Relevance: The audience of this lecture were those who learned Python for AI 105, have some coding experience, and know a bit of AI knowledge. It is recommended that complete newbies should read the materials and spend time practicing writing code without the assistance of AI over and over again to improve their coding and code-reading skills. Note that only necessary Python knowledge is introduced here.

________quote____________________
-quoter’s name

Up to this point, we’ve discussed primary built-in data structures. Even though they may be enough for general tasks, user-defined data structures like trees, stack, and queue are much more flexible and efficient while handling complex problems. In today’s post, we’ll delve into tree, stack, queue, and their algorithms. We’ll also discuss some applications in Machine Learning including decision tree.

Tree

Previously learned data structures are considered linear since they store data sequentially and take linear time to retrieve an element, that is, we must traverse through up to the whole list depending on where the desired element stays. For example, wee need at least seven steps to find number 8.

DEMONSTRATION

If a list of millions of elements is given, searching will be definitely time-consuming. This is where a tree data structure comes into play. Some familiar real-world examples are

• a computer: folder, subfolders, and files
• a webpage: title, headings, subheadings, and detailed content
• a database: table, columns, and information.

In contrast to a real-life tree, a programming tree, looking more like a cluster of grapes to me, has its root on top and left and right branches coming down from there. Let’s look at the example above using a tree, particularly a binary search tree—left-branched values are less than right-branched ones. We’ll talk more about how to design a tree properly later.

DEMONSTRATION

Explanation within demonstration or words. depending on demonstration

In this case, number 8 can be found within only two steps, which requires way fewer calculations than linear data structures, thanks to how the tree is organized.

Terminology

Formally, a tree is a non-linear hierachial data structure that consists of nodes connected by edges.

• Node: (circle) the fundamental building block of a tree that holds data
• Edge: (line) the connection representing a parent-child relationship like in classes.

Key terminology in tree data structure includes:

• Parent Node: the immediate predecessor of another
• Child Node: an immediate succesor of another
• Siblings: the child nodes that have the same parent node
• Root Node: the topmost unique node of a tree—no parent node
• Leaf Node: the bottommost node of a branch—no child node (no branch can grow out of a leaf)
• Height: the length of the longest path from the node to a leaf node
• Depth: the number of edges on the path from the root node to that node—levels/layers counted topdown
• Subtree: any node with its decendants—any node can be the root node
• Ancestor Node: any predecessor node of a node.

DEMONSTRATION. depending on the image to change the above to a table with examples or not

Notice that we only need the root node to know the whole tree since we can track down the rest via edges. We’ll implement this idea in a later section.

Implementation of a Node

We want to implement tree data structure from which any tree can be produced. Among all data types we’ve learned so far, a class would highly likely do so.

1. Initialization:
   • A node holds data -> need to pass data to the class
   • A node can have one or more child -> need to have an attribute set to be a list
   • A node can have only one parent -> need to have an attribute for it.
2. Connection by adding a child to a node:
   • Set the current node to be a parent
   • Append a child to the parent
3. Others:
   • Get height
   • Get depth

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []
        self.parent = None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

# an object example here

We can certainly make a clear and pretty tree visualization using package Graph.

DEMONSTRATION and EXPLANATION OPERATIONS ON BINARY TREE SLIDE

Types of Tree
Binary search tree mentioned above is a specific kind of binary tree. Trees can be categorized into the main following types based on the maximum number of children of a node. We focus on binary tree in this post.

• Binary Tree: each node has at most 2 child nodes
• Ternary Tree: each node has at most 3 child nodes
• N-ary Tree: each node has at most N child nodes.

Applications in AI
One of the basic Machine Learning algorithms is Decision Tree. It is simple but useful for classification problems and data mining. For example, we can create a decision tree from a table of sepal and petal data, which helps identify the species of Iris flower.

DEMONSTRATION

Another application is K-Dimensional Tree (K-D Tree) where a node contains a list of values and K represents its length. This type of tree is widespread in Machine Learning.

Algorithms on (Binary) Tree: DFS vs BFS

Going back to the question posed at the beginning of this post, we’d like know how to search and retrieve an element in a data structure. In our case, we want to traversal on a tree, meaning visiting each node in a tree data structure exactly once in a certain order. There are two elementary algorithms for this process. Both start from the root node.

• Depth First Search:
  1. traveling through all nodes along one branch
  2. backtracking to the next branch
• Breadth First Search:
  1. traveling through all nodes on the same depth level
  2. moving to vertices on the next layer

DEMONTRATION

To implement these algorithms, we’ll need more advanced data structures rather than just a simple list since the search requires flexible movements. They are stack and queue.

Pro tip: Tree traversal is just one of many problems DFS and BFS can solve. Stack and queue are used to implement many other algorithms or work with different data structures.

Stack - DFS

Stack is a linear data structure using a list’s structure as its building block.

• Its principle is Last-In First-Out (LIFO).
• Elements are inserted into and removed from only one end.
  • push() to insert an element
  • pop() to remove an element and return it.

You can think of a vending machine. New soda cans are added from the front in this order: a Coke, a Sprite, and a Fanta. A customer can only get them from the front in the reverse order: the Fanta, the Sprite, and the Coke.

DEMONTRATION

Implementation

class MyStack:
    def __init__(self):
        self.__items = []

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

    # get the last item
    def pop(self):
        if not self.is_empty():
            return self.__items.pop()

    def is_empty(self):
        return len(self.__Items) == 0

We can also limit the number of elements in a stack by defining a capacity attribute inside the Stack class. If so, a method to check if the stack is full should be created.

Depth First Search Algorithm

DEMONTRATION and EXPLANATION

We need to create a binary tree. Earlier we said we only need the root node, so here stack only takes the root node. That node itself carries the whole tree.

Use stack to work with this tree. Start with an empty stack. Push child nodes (right first, then left) and pop one node.

TreeNode only needs to contain value, left, and right

Queue - BFS

Queue is a linear data structure using a list’s structure as its building block.

• Its principle is First-In First-Out (FIFO).
• Elements are inserted into and removed from opposite ends.
  • enqueue() is to insert an element to the end/rear
  • dequeue() is to remove an element from the front.

Imagine a queue of people are waiting at the cash register in a store. Customers line up to the end, but the cashier would serve the first person to enter the line, the second, and so on.

DEMONTRATION

Implementation

Using List

class MyQueue:
    def __init__(self):
        self.__item = []

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

    # get the first element
    def dequeue(self):
        if self.__items.is_empty():
            return self.__items.pop(0)

    def is_empty():
        return len(self.__items) == 0

Like stack, we can also limit the number of elements in a queue and need a method to check if the queue is full in that case.

We can also make a queue object with available packages rather than creating our own class. These packages also have enqueue and dequeue operations but both are named differently. Make sure to import necessary packages to use them. Check out this website for visualization.

Using deque Package

from collections import deque

# initialize a queue
q = deque()

# enqueue an element
q.append(1)
q.append(2)
print(f'Initial queue: {q}, {list(q)}')

# dequeue an element
print(q.popleft())
print(f'Queue after dequeue: {q}, {list(q)}')

'''
Initial queue: deque([1, 2]), [1, 2]
1
Queue after dequeue: deque([2]), [2]
'''

Using Queue Package

from queue import Queue

# initialize a queue
q =  Queue()

# enqueue an element
q.put(1)
q.put(2)
print(f'Initial queue: {q.queue}, {list(q.queue)}')

# dequeue an element
print(q.get())
print(f'Queue after dequeue: {q.queue}, {list(q.queue)}')

'''
Initial queue: deque([1, 2]), [1, 2]
1
Queue after dequeue: deque([2]), [2]
'''

Breadth First Search Algorithm

DEMONTRATION and EXPLANATION

Push the child nodes (left first, then right)

Binary Tree

As we know, left-branched values need be less than right-branched in a binary search tree. Not just binary search tree, other types of tree need to follow specific rules for their data to be organized in a systematic and useful manner.

Recall binary tree is a (non-linear) tree data structure in which each node can have at most two children referred to as the left child and right child. Based on this definition, binary trees can be separated into four types: left-skewed tree, right-skewed tree, skewed tree, and full binary tree.

DEMONSTRATION

Observe that some of tree structures can lead to inefficient traversals as they are not well-suited optimized search algorithms. The idea of a balanced tree is introduced to handle such situations.

DEMONSTRATION and EXPLANATION from why balanced binary tree? slide

Balanced Binary Tree

A binary tree is said to be balanced if it satisfies the following conditions:

• the difference (df) between the heights of the left and the right subtrees for any node is at most one
• the left subtree is balanced
• the right subtree is balanced.

To determine df of all subtrees, it’s sufficient to check it at every node of the tree.

DEMONSTRATION and EXPLANATION

Operations on Binary Tree

You may wonder, How can I construct a balanced binary tree from scratch or update one to be balanced?

That’s a valid question and we’ll now go over some operations with which we can apply balanced-tree rules. It may take time to carry out these operations at first, but life will be far easier once you have a well-organized tree. You will query a tree more than creating it after all.

Insert a Node

implementation -> level-order: bfs

DEMONSTRATION and EXPLANATION

Delete a Node

delete 1 -> 3 or 4 to be the root -> 3 because it is the deepest rightmost (next slide)

why deepest rightmost? preserve balance

:heavy_exclamation mark: Binary Tree Limitations

use dfs:

to find 9 -> 5 12 0 5 8 11 9 -> 6 steps: too many steps

to find 3 -> too many steps

-> need a way to reorganized this tree to not waste time -> binary search tree

for the image on bst algorithm: if remove 30 -> add 80 (deepest rightmost) -> not bst anymore -> add 40 instead (righmost) -> preserve balance

Binary Search Tree Algorithm

__________Heading 3____________

Concept Name

______________________TABLE ONLY__________________________________________________________________

# _________________explanation_________________

_________________setup_________________

# test
_________________code_________________

'''
_________________rendered output_________________
'''

# _________________explanation_________________

_________________setup_________________

# test
_________________code_________________

'''
_________________rendered output_________________
'''

_________________code_________________

# _________________explanation_________________

_________________setup_________________

# test
_________________code_________________

'''
_________________rendered output_________________
'''

# _________________explanation_________________

_________________setup_________________

# test
_________________code_________________

'''
_________________rendered output_________________
'''