Cây tìm kiếm nhị phân Python

Trong bài viết này, chúng ta sẽ tìm hiểu về cây tìm kiếm nhị phân. Chúng ta sẽ nghiên cứu các khái niệm cơ bản đằng sau cây tìm kiếm nhị phân và sau đó triển khai mã. Bạn nên làm quen với các khái niệm về cây nhị phân để đọc bài viết này

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

Cây tìm kiếm nhị phân là cấu trúc dữ liệu cây nhị phân với các thuộc tính bổ sung cùng với các thuộc tính của cây nhị phân. Trong một cây tìm kiếm nhị phân,

• Không có giá trị trùng lặp
• Cây con bên trái của một nút có tất cả các giá trị dữ liệu nhỏ hơn dữ liệu của chính nó. tôi. e. Con trái hoặc con của con trái luôn nhỏ hơn giá trị trong nút hiện tại
• Cây con bên phải của một nút có tất cả các giá trị dữ liệu lớn hơn dữ liệu của chính nó. tôi. e. Con phải hoặc con của con phải của nút hiện tại luôn lớn hơn nút hiện tại

Điều này có thể được quan sát trong ví dụ sau

Triển khai cây tìm kiếm nhị phân trong Python

Để triển khai Cây tìm kiếm nhị phân, chúng tôi sẽ sử dụng cấu trúc nút giống như cấu trúc của cây nhị phân như sau

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None

Bây giờ, để triển khai cây tìm kiếm nhị phân, chúng ta sẽ triển khai các hàm để chèn một giá trị vào cây, tìm kiếm một giá trị trong cây nhị phân, sau đó chúng ta sẽ xem cách tìm các phần tử tối thiểu và tối đa từ cây tìm kiếm nhị phân

Chèn một nút trong Cây tìm kiếm nhị phân

Trong khi chèn một nút vào cây tìm kiếm nhị phân, ba điều kiện có thể phát sinh

1. Cây tìm kiếm nhị phân có thể trống. tôi. e. Bản thân gốc sẽ là một giá trị Không có
2. Giá trị được chèn nhỏ hơn giá trị gốc
3. Giá trị được chèn lớn hơn giá trị gốc

Để thực hiện điều kiện đầu tiên, chúng ta chỉ cần tạo một nút mới và khai báo nó là root. Để thực hiện điều kiện thứ hai và thứ ba, chúng tôi làm theo cách tiếp cận sau

Từ các thuộc tính của cây tìm kiếm nhị phân, chúng ta có thể thấy rằng mỗi cây con tự nó là một cây tìm kiếm nhị phân. Như vậy ta có thể coi mỗi nút là gốc của một cây nhị phân khác

Trong khi chèn một nút mới, nếu giá trị của dữ liệu mới nhỏ hơn giá trị của nút hiện tại, chúng tôi sẽ thêm nó vào con bên trái của cây tìm kiếm nhị phân, nếu không, chúng tôi sẽ thêm nó vào con bên phải

Tiếp tục đệ quy ta sẽ luôn đạt điều kiện đầu tiên rồi khai báo nút mới và thêm nút vào cây tìm kiếm nhị phân

Sau đây là việc thực hiện phương pháp trên

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) a1=root a2=a1.leftChild a3=a1.rightChild a4=a2.leftChild a5=a2.rightChild a6=a3.leftChild a7=a3.rightChild print("Root Node is:") print(a1.data) print("left child of node is:") print(a1.leftChild.data) print("right child of node is:") print(a1.rightChild.data) print("Node is:") print(a2.data) print("left child of node is:") print(a2.leftChild.data) print("right child of node is:") print(a2.rightChild.data) print("Node is:") print(a3.data) print("left child of node is:") print(a3.leftChild.data) print("right child of node is:") print(a3.rightChild.data) print("Node is:") print(a4.data) print("left child of node is:") print(a4.leftChild) print("right child of node is:") print(a4.rightChild) print("Node is:") print(a5.data) print("left child of node is:") print(a5.leftChild) print("right child of node is:") print(a5.rightChild) print("Node is:") print(a6.data) print("left child of node is:") print(a6.leftChild) print("right child of node is:") print(a6.rightChild) print("Node is:") print(a7.data) print("left child of node is:") print(a7.leftChild) print("right child of node is:") print(a7.rightChild)

đầu ra

Root Node is: 15 left child of node is: 10 right child of node is: 25 Node is: 10 left child of node is: 6 right child of node is: 14 Node is: 25 left child of node is: 20 right child of node is: 60 Node is: 6 left child of node is: None right child of node is: None Node is: 14 left child of node is: None right child of node is: None Node is: 20 left child of node is: None right child of node is: None Node is: 60 left child of node is: None right child of node is: None

