Thư viện Python DSA

Category: Python

Cấu trúc dữ liệu và thuật toán (DSA) đóng vai trò là xương sống cho việc giải quyết vấn đề hiệu quả và phát triển phần mềm. Python, được biết đến với sự đơn giản và tính linh hoạt, cung cấp rất nhiều thư viện và gói giúp triển khai nhiều khái niệm DSA khác nhau. Trong bài viết này, chúng ta sẽ đi sâu vào một số thư viện Python thiết yếu cho DSA, bao gồm mảng, danh sách liên kết, hàng đợi, bản đồ băm, đống, cây và các thuật toán chuyên biệt như Bisect, Interval Trees và Trie Trees.

Mục lục

  • Mảng trong Python

  • Danh sách liên kết trong Python

  • Hàng đợi trong Python

  • Bản đồ băm trong Python

  • Đống trong Python

  • Cây trong Python

  • Thuật toán chia đôi trong Python

  • Cây khoảng trong Python

  • Trie Tree trong Python

Gói hoặc thư viện để triển khai mảng trong Python

Mảng trong Python có thể được tạo bằng cách nhập mô-đun mảng.  array( data_type ,  value_list )  được sử dụng để tạo một mảng với kiểu dữ liệu và danh sách giá trị được chỉ định trong các đối số của nó. 

Gói hoặc Thư viện để triển khai Mảng trong Python

' Thư viện mảng ' trong Python được sử dụng để triển khai Mảng trong Python

'Mảng mô-đun' trong Python là gì?

Mô-đun mảng trong Python định nghĩa một kiểu đối tượng có thể biểu diễn một cách ngắn gọn một mảng các giá trị cơ bản: ký tự, số nguyên và số dấu phẩy động.

Các phương pháp quan trọng trong thư viện mảng

  • mảng.itemssize()

  • mảng.buffer_info()

  • mảng.count(x)

  • array.extend(có thể lặp lại)

Cú pháp sử dụng Thư viện mảng trong Python:

# Nhập mô-đun mảng
import array as <module variable>
# Tạo một mảng trong Python bằng cách sử dụng Mô-đun Mảng
<array variable> = <module variable>.array('<data type of elements>', <list of elements of specified type>)

Ví dụ sử dụng Thư viện mảng trong Python

import array

# Tạo một mảng số nguyên
int_array = array.array('i', [1, 2, 3, 4, 5])

# Truy cập các phần tử
print(int_array[0])

Đầu ra:

1

Gói hoặc thư viện để triển khai danh sách liên kết trong Python

Danh sách liên kết bao gồm một chuỗi các phần tử được gọi là các nút, trong đó mỗi nút chứa một số dữ liệu và một tham chiếu (hoặc con trỏ) đến nút tiếp theo trong chuỗi. Nút cuối cùng thường trỏ đến null để chỉ ra kết thúc của danh sách.

Gói hoặc Thư viện để triển khai Mảng trong Python

Thư viện ' collections.deque ' trong Python được sử dụng để triển khai Danh sách liên kết trong Python.

'Deque module' trong Python là gì?

Trong Python, mô-đun collections cung cấp một lớp deque đa năng, viết tắt của "double-ended queue". Mặc dù không được đặt tên cụ thể là "danh sách liên kết đôi", nhưng về mặt nội bộ, nó sử dụng cấu trúc danh sách liên kết đôi để cung cấp các hoạt động chèn và xóa hiệu quả ở cả hai đầu của hàng đợi.

Các phương pháp quan trọng trong thư viện deque

  • append(ele): Thêm ele vào bên phải của deque

  • appendleft(ele): Thêm ele vào phía bên trái của deque.

  • clear(): Xóa tất cả các phần tử khỏi deque, giữ lại độ dài bằng 0.

  • copy(): Tạo một bản sao nông của deque.

  • count(ele): Đếm số lượng phần tử deque bằng x.

  • extend(): Mở rộng phía bên phải của deque bằng cách thêm các phần tử từ đối số có thể lặp lại.

  • extendleft(): Mở rộng phần bên trái của deque bằng cách thêm các phần tử từ iterable.

  • index(): Trả về vị trí của x trong deque. Trả về kết quả khớp đầu tiên.

  • insert(): Chèn x vào deque tại vị trí i.

  • pop(): Xóa và trả về một phần tử ở phía bên phải của deque.

  • popleft(): Xóa và trả về một phần tử ở phía bên trái của deque.

  • remove(): Xóa giá trị xuất hiện đầu tiên.

  • reverse(): Đảo ngược các phần tử của deque.

  • rotate(): Xoay deque n bước sang phải.

