Hướng dẫn what is binary search tree in python - cây tìm kiếm nhị phân trong python là gì

Cây tìm kiếm nhị phân là gì? 🔗 🔗

Cây tìm kiếm nhị phân, hoặc viết tắt là một cây trong đó mỗi nút có giá trị lớn hơn tất cả các nút con trái của nó và ít hơn tất cả các nút con phải của nó. Đọc tiếp để thực hiện một cây tìm kiếm nhị phân trong Python từ đầu!

Tại sao tôi sẽ sử dụng một cây tìm kiếm nhị phân? 🔗 🔗

Cây nhị phân rất hữu ích để lưu trữ dữ liệu theo cách có tổ chức để có thể nhanh chóng lấy, chèn, cập nhật và xóa. Sự sắp xếp của các nút này cho phép mỗi so sánh để bỏ qua khoảng một nửa phần còn lại của cây, do đó, mỗi hoạt động nói chung là sét nhanh.

Nói chính xác, các cây tìm kiếm nhị phân cung cấp độ phức tạp trung bình lớn của

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

1 cho các hoạt động tìm kiếm, chèn, cập nhật và xóa.

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

2 nhanh hơn nhiều so với thời gian

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

3 tuyến tính cần thiết để tìm các phần tử trong một mảng chưa được phân loại. Nhiều cơ sở dữ liệu sản xuất phổ biến như PostgreSQL và MySQL sử dụng cây nhị phân dưới mui xe để tăng tốc các hoạt động của CRUD.

Ưu điểm của một BST 🔗 🔗

• Khi cân bằng, một BST cung cấp các lần chèn, xóa và tra cứu

    10                                10
   /   \        Insert 5            /    \
   2    60    --------->           2     60
  /  \                            /  \
  1   3                           1   3
                                       \
                                        5
  

  1 nhanh.
• Cây tìm kiếm nhị phân rất đơn giản để thực hiện. Một BST thông thường, không giống như một cây màu đen màu đỏ cân bằng, đòi hỏi rất ít mã để chạy.

Nhược điểm của một BST 🔗 🔗

• Chậm cho một tìm kiếm vũ phu. Nếu bạn cần lặp lại trên mỗi nút, bạn có thể có nhiều thành công hơn với một mảng.
• Khi cây trở nên không cân bằng, tất cả các hoạt động

    10                                10
   /   \        Insert 5            /    \
   2    60    --------->           2     60
  /  \                            /  \
  1   3                           1   3
                                       \
                                        5
  

  1 nhanh chóng xuống cấp xuống

    10                                10
   /   \        Insert 5            /    \
   2    60    --------->           2     60
  /  \                            /  \
  1   3                           1   3
                                       \
                                        5
  

  3.
• Vì các con trỏ đến toàn bộ các đối tượng thường có liên quan, một BST có thể yêu cầu khá nhiều bộ nhớ hơn một mảng, mặc dù điều này phụ thuộc vào việc thực hiện.

Nhận một công việc back-end mà không cần chi 10 nghìn đô la cho một bootcamp

• Tìm hiểu Python, JavaScript và GO
• Xây dựng các dự án chuyên nghiệp mà bạn cần để tìm được công việc đầu tiên của mình
• Dành khoảng 6 tháng (khi hoàn thành bán thời gian)
• Giá thấp tới $ 24/tháng*
• Không mạo hiểm. Hủy bất cứ lúc nào.

Thực hiện một cây B trong Python 🔗 🔗

Bước 1 - Lớp BSTNode 🔗 🔗

Việc triển khai của chúng tôi đã giành chiến thắng sử dụng một lớp

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

7, nhưng thay vào đó chỉ là một lớp

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

8. Cây nhị phân thực sự chỉ là một con trỏ tới một nút gốc lần lượt kết nối với từng nút con, vì vậy chúng tôi sẽ chạy với ý tưởng đó.

Đầu tiên, chúng tôi tạo một hàm tạo:

class BSTNode:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val

Chúng tôi sẽ cho phép một giá trị, cũng sẽ đóng vai trò là chìa khóa, được cung cấp. Nếu một người không được cung cấp, chúng tôi sẽ đặt nó thành

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

9. Chúng tôi cũng sẽ khởi tạo cả hai đứa trẻ của nút mới thành

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

9.

Bước 2 - Chèn 🔗 🔗

Chúng ta cần một cách để chèn dữ liệu mới vào cây. Chèn một nút mới nên nối nó như một nút lá ở vị trí thích hợp.

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

Phương pháp chèn như sau:

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

