Thuật toán cây Python

Cây được đại diện bởi một tập hợp các nút được kết nối bởi các cạnh. Chúng được coi là cấu trúc dữ liệu phân cấp và phi tuyến tính, vì dữ liệu trong cây được lưu trữ trên nhiều cấp độ. Cây có những đặc điểm sau

• Nút gốc. mỗi cây có một nút được chỉ định là nút gốc, là nút ở trên cùng của cây và là nút không có bất kỳ nút cha nào
• nút cha. một nút cha là nút trước nó và mọi nút trừ nút gốc đều có một nút cha
• nút con. một nút con là nút sau nó. Tùy thuộc vào loại cây, mỗi nút có thể có số lượng nút con khác nhau

Có những cây nói chung có các thuộc tính được liệt kê ở trên và không có hạn chế nào khác về số lượng nút. Ngoài ra còn có nhiều loại cấu trúc dữ liệu cây với nhiều hạn chế hơn cho các trường hợp sử dụng khác nhau và dưới đây là một số loại thường thấy

1. Cây nhị phân. Cây nhị phân là cây mà mỗi nút có thể có nhiều nhất hai nút con, như nhãn “nhị phân” gợi ý
2. Cây tìm kiếm nhị phân (BST). BST là trường hợp đặc biệt của cây nhị phân trong đó các nút được sắp xếp theo giá trị của chúng. Đối với mỗi nút cha, nút con bên trái có giá trị nhỏ hơn, trong khi nút con bên phải có giá trị lớn hơn. Cấu trúc này giúp tra cứu nhanh và do đó hữu ích cho các thuật toán tìm kiếm và sắp xếp
3. đống. Heap là một cấu trúc dữ liệu cây đặc biệt và có hai loại heap. i) Min Heap là một cấu trúc cây trong đó mỗi nút cha nhỏ hơn hoặc bằng nút con của nó; . Loại cấu trúc dữ liệu này rất hữu ích để triển khai hàng đợi ưu tiên trong đó các mục được ưu tiên theo trọng số. Lưu ý rằng Python có một thư viện tích hợp có tên là heapq với các hàm để thực hiện các thao tác khác nhau trên cấu trúc dữ liệu heap

Sau khi xem xét các loại cấu trúc dữ liệu cây phổ biến, dưới đây là một số ví dụ phổ biến về thuật toán duyệt cây và cách triển khai chúng trong Python

Tìm kiếm theo chiều rộng (BFS)

Tìm kiếm đầu tiên (BFS) là một thuật toán phổ biến được sử dụng để duyệt qua cây tìm kiếm nhị phân (BST) hoặc biểu đồ theo thứ tự có hệ thống. Nó bắt đầu tại nút gốc ở mức 0 và truy cập từng nút một di chuyển ngang từ bên này sang bên kia cho đến khi tìm thấy nút mong muốn hoặc tất cả các nút đã được truy cập. Thuật toán tìm kiếm rộng trước khi đi sâu hơn, do đó có tên là bread-first search

Độ phức tạp về thời gian của BFS là O(n), vì kích thước cây được quyết định bởi độ dài tìm kiếm mục và mỗi nút được truy cập một lần. Dưới đây là triển khai trong Python

def bfs(graph, source):
   """Function to traverse graph/ tree using breadth-first search   Parameters:
   graph (dict): dictionary with node as key and 
                 list of connected nodes as values.
   source (str): source node to start from, usually 
                 the root node of the tree.   Returns:
   bfs_result (list): list of visited nodes in order.
   """
   # Define variables
   bfs_result = []
   queue = []   # Add source node to queue
   queue.append(source)   while queue:
     # Visit node at front of queue
     node = queue.pop(0)     # Check if we have visited this node before
     if node not in bfs_result:
        # Mark node as visited
        bfs_result.append(node)
        # Add all neighbor nodes to queue
        for neighbor in graph.get(node, []):
           queue.append(neighbor)   return bfs_result

Tìm kiếm chuyên sâu

Tìm kiếm theo chiều sâu (DFS) là một biến thể khác của thuật toán duyệt cây, trong đó nó cũng bắt đầu từ nút gốc nhưng di chuyển xuống một nhánh và đi xuống nhánh càng xa càng tốt. Nếu nút mong muốn không nằm trong nhánh đó, nó sẽ quay trở lại và chọn một nhánh khác để đi xuống. Thuật toán thực hiện điều này cho đến khi tìm thấy nút mong muốn hoặc tất cả các nút đã được truy cập. Thuật toán khám phá một nhánh (sâu) trước khi đi đến một nhánh khác, do đó có tên là tìm kiếm theo chiều sâu

Độ phức tạp về thời gian của DFS cũng là O(n) vì những lý do tương tự như BFS. Dưới đây là triển khai trong Python

def dfs(graph, source):
   """Function to traverse graph/ tree using depth-first search   Parameters:
   graph (dict): dictionary with node as key and 
                 list of child nodes as values.
   source (str): source node to start from, usually 
                 the root node of the tree.   Returns:
   dfs_result (list): list of visited nodes in order.
   """
   # Define variables
   dfs_result = []
   queue = []   # Add source node to queue
   queue.append(source)   while queue:
      # Get last item in queue
      node = queue.pop()      # Check if we have visited node before
      if node not in dfs_result:
         dfs_result.append(node)
         # Add neighbors to queue
         for neighbor in graph.get(node, []):
            queue.append(neighbor)   return dfs_result

Phần kết luận

Cây là cấu trúc dữ liệu hữu ích để biểu diễn dữ liệu phân cấp và phi tuyến tính. Các loại cấu trúc dữ liệu cây được sử dụng phổ biến nhất là cây nhị phân (mỗi nút trong cây có nhiều nhất hai nút con), cây tìm kiếm nhị phân (cây nhị phân trong đó các nút được sắp xếp theo giá trị) và đống (cây trong đó các nút cha nhỏ hơn hoặc

Về mặt thuật toán, tìm kiếm dựa trên bánh mì và tìm kiếm theo chiều sâu là các thuật toán duyệt cây quan trọng với nhiều ứng dụng trong thế giới thực, từ tìm đường đi và lập kế hoạch tuyến đường trong hệ thống định vị GPS đến lập lịch trình cho cấu trúc liên kết mạng. Trong bài viết tiếp theo, chúng ta sẽ xem xét một ví dụ đặc biệt về phép duyệt cây được sử dụng để mã hóa thông tin có tên là Mã Huffman

Xem thêm từ loạt Giải thích thuật toán này. #1. đệ quy, #2. sắp xếp, #3. tìm kiếm, #4. thuật toán tham lam, #5. lập trình động, #6. duyệt cây (bài viết hiện tại)

Python có cấu trúc cây không?

Cây thuật toán là gì?

Thuật toán phân loại cây quyết định trong Python là gì?

Làm cách nào để triển khai thuật toán cây quyết định trong Python?