Ví dụ sử dụng Thư viện Deque trong Python

from collections import deque

# Tạo một deque (hàng đợi hai đầu)
my_queue = deque()

# Thêm phần tử vào hàng đợi
my_queue.append(1)       # Thêm vào cuối bên phải
my_queue.appendleft(2)   # Thêm vào đầu bên trái

# Loại bỏ phần tử khỏi hàng đợi
element = my_queue.pop()      # Xóa và trả về phần tử ở cuối bên phải
element = my_queue.popleft()  # Xóa và trả về phần tử ở đầu bên trái

# Các phương thức khác có sẵn trong deque bao gồm: extend, extendleft, rotate, v.v.

Gói hoặc thư viện để triển khai hàng đợi trong Python

Trong hàng đợi, các phần tử được thêm vào (hoạt động enqueue) ở phía sau (còn gọi là "đuôi") và được xóa khỏi phía trước (còn gọi là "đầu") (hoạt động dequeue). Điều này đảm bảo rằng các phần tử cũ nhất được xử lý trước, trong khi các phần tử mới hơn được thêm vào cuối hàng đợi.

Gói hoặc thư viện để triển khai Hash Map trong Python

Thư viện ' queue.Queue ' trong Python được sử dụng để triển khai Queue trong Python.

'Mô-đun hàng đợi' trong Python là gì?

Trong Python, mô-đun hàng đợi cung cấp nhiều lớp khác nhau để triển khai hàng đợi đa nhà sản xuất, đa người tiêu dùng. Các lớp này được thiết kế để sử dụng trong lập trình đa luồng và đặc biệt hữu ích cho việc giao tiếp giữa các luồng một cách an toàn.

Các phương pháp quan trọng trong thư viện Counter

  • Queue.qsize(): Trả về kích thước gần đúng của hàng đợi.

  • Queue.empty(): Trả về True nếu hàng đợi trống, ngược lại trả về False.

  • Queue.full(): Trả về True nếu hàng đợi đã đầy, nếu không thì trả về False.

  • Queue.put(): Đưa phần tử vào hàng đợi.

  • Queue.get(): Xóa và trả về một mục khỏi hàng đợi.

Ví dụ sử dụng Thư viện hàng đợi trong Python

from queue import Queue

# Tạo một hàng đợi
my_queue = Queue()

# Thêm phần tử vào hàng đợi
my_queue.put(1)
my_queue.put(2)
my_queue.put(3)

# Loại bỏ phần tử khỏi hàng đợi
# Loại bỏ và trả về phần tử được thêm vào đầu tiên (FIFO - vào trước ra trước)
element = my_queue.get()  
print(element) 

# Kiểm tra xem hàng đợi có rỗng hay không
print(my_queue.empty())  

# Lấy kích thước (số phần tử) của hàng đợi
print(my_queue.qsize())  

# Các phương thức khác có sẵn trong Queue bao gồm: empty,
# qsize, full, task_done, join, v.v.

Đầu ra:

1 
False 
2

Gói hoặc thư viện để triển khai Hash Map trong Python

Bản đồ băm, còn được gọi là bảng băm, là một cấu trúc dữ liệu lưu trữ các cặp khóa-giá trị. Nó cung cấp các hoạt động chèn, xóa và tra cứu hiệu quả. Bản đồ băm hoạt động bằng cách sử dụng hàm băm để ánh xạ khóa thành chỉ mục trong một mảng.

Gói hoặc Thư viện để triển khai Hash Map trong Python

Thư viện ' collections.Counter ' trong Python được sử dụng để triển khai Hash Map trong Python.

