Cây nhị phân DSA
Cây nhị phân
Cây nhị phân là một loại cấu trúc dữ liệu cây trong đó mỗi nút có thể có tối đa hai nút con, một nút con bên trái và một nút con bên phải.
Hạn chế này, một nút có thể có tối đa hai nút con, mang lại cho chúng ta nhiều lợi ích:
- Các thuật toán như duyệt ngang, tìm kiếm, chèn và xóa trở nên dễ hiểu, dễ triển khai và chạy nhanh hơn.
- Việc sắp xếp dữ liệu trong Cây tìm kiếm nhị phân (BST) giúp việc tìm kiếm trở nên rất hiệu quả.
- Việc cân bằng cây sẽ dễ thực hiện hơn với số lượng nút con hạn chế, chẳng hạn như sử dụng Cây nhị phân AVL.
- Cây nhị phân có thể được biểu diễn dưới dạng mảng, làm cho cây có hiệu quả bộ nhớ cao hơn.
Sử dụng hình ảnh động bên dưới để xem Cây nhị phân trông như thế nào và chúng tôi sử dụng những từ nào để mô tả nó.
Nút cha hoặc nút bên trong trong Cây nhị phân là nút có một hoặc hai nút con .
Nút con bên trái là nút con ở bên trái.
Nút con bên phải là nút con ở bên phải.
Chiều cao của cây là số cạnh tối đa tính từ nút gốc đến nút lá.
Cây nhị phân so với mảng và danh sách liên kết
Lợi ích của cây nhị phân so với mảng và danh sách liên kết:
- Mảng rất nhanh khi bạn muốn truy cập trực tiếp vào một phần tử, chẳng hạn như phần tử số 700 trong một mảng gồm 1000 phần tử chẳng hạn. Nhưng việc chèn và xóa các phần tử yêu cầu các phần tử khác phải dịch chuyển trong bộ nhớ để nhường chỗ cho phần tử mới hoặc thay thế các phần tử đã xóa và điều đó rất tốn thời gian.
- Danh sách liên kết rất nhanh khi chèn hoặc xóa các nút, không cần dịch chuyển bộ nhớ, nhưng để truy cập một phần tử bên trong danh sách, danh sách phải được duyệt qua và điều đó cần có thời gian.
- Cây nhị phân , chẳng hạn như Cây tìm kiếm nhị phân và Cây AVL, rất tuyệt vời so với Mảng và Danh sách liên kết vì chúng CẢ HAI nhanh khi truy cập một nút, VÀ nhanh khi xóa hoặc chèn một nút mà không cần thay đổi bộ nhớ.
Chúng ta sẽ xem xét kỹ hơn cách hoạt động của Cây tìm kiếm nhị phân (BST) và Cây AVL trên hai trang tiếp theo, nhưng trước tiên hãy xem cách triển khai Cây nhị phân và cách duyệt qua nó.
Các loại cây nhị phân
Có nhiều biến thể hoặc loại khác nhau của Cây nhị phân đáng để thảo luận để hiểu rõ hơn về cách cấu trúc Cây nhị phân.
Các loại Cây nhị phân khác nhau cũng đáng được đề cập bây giờ vì những từ và khái niệm này sẽ được sử dụng sau trong hướng dẫn.
Dưới đây là những giải thích ngắn gọn về các loại cấu trúc Cây nhị phân khác nhau và bên dưới phần giải thích là các hình vẽ của các loại cấu trúc này để làm cho nó dễ hiểu nhất có thể.
Cây nhị phân cân bằng có chênh lệch tối đa 1 giữa chiều cao cây con bên trái và bên phải của nó đối với mỗi nút trong cây.
Cây nhị phân hoàn chỉnh có tất cả các cấp có đầy đủ các nút, ngoại trừ cấp cuối cùng, cũng có thể đầy hoặc được điền từ trái sang phải. Các thuộc tính của Cây nhị phân hoàn chỉnh có nghĩa là nó cũng được cân bằng.
Cây nhị phân đầy đủ là một loại cây trong đó mỗi nút có 0 hoặc 2 nút con.
Cây nhị phân hoàn hảo có tất cả các nút lá ở cùng một cấp độ, có nghĩa là tất cả các cấp độ đều có đầy đủ các nút và tất cả các nút bên trong đều có hai nút con. Các thuộc tính của Cây nhị phân hoàn hảo có nghĩa là nó cũng đầy đủ, cân bằng và đầy đủ.
Thực hiện cây nhị phân
Hãy triển khai Cây nhị phân này:
Cây nhị phân ở trên có thể được triển khai giống như chúng tôi đã triển khai Danh sách liên kết đơn , ngoại trừ việc thay vì liên kết từng nút với một nút tiếp theo, chúng tôi tạo một cấu trúc trong đó mỗi nút có thể được liên kết với cả nút con trái và phải của nó.
Đây là cách Cây nhị phân có thể được triển khai:
Ví dụ
Trăn:
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# Test
print("root.right.left.data:", root.right.left.data) Chạy ví dụ »Truyền tải cây nhị phân
Đi qua Cây bằng cách truy cập từng nút, từng nút một, được gọi là truyền tải.
Vì Mảng và Danh sách liên kết là các cấu trúc dữ liệu tuyến tính nên chỉ có một cách rõ ràng để duyệt qua các cấu trúc này: bắt đầu từ phần tử hoặc nút đầu tiên và tiếp tục truy cập phần tiếp theo cho đến khi bạn đã truy cập tất cả.
Nhưng vì Cây có thể phân nhánh theo các hướng khác nhau (phi tuyến tính) nên có nhiều cách khác nhau để đi qua Cây.
Có hai loại phương pháp duyệt cây chính:
Tìm kiếm theo chiều rộng đầu tiên (BFS) là khi các nút ở cùng cấp độ được truy cập trước khi chuyển sang cấp độ tiếp theo trong cây. Điều này có nghĩa là cây được khám phá theo hướng nghiêng hơn.
Tìm kiếm theo chiều sâu (DFS) là khi quá trình duyệt di chuyển xuống cây đến tận các nút lá, khám phá từng nhánh cây theo hướng đi xuống.
Có ba loại truyền tải DFS khác nhau:
Ba lần duyệt tìm kiếm theo chiều sâu đầu tiên này được mô tả chi tiết ở các trang tiếp theo.
