Skip to main content

Datastructure & Algorithm: Tree

 What is Tree?

  • Tree is a data structure which has a hierarchy system.  

Concepts & Words

  • Node: each element of the tree
  • Root: The uppermost node of the tree
  • Parent: a node that is above another node
  • Child: a node that is under another node
  • Leaf: Nodes have no children
  • Edge: The line connects nodes
  • Level: The depth from the root (The level of the root is 0)
  • Height: Max level of the tree

Features of Tree

  • Hierarchy System: the relationship between subordinates and superiors
  • No cycle: you can't go backward
  • Connections: All nodes are connected from the root
  • Distinct route: There is only one route between two random nodes

Implementing the Tree

Core Elements to implement

1. Node Class: Each node has the reference to its child node and data
2. Main Functions

    • Insert: Adding a new node
    • Search: Finding a specific value
    • Traversal: Visiting all nodes
    • Delete: Removing a node
3. Ways Of Traversing A Tree

  • Preorder: Root -> Left -> Right
  • Inorder: Left -> Root -> Right
  • Postorder: Left -> Right -> Root

4. Recursion

  • Tree is a basically recursive structure. Each node can be a small tree, so most of operations are implemented as recursion.
Recursion Pattern in Python

def tree_operation(node, data):
    # Base case (exit condition)
    if node is None:
        return result    
    # Recursion Case (Calling itself)
    if condtion:
        return tree_operation(node.left, data)
    else:
        return tree_operation(node.right, data)

Pseudo Code For Implementing

Step 1. Define Node Class

Class Node:
    data = value
    left = None
    right = None

Step 2. Insertion

function insert(root, new_value):
    if root == None:
        create a new node and return
    if new value < root.data:
        root.left = insert(root.left, new_value)
    else:
        root.right = insert(root.right, new_value)
    return root

Step 3. Search

function search(root, target_value):
    if root == None or root.data == target_value:
        return root
    if root.data > target_value:
        return search(root.left, target_value)
    else:
        return search(root.right, target_value)
Labels:

Comments

Post a Comment

Popular posts from this blog

ML Zoomcamp 2025 : Week 1. Intro to Machine Learning

Week 1. Intro to Machine Learning Machine Learning Definition A process of extracting patterns from data An algorithm that learns patterns from data and predicts outcomes. Related concepts Model:  The output of a machine learning algorithm after it has been trained on data. A model encapsulates all the patterns learned during training. Model Training 2 Types of Data - feature: all information about the object - target: What we want to predict about the project Comparison: Rule-Based Systems VS Machine Learning Example: Spam Mail Case 1. Rule-Base System Observing data and create rules to filter spam mail ex) if a mail contains ‘review, promotion, …’ then this mail is a spam -> but spams are keep changing…. it is hard to maintain the code and add new rules… JUST USE MACHINE LEARNING! Case 2. Machine Learning Get Data Define & Calculate features Train and use the model - in this case, use model to classify messages into spam or not spam Process of ML Features: We put t...
Post a Comment
Read more

Quick Look at Numpy

 What is numpy? NumPy is an open source project that enables numerical computing with Python. Numpy is implemented in C, its performance is faster than a Python list. Document Core Features ndarray : N-dimensional Array Object, the basic data type of NumPy. Vectorization : Operations (or Calculations) performed on the entire array without explicit loops. Broadcasting : Enables operations between arrays of different shapes (or sizes) Array Operations and Attributes 1. Array Creation np.array(): Creates an array from a Python list. np.zeros(): An array filled with zeros. np.ones(): An array filled with ones. np.arange(): An array of consecutive numbers. np.linspace(): An array with evenly spaced numbers. np.random: Module for generating random arrays. 2. Array Attributes shape: The array's dimensions/axes (rows, columns). dtype: Data type. ndim: Number of dimensions. size: Total number of elements. 3. Array Indexing and Slicing Basic Indexing: arr[0], arr[1, 2] Slicing: arr[1:3]...
Post a Comment
Read more