'Counter Module' trong Python là gì?

Bộ đếm trong mô-đun bộ sưu tập của Python là một từ điển chuyên dụng được thiết kế để đếm các đối tượng có thể băm. Nó đặc biệt hữu ích để đếm số lần xuất hiện của các phần tử trong một bộ sưu tập (ví dụ: danh sách hoặc chuỗi). Lớp Bộ đếm cung cấp các phương thức để đếm các phần tử một cách hiệu quả và thực hiện các phép toán như cộng, trừ, giao và hợp của các số đếm.

Các phương pháp quan trọng trong thư viện Counter

Chắc chắn rồi! Sau đây là một số phương thức chính được cung cấp bởi các đối tượng Counter trong mô-đun collections của Python, cùng với giải thích cho từng phương thức:

  1. Counter.elements() : Trả về một trình lặp qua các phần tử lặp lại từng phần tử nhiều lần bằng số đếm của nó. Các phần tử được trả về theo thứ tự tùy ý.

  2. Counter.most_common([n]) : Trả về danh sách n phần tử phổ biến nhất và số lượng của chúng từ phổ biến nhất đến ít nhất. Nếu n bị bỏ qua hoặc None, trả về tất cả các phần tử trong bộ đếm.

  3. Counter.subtract([iterable-or-mapping]) : Các phần tử được trừ khỏi một iterable hoặc khỏi một ánh xạ khác (hoặc bộ đếm).

  4. Counter.total(): Tính tổng các số đếm.

  5. Counter.update([iterable-or-mapping]) : Các phần tử được đếm từ một iterable hoặc được thêm vào từ một ánh xạ khác (hoặc bộ đếm).

  6. Counter.fromkeys(iterable, value) : Phương thức lớp tạo đối tượng Counter mới từ một đối tượng có thể lặp lại và khởi tạo số lượng của mỗi phần tử thành giá trị đã chỉ định.

Ví dụ sử dụng Thư viện Counter trong Python

from collections import Counter

# Tạo một đối tượng Counter từ danh sách
my_list = ['apple', 'banana', 'apple', 'orange', 'apple', 'banana']
my_counter = Counter(my_list)

print(my_counter)

Đầu ra:

Counter({'apple': 3, 'banana': 2, 'orange': 1})

Thư viện hiệu quả để quản lý từ điển

Ngoài ra còn có collections.ChainMap, collections.defaultdict và collections.OrderedDict Method bên trong thư viện bộ sưu tập. Ở đây, bản thân Counter không sử dụng nó, nhưng bạn có thể sử dụng chúng cùng nhau trong một số trường hợp nhất định, tùy thuộc vào yêu cầu cụ thể của bạn.

'Thư viện ChainMap' trong Python là gì?

ChainMap là một lớp trong mô-đun collections của Python cung cấp khả năng liên kết nhiều ánh xạ với nhau để tạo thành một chế độ xem duy nhất. Nó cho phép bạn tìm kiếm nhiều từ điển như thể chúng là một.

# Chương trình Python để chứng minh ChainMap
from collections import ChainMap 
    
d1 = {'a': 1, 'b': 2} 
d2 = {'c': 3, 'd': 4} 
d3 = {'e': 5, 'f': 6} 
    
# Định nghĩa chainmap
c = ChainMap(d1, d2, d3)

'Thư viện defaultdict' trong Python là gì?

defaultdict là một lớp tiện dụng khác được cung cấp bởi mô-đun collections trong Python. Đây là lớp con của lớp dict tích hợp sẵn và cung cấp một cách thuận tiện để tạo từ điển với các giá trị mặc định cho các khóa chưa được thiết lập rõ ràng.

from collections import defaultdict
# Định nghĩa defaultdict với giá trị mặc định là 0
my_defaultdict = defaultdict(int)

'Thư viện OrderedDict' trong Python là gì?

OrderedDict là một lớp con từ điển được cung cấp bởi mô-đun collections trong Python. Nó tương tự như lớp dict tích hợp nhưng có một điểm khác biệt chính: nó duy trì thứ tự chèn các khóa của nó.