Trong đầu ra ở trên, chúng ta có thể xác minh mọi thuộc tính của cây tìm kiếm nhị phân trong ví dụ của chúng ta. Ở đây, sau khi khai báo nút gốc, bất kể thứ tự chèn các phần tử ở đó là gì, đầu ra sẽ luôn giống nhau. Hãy thử điều này bằng cách sao chép và dán mã này vào IDE python của riêng bạn

Tìm kiếm một phần tử trong cây tìm kiếm nhị phân

Ở trên chúng ta đã thấy rằng một nút có giá trị nhỏ hơn giá trị của nút hiện tại sẽ luôn nằm trong cây con bên trái của nút hiện tại và một nút có giá trị lớn hơn giá trị của nút hiện tại sẽ luôn nằm trong cây con bên phải . Chúng tôi sẽ sử dụng thuộc tính này để tìm kiếm một phần tử trong cây tìm kiếm nhị phân

1. Nếu nút hiện tại trống, tôi. e. Không, phần tử được tìm kiếm không có trong cây và chúng tôi sẽ trả về Sai
2. Nếu nút hiện tại có giá trị bằng truy vấn tìm kiếm, chúng tôi sẽ trả về True
3. Nếu giá trị cần tìm lớn hơn giá trị của nút hiện tại, chúng tôi sẽ tìm kiếm cây con bên phải của nút hiện tại
4. Nếu giá trị cần tìm nhỏ hơn giá trị của nút hiện tại, chúng tôi sẽ tìm kiếm cây con bên trái của nút hiện tại

Việc thực hiện logic được đưa ra dưới đây

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root def search(root,value): #Condition 1 if root==None: return False #Condition 2 elif root.data==value: return True #Condition 3 elif root.data <value: return search(root.rightChild,value) # Condition 4 else: return search(root.leftChild,value) root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print(search(root,14)) print(search(root,22))

đầu ra

True False

Làm cách nào để tìm phần tử tối đa của Cây tìm kiếm nhị phân?

Từ bất cứ điều gì chúng ta đã thấy cho đến nay, chúng ta biết rằng một phần tử lớn hơn nút hiện tại luôn ở phía bên phải của nó

Khi chúng ta di chuyển đến nút con bên phải của mỗi nút bắt đầu từ gốc cho đến cuối theo cách đệ quy, phần tử lớn nhất sẽ xuất hiện ở cuối

Vì vậy, để tìm phần tử lớn nhất của cây tìm kiếm nhị phân, chúng ta chỉ cần tìm phần tử ngoài cùng bên phải của cây. Đây là việc thực hiện logic này

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root def findLargestElement(root): #check if binary search tree is empty if root==None: return False #check if current node is rightmost node elif root.rightChild==None: return root.data #check right subtree of current node else: return findLargestElement(root.rightChild) root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Largest Element is:") print(findLargestElement(root))

đầu ra

Largest Element is: 60

Làm cách nào để tìm phần tử nhỏ nhất của cây tìm kiếm nhị phân?

Chúng tôi biết rằng một phần tử nhỏ hơn nút hiện tại luôn ở phía bên trái của nó. Khi chúng ta di chuyển đến nút con bên trái của mỗi nút bắt đầu từ gốc cho đến cuối theo cách đệ quy, phần tử nhỏ nhất sẽ xuất hiện trong nút cuối cùng.

Vì vậy, để tìm phần tử nhỏ nhất của cây tìm kiếm nhị phân, chúng ta chỉ cần tìm phần tử ngoài cùng bên trái của cây. Đây là việc thực hiện logic này

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild=None def insert(root,newValue): #if binary search tree is empty, make a new node and declare it as root if root is None: root=BinaryTreeNode(newValue) return root #binary search tree is not empty, so we will insert it into the tree #if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue<root.data: root.leftChild=insert(root.leftChild,newValue) else: #if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild=insert(root.rightChild,newValue) return root def findSmallestElement(root): #check if binary search tree is empty if root==None: return False #check if current node is leftmost node elif root.leftChild==None: return root.data #check right subtree of current node else: return findSmallestElement(root.leftChild) root= insert(None,15) insert(root,10) insert(root,25) insert(root,6) insert(root,14) insert(root,20) insert(root,60) print("Smallest Element is:") print(findSmallestElement(root))

đầu ra

________số 8

Sự kết luận

Trong bài viết này, chúng ta đã thấy các khái niệm cơ bản đằng sau cây tìm kiếm nhị phân. Chúng tôi cũng đã triển khai các thao tác khác nhau như chèn, tìm kiếm, tìm phần tử lớn nhất và tìm phần tử nhỏ nhất trong cây tìm kiếm nhị phân

Tôi sẽ khuyến khích bạn thực hiện các mã và chơi với chúng. Hãy theo dõi để biết thêm hướng dẫn thông tin

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

cây tìm kiếm nhị phân với ví dụ là gì?

Python có sử dụng tìm kiếm nhị phân không?