Nếu nút không có giá trị, chúng ta chỉ có thể đặt giá trị đã cho và trả về. Nếu chúng ta cố gắng chèn một giá trị cũng tồn tại, chúng ta cũng có thể quay lại vì điều này có thể được coi là một không có op. Nếu giá trị đã cho nhỏ hơn giá trị nút của chúng tôi và chúng tôi đã có con trái thì chúng tôi gọi đệ quy

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

1 trên đứa con trái của chúng tôi. Nếu chúng tôi không có một đứa con trái thì chúng tôi chỉ cần làm cho giá trị đã cho là đứa con bên trái mới của chúng tôi. Chúng ta có thể làm như vậy (nhưng đảo ngược) cho phía bên phải của chúng ta.

Bước 3 - Nhận tối thiểu và nhận tối đa 🔗

def get_min(self):
    current = self
    while current.left is not None:
        current = current.left
    return current.val

def get_max(self):
    current = self
    while current.right is not None:
        current = current.right
    return current.val

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

2 và

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

3 là các chức năng trợ giúp hữu ích và chúng rất dễ viết! Chúng là các hàm đệ quy đơn giản đi qua các cạnh của cây để tìm các giá trị nhỏ nhất hoặc lớn nhất được lưu trữ trong đó.

Bước 4 - Xóa 🔗 🔗

def delete(self, val):
    if self == None:
        return self
    if val < self.val:
        self.left = self.left.delete(val)
        return self
    if val > self.val:
        self.right = self.right.delete(val)
        return self
    if self.right == None:
        return self.left
    if self.left == None:
        return self.right
    min_larger_node = self.right
    while min_larger_node.left:
        min_larger_node = min_larger_node.left
    self.val = min_larger_node.val
    self.right = self.right.delete(min_larger_node.val)
    return selfdef delete(self, val):
    if self == None:
        return self
    if val < self.val:
        if self.left:
            self.left = self.left.delete(val)
        return self
    if val > self.val:
        if self.right:
            self.right = self.right.delete(val)
        return self
    if self.right == None:
        return self.left
    if self.left == None:
        return self.right
    min_larger_node = self.right
    while min_larger_node.left:
        min_larger_node = min_larger_node.left
    self.val = min_larger_node.val
    self.right = self.right.delete(min_larger_node.val)
    return selfdef delete(self, val):
    if self == None:
        return self
    if val < self.val:
        self.left = self.left.delete(val)
        return self
    if val > self.val:
        self.right = self.right.delete(val)
        return self
    if self.right == None:
        return self.left
    if self.left == None:
        return self.right
    min_larger_node = self.right
    while min_larger_node.left:
        min_larger_node = min_larger_node.left
    self.val = min_larger_node.val
    self.right = self.right.delete(min_larger_node.val)
    return self

Hoạt động xóa là một trong những hoạt động phức tạp hơn. Nó cũng là một chức năng đệ quy, nhưng nó cũng trả về trạng thái mới của nút đã cho sau khi thực hiện thao tác xóa. Điều này cho phép cha mẹ có con đã bị xóa để đặt đúng cách

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

4 hoặc

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

5 thành viên dữ liệu thành

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

9.

Bước 5 - tồn tại 🔗 🔗

Hàm tồn tại là một hàm đệ quy đơn giản khác trả về

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

7 hoặc

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

8 tùy thuộc vào việc một giá trị nhất định đã tồn tại trong cây.

def exists(self, val):
    if val == self.val:
        return True

    if val < self.val:
        if self.left == None:
            return False
        return self.left.exists(val)

    if self.right == None:
        return False
    return self.right.exists(val)

Bước 6 - Inorder 🔗 🔗

Nó rất hữu ích để có thể in ra cây theo định dạng có thể đọc được. Phương pháp

def insert(self, val):
    if not self.val:
        self.val = val
        return

    if self.val == val:
        return

    if val < self.val:
        if self.left:
            self.left.insert(val)
            return
        self.left = BSTNode(val)
        return

    if self.right:
        self.right.insert(val)
        return
    self.right = BSTNode(val)

9 in các giá trị trong cây theo thứ tự các khóa của chúng.

def inorder(self, vals):
    if self.left is not None:
        self.left.inorder(vals)
    if self.val is not None:
        vals.append(self.val)
    if self.right is not None:
        self.right.inorder(vals)
    return vals

Bước 7 - Đặt hàng trước 🔗 🔗

def preorder(self, vals):
    if self.val is not None:
        vals.append(self.val)
    if self.left is not None:
        self.left.preorder(vals)
    if self.right is not None:
        self.right.preorder(vals)
    return vals