from collections import OrderedDict
my_ordered_dict = OrderedDict()

Gói hoặc thư viện để triển khai Heap trong Python

Heap là một cấu trúc dữ liệu dạng cây chuyên biệt đáp ứng được tính chất heap. Heap thường được triển khai dưới dạng cây nhị phân, cụ thể là min-heap nhị phân hoặc max-heap nhị phân.

Gói hoặc thư viện để triển khai Hash Map trong Python

Thư viện ' heapq ' trong Python được sử dụng để triển khai Queue trong Python.

'Mô-đun heapq' trong Python là gì?

Mô-đun heapq trong Python cung cấp một tập hợp các thuật toán dựa trên heap, cụ thể là các hàm để triển khai heap như các danh sách thông thường và thực hiện các hoạt động heap một cách hiệu quả. Mặc dù được đặt tên là "heapq", nhưng nó không cung cấp một lớp cấu trúc dữ liệu heap riêng biệt. Thay vào đó, nó cung cấp các hàm để thao tác các danh sách Python thông thường như các heap.

Các phương pháp quan trọng trong thư viện Counter

Mô-đun heapq trong Python cung cấp các hàm thay vì các phương thức cho các hoạt động heap. Sau đây là các hàm chính có trong mô-đun heapq:

  • heapify(heap): Hàm này chuyển đổi một danh sách thành một heap theo thời gian tuyến tính.

  • heappush(heap, item): Hàm này thêm mục vào heap trong khi vẫn duy trì thuộc tính heap. Nó chèn mục vào vị trí thích hợp trong heap.

  • heappop(heap): Hàm này xóa và trả về phần tử nhỏ nhất trong heap.

  • heappushpop(heap, item): Đẩy mục vào heap rồi pop và trả về phần tử nhỏ nhất từ ​​heap.

  • heapreplace(heap, item): Hàm này trước tiên sẽ bật lên và trả về phần tử nhỏ nhất từ ​​heap trước khi đẩy mục mới vào heap.

  • merge(iterables): Hàm này hợp nhất nhiều đầu vào đã sắp xếp (iterables) thành một đầu ra đã sắp xếp duy nhất (một trình lặp).

  • nlargest(n, iterable): Hàm này trả về n phần tử lớn nhất từ ​​iterable, được sắp xếp theo thứ tự giảm dần.

  • nsmallest(n, iterable): Hàm này trả về n phần tử nhỏ nhất từ ​​iterable, được sắp xếp theo thứ tự tăng dần.

Ví dụ sử dụng Thư viện Heapq trong Python

# nhập "heapq" để triển khai hàng đợi heap
import heapq

# khởi tạo danh sách
li = [5, 7, 9, 1, 3]

# sử dụng heapify để chuyển danh sách thành heap
heapq.heapify(li)

# in ra heap đã được tạo
print("Heap được tạo là:", list(li))

Đầu ra:

The created heap is :  [1, 3, 9, 7, 5]

Gói để triển khai Tree trong Python

Cây là một cấu trúc dữ liệu phân cấp bao gồm các nút được kết nối bằng các cạnh. Đây là một cấu trúc dữ liệu được sử dụng rộng rãi trong khoa học máy tính để tổ chức dữ liệu theo cách phân cấp.

Gói hoặc thư viện để triển khai Tree trong Python

Thư viện 'treelib' trong Python được sử dụng để triển khai Queue trong Python.

'Mô-đun treelib' trong Python là gì?

Đây treelib là thư viện Python cung cấp chức năng làm việc với cấu trúc cây. Nó cho phép bạn tạo, thao tác, duyệt và trực quan hóa cấu trúc dữ liệu cây một cách hiệu quả.

Các phương pháp quan trọng trong thư viện bisect

  • create_node(tag, node_id=None, parent=None) : Tạo một nút mới với thẻ được chỉ định và dữ liệu tùy chọn. Tùy chọn chỉ định mã định danh nút (node_id) và nút cha (parent).

  • remove_node(node_id) : Xóa nút có mã định danh được chỉ định khỏi cây.

  • get_node(node_id) : Truy xuất nút có mã định danh được chỉ định từ cây.

  • update_node(node_id, tag=None, data=None) : Cập nhật thẻ và/hoặc dữ liệu của nút bằng mã định danh được chỉ định.

  • contains(node_id) : Kiểm tra xem cây có chứa nút có mã định danh được chỉ định hay không.

  • parent(node_id) : Trả về mã định danh nút cha của nút có mã định danh được chỉ định.

  • children(node_id) : Trả về danh sách các định danh của các nút con của nút có định danh được chỉ định.

  • depth(node_id) : Tính toán độ sâu của nút có mã định danh được chỉ định trong cây.

  • size(node_id=None): Tính toán kích thước (số nút) của cây con có gốc tại nút có định danh được chỉ định. Nếu không có định danh nào được cung cấp, tính toán kích thước của toàn bộ cây.

  • height(node_id=None) : Tính toán chiều cao (độ sâu tối đa) của cây con có gốc tại nút có định danh được chỉ định. Nếu không có định danh nào được cung cấp, tính toán chiều cao của toàn bộ cây.

  • show(line_type="ascii"): In ra biểu diễn dạng văn bản của cây

Ví dụ sử dụng Thư viện Bisect trong Python

from treelib import Node, Tree

# Tạo một cây nhị phân mới
tree = Tree()

# Thêm các nút vào cây
tree.create_node("Root", "root")  # Tạo nút gốc
tree.create_node("Left Child", "left", parent="root")  # Tạo nút con bên trái
tree.create_node("Right Child", "right", parent="root")  # Tạo nút con bên phải

# Thêm các nút vào nhánh con trái
tree.create_node("Left Grandchild", "left_grand", parent="left")  # Tạo cháu trái
tree.create_node("Right Grandchild", "right_grand", parent="left")  # Tạo cháu phải

# In ra cấu trúc của cây
print("Cấu trúc cây:")
tree.show()

# Duyệt cây (duyệt theo thứ tự trước - pre-order)
print("\nDuyệt cây theo pre-order:")
for node in tree.all_nodes():
    print(node.tag)

# Trực quan hóa cây bằng ký tự ASCII
tree.show(line_type="ascii-em")

# Trực quan hóa cây bằng Graphviz (cần cài đặt Graphviz)
# tree.show()

Đầu ra:

Tree structure:
root
├── left
│   ├── left_grand
│   └── right_grand
└── right
Pre-order traversal:
root
left
left_grand
right_grand
right
  root
|-- left
|   |-- left_grand
|   +-- right_grand
+-- right

Thư viện để triển khai thuật toán Bisect trong Python

Thuật toán bisect, còn được gọi là tìm kiếm nhị phân, là một kỹ thuật được sử dụng để tìm hiệu quả vị trí mà một phần tử nên được chèn vào danh sách đã sắp xếp để duy trì thứ tự đã sắp xếp. Nó được đặt tên theo hàm bisect do mô-đun bisect trong Python cung cấp, mô-đun này triển khai thuật toán này.

Gói hoặc thư viện để triển khai thuật toán Bisect trong Python

Thư viện ' bisect ' trong Python được sử dụng để triển khai Queue trong Python.

'Bisect Module' trong Python là gì?

Mô-đun bisect trong Python cung cấp các hàm để chèn hiệu quả các phần tử vào danh sách đã sắp xếp và tìm điểm chèn cho các phần tử mới trong khi vẫn duy trì thứ tự đã sắp xếp. Nó đặc biệt hữu ích khi xử lý các bộ sưu tập đã sắp xếp và cần duy trì thứ tự của chúng một cách hiệu quả.

Các phương pháp quan trọng trong thư viện bisect

Vì mô-đun bisect hỗ trợ các phương pháp bổ sung, vui lòng đề cập đến tất cả các phương pháp trong các điểm có giải thích

  • bisect(list, num, beg, end): Hàm này trả về vị trí trong danh sách đã được sắp xếp.

  • bisect.bisect_left()

  • bisect.bisect_right()

  • bisect.insort_left()

  • bisect.insort_right()

  • bisect.insort()

Ví dụ sử dụng Thư viện Bisect trong Python