Bước 8 - Bưu điện 🔗 🔗

def postorder(self, vals):
    if self.left is not None:
        self.left.postorder(vals)
    if self.right is not None:
        self.right.postorder(vals)
    if self.val is not None:
        vals.append(self.val)
    return vals

Sử dụng BST 🔗 🔗

def main():
    nums = [12, 6, 18, 19, 21, 11, 3, 5, 4, 24, 18]
    bst = BSTNode()
    for num in nums:
        bst.insert(num)
    print("preorder:")
    print(bst.preorder([]))
    print("#")

    print("postorder:")
    print(bst.postorder([]))
    print("#")

    print("inorder:")
    print(bst.inorder([]))
    print("#")

    nums = [2, 6, 20]
    print("deleting " + str(nums))
    for num in nums:
        bst.delete(num)
    print("#")

    print("4 exists:")
    print(bst.exists(4))
    print("2 exists:")
    print(bst.exists(2))
    print("12 exists:")
    print(bst.exists(12))
    print("18 exists:")
    print(bst.exists(18))

Cây tìm kiếm nhị phân đầy đủ trong Python 🔗 🔗

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

0

Bạn sẽ sử dụng cây tìm kiếm nhị phân ở đâu trong cuộc sống thực? 🔗 🔗

Có nhiều ứng dụng của các cây tìm kiếm nhị phân trong cuộc sống thực và một trong những trường hợp sử dụng phổ biến nhất là trong việc lưu trữ các chỉ mục và khóa trong cơ sở dữ liệu.

Ví dụ: trong MySQL hoặc PostgreSQL Khi bạn tạo một cột khóa chính, những gì bạn thực sự đang làm là tạo một cây nhị phân trong đó các phím là các giá trị của cột và các nút đó trỏ đến các hàng cơ sở dữ liệu. Điều này cho phép ứng dụng dễ dàng tìm kiếm các hàng cơ sở dữ liệu bằng cách cung cấp khóa. Ví dụ: nhận được bản ghi người dùng bằng khóa chính

def get_min(self):
    current = self
    while current.left is not None:
        current = current.left
    return current.val

def get_max(self):
    current = self
    while current.right is not None:
        current = current.right
    return current.val

0.

Có nhiều ứng dụng của các cây tìm kiếm nhị phân trong cuộc sống thực và một trong những trường hợp sử dụng phổ biến nhất là lưu trữ các chỉ mục và khóa trong cơ sở dữ liệu.

Ví dụ: khi bạn tạo một cột khóa chính trong MySQL hoặc PostgreSQL, bạn tạo một cây nhị phân trong đó các phím là các giá trị của cột và các nút trỏ đến các hàng cơ sở dữ liệu. Điều này cho phép ứng dụng dễ dàng tìm kiếm các hàng cơ sở dữ liệu bằng cách chỉ định khóa, để tìm bản ghi người dùng bằng khóa chính email.

Các ứng dụng phổ biến khác bao gồm:

• Các thuật toán Pathfinding trong trò chơi video (A*) sử dụng BSTS
• Nén tệp bằng cách sử dụng sơ đồ mã hóa Huffman sử dụng cây tìm kiếm nhị phân
• Tính toán kết xuất - Doom (1993) nổi tiếng là trò chơi đầu tiên sử dụng BST
• Trình biên dịch cho các ngôn ngữ mã hóa cấp thấp Parse Syntax bằng cách sử dụng BST
• Hầu như mọi cơ sở dữ liệu đang tồn tại đều sử dụng BSTS để tra cứu khóa

Điều gì khác biệt giữa một cây nhị phân và một danh sách được liên kết? 🔗 🔗

Trong khi các cây nhị phân và danh sách được liên kết cả hai sử dụng con trỏ để theo dõi các nút, cây nhị phân hiệu quả hơn để tìm kiếm. Trên thực tế, các danh sách được liên kết là

  10                                10
 /   \        Insert 5            /    \
 2    60    --------->           2     60
/  \                            /  \
1   3                           1   3
                                     \
                                      5

3 khi được sử dụng để tìm kiếm một yếu tố cụ thể - điều đó khá tệ! Danh sách được liên kết vượt trội khi loại bỏ và chèn các yếu tố nhanh chóng ở giữa danh sách.

Cây tìm kiếm nhị phân là gì?

Làm thế nào một cây tìm kiếm nhị phân được triển khai python?

Cây nhị phân giải thích với ví dụ là gì?

Làm thế nào để tìm kiếm nhị phân trong Python hoạt động?