import bisect

# Danh sách đã được sắp xếp
sorted_list = [1, 3, 5, 7, 9]

# Phần tử cần chèn
new_element = 6

# Tìm vị trí chèn bằng cách sử dụng bisect_left
insertion_point = bisect.bisect_left(sorted_list, new_element)

# Chèn phần tử vào danh sách đã sắp xếp tại vị trí phù hợp
sorted_list.insert(insertion_point, new_element)

print("Danh sách sau khi chèn phần tử:", sorted_list)
print("Phần tử mới được chèn tại chỉ số:", insertion_point)

Đầu ra:

Sorted list after insertion: [1, 3, 5, 6, 7, 9]
New element inserted at index: 3

Gói để triển khai cây khoảng thời gian trong Python

Cây khoảng là một cấu trúc dữ liệu được sử dụng để lưu trữ và truy vấn hiệu quả các khoảng hoặc phạm vi. Đây là một loại cây tìm kiếm nhị phân được thiết kế riêng để xử lý các truy vấn khoảng một cách hiệu quả.

Gói hoặc thư viện để triển khai thuật toán Bisect trong Python

Thư viện ' intervaltree ' trong Python được sử dụng để triển khai Queue trong Python.

'Intervaltree Module' trong Python là gì?

Thư viện intervaltree trong Python là một cấu trúc dữ liệu được thiết kế để lưu trữ và truy vấn hiệu quả các khoảng hoặc phạm vi. Thư viện này cung cấp một triển khai của cây khoảng, một loại cây tìm kiếm nhị phân được tối ưu hóa cho các truy vấn khoảng.

Các phương pháp quan trọng trong thư viện intervaltree

Mô-đun intervaltree trong Python cung cấp một số phương pháp để làm việc hiệu quả với cây khoảng thời gian.

  • add(khoảng thời gian): Thêm một khoảng thời gian vào cây khoảng thời gian.

  • remove(interval): Xóa một khoảng khỏi cây khoảng.

  • search(begin): Tìm kiếm các khoảng thời gian chồng lấn với phạm vi nhất định được xác định bởi begin và end (bao gồm).

  • overlap(begin): Biệt danh cho search(). Tìm kiếm các khoảng chồng chéo với phạm vi nhất định được xác định bởi begin và end.

  • at(begin): Tìm kiếm các khoảng chứa điểm bắt đầu được chỉ định. Trả về một tập hợp các khoảng chứa điểm.

  • clear(): Xóa tất cả các khoảng thời gian khỏi cây khoảng thời gian, làm cho nó trở nên trống rỗng.

  • copy(): Tạo một bản sao nông của cây khoảng, bao gồm tất cả các khoảng.

  • discard(interval): Xóa một khoảng khỏi cây khoảng nếu nó tồn tại, tương tự như phương thức remove().

  • items(): Trả về một trình tạo tạo ra tất cả các khoảng thời gian được lưu trữ trong cây khoảng thời gian.

  • size(): Trả về số khoảng thời gian được lưu trữ trong cây khoảng thời gian.

  • empty(): Trả về True nếu cây khoảng trống, nếu không thì trả về False.

Ví dụ sử dụng Thư viện Intervaltree trong Python

from intervaltree import IntervalTree, Interval

# Tạo một cây đoạn (interval tree)
tree = IntervalTree()

# Thêm các đoạn vào cây
tree.add(Interval(1, 5))
tree.add(Interval(3, 8))
tree.add(Interval(6, 10))
tree.add(Interval(12, 15))

# Truy vấn các đoạn giao nhau với một khoảng cho trước
query_range = (4, 7)
result_intervals = tree.search(*query_range)

print("Các đoạn giao nhau với khoảng truy vấn:", result_intervals)

# Duyệt qua các đoạn kết quả và in ra điểm bắt đầu và kết thúc của chúng
print("Điểm bắt đầu và kết thúc của các đoạn giao nhau:")
for interval in result_intervals:
    print("Bắt đầu:", interval.begin, "Kết thúc:", interval.end)

Đầu ra:

Intervals that overlap with the query range: {Interval(1, 5), Interval(3, 8), Interval(6, 10)}
Start and end points of the overlapping intervals:
Start: 1 End: 5
Start: 3 End: 8
Start: 6 End: 10

Gói để triển khai Trie Tree trong Python

Trie, còn được gọi là cây tiền tố hoặc cây kỹ thuật số, là một cấu trúc dữ liệu dạng cây được sử dụng để lưu trữ một tập hợp động các chuỗi trong đó các khóa thường là các chuỗi. Mỗi nút trong Trie biểu diễn một ký tự duy nhất của một chuỗi và đường dẫn từ gốc đến một nút cụ thể biểu diễn tiền tố của một hoặc nhiều chuỗi.

Gói hoặc thư viện để triển khai Trie trong Python

Thư viện ' trie ' trong Python được sử dụng để triển khai Queue trong Python.

'Intervaltree Module' trong Python là gì?

Thư viện intervaltree trong Python là một cấu trúc dữ liệu được thiết kế để lưu trữ và truy vấn hiệu quả các khoảng hoặc phạm vi. Thư viện này cung cấp một triển khai của cây khoảng, một loại cây tìm kiếm nhị phân được tối ưu hóa cho các truy vấn khoảng.

Các phương pháp quan trọng trong thư viện intervaltree

  • Trie() : Phương thức khởi tạo để tạo một đối tượng Trie mới.

  • insert(str) -> None : Chèn một từ vào trie.

  • search(str) : Tìm kiếm một từ trong trie. Trả về True nếu tìm thấy từ đó, nếu không thì trả về False.

  • startswith(prefix: str): Kiểm tra xem có từ nào trong trie bắt đầu bằng tiền tố đã cho không. Trả về True nếu một từ bắt đầu bằng tiền tố, nếu không thì trả về False.

  • delete(word: str): Xóa một từ khỏi trie.

  • words(tiền tố: str = ''): Trả về danh sách các từ trong trie bắt đầu bằng tiền tố đã cho.

Ví dụ sử dụng Thư viện Trie trong Python

from trie import Trie

# Tạo một đối tượng Trie mới
trie = Trie()

# Chèn một số từ vào trie
trie.insert(&quot;apple&quot;)
trie.insert(&quot;banana&quot;)
trie.insert(&quot;app&quot;)
trie.insert(&quot;bat&quot;)
trie.insert(&quot;ball&quot;)

# Tìm kiếm các từ trong trie
print(&quot;Search Results:&quot;)
print(&quot;Does 'apple' exist?&quot;, trie.search(&quot;apple&quot;))  # Đầu ra: True
print(&quot;Does 'app' exist?&quot;, trie.search(&quot;app&quot;))      # Đầu ra: True
print(&quot;Does 'orange' exist?&quot;, trie.search(&quot;orange&quot;))  # Đầu ra: False

# Kiểm tra xem có từ nào bắt đầu bằng tiền tố đã cho không
print(&quot;\nStartsWith Results:&quot;)
print(&quot;Does any word start with 'ap'?&quot;, trie.startswith(&quot;ap&quot;))  # Đầu ra: True
print(&quot;Does any word start with 'ora'?&quot;, trie.startswith(&quot;ora&quot;))  # Đầu ra: False

# Nhận gợi ý tự động hoàn thành cho một tiền tố nhất định
print(&quot;\nAutocomplete Suggestions for 'ba':&quot;, trie.autocomplete(&quot;ba&quot;))  # Đầu ra: ['ball', 'banana', 'bat']

# Xóa một từ khỏi trie
trie.delete(&quot;apple&quot;)
print(&quot;\nAfter deleting 'apple':&quot;, trie.words())  # Đầu ra: ['app', 'ball', 'banana', 'bat']

# Đếm tổng số từ trong trie
print(&quot;\nTotal Number of Words:&quot;, trie.count_words())  # Đầu ra: 4

# Đếm số lượng từ có tiền tố cho trước
print(&quot;Number of words with prefix 'ba':&quot;, trie.count_prefixes(&quot;ba&quot;))  # Đầu ra: 3

Published on Jun 23, 2025