Binary Search Trees

Question

Đây là một số mã được tìm thấy trên wikipedia về BST:

# 'node' refers to the parent-node in this case 
def search_binary_tree(node, key): 
    if node is None: 
     return None # key not found 
    if key < node.key: 
     return search_binary_tree(node.leftChild, key) 
    elif key > node.key: 
     return search_binary_tree(node.rightChild, key) 
    else: # key is equal to node key 
     return node.value # found key 

Bây giờ đây là một cây nhị phân:

 10 
    5  12 
    3 8 9 14 
    4 11 

Nếu tôi đang tìm kiếm 11, và tôi làm theo các thuật toán lên đó , Tôi bắt đầu với 10, tôi đi ngay đến 12, và sau đó còn lại đến 9. Và tôi đạt đến cuối của cây mà không tìm thấy 11. Nhưng 11 tồn tại trong cây của tôi, nó chỉ ở phía bên kia.

Bạn có thể giải thích những hạn chế trong cây nhị phân để thuật toán này hoạt động trên cây của tôi không?

Cảm ơn.

Answer 1

Chỉ vì cây của bạn không phải là cây tìm kiếm nhị phân: cây không được đặt hàng chính xác. BST được xây dựng như mô tả trong thuật toán thực sự. Ví dụ trong cây của bạn: nút '9' không ở đúng vị trí vì vì 9 < 10 nên nằm dưới nhánh bên trái của nút gốc '10'. Tương tự cho '14' và '11' nên ở bên phải nhánh.

ví dụ một BST có thể sth như thế này:

10 
    5 11 
3 8 12 
      14 

Answer 2

Đừng nhầm lẫn giữa cây nhị phân và cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân (viết tắt là BST) là một loại cây nhị phân đặc biệt, trong đó tất cả các nút ở bên trái nhỏ hơn hoặc bằng nút cha và tất cả các nút phải lớn hơn nút cha.

Trong khi ví dụ bạn đã cho chỉ là một cây nhị phân chứ không phải cây tìm kiếm nhị phân. Bạn có thể thấy rằng giá trị 11 và 14 được để lại cho nút cha 10 mà vi phạm thuộc tính BST. Hãy xem here cho cây tìm kiếm nhị phân.

Answer 3

Bạn đã đặt các nút 14 và 11 ở vị trí sai. Từ the Wikipedia article on BSTs:

• Các cây con trái của một node chỉ chứa các nút với các phím dưới phím nút của.
• Dấu phụ phải của nút chỉ chứa các nút có khóa lớn hơn khóa của nút .
• Cả hai subtrees trái và phải cũng phải là cây tìm kiếm nhị phân.

Như bạn có thể thấy, cả 14 và 11 lớn hơn 8.

Answer 4

Cây bạn trình bày trong không phải là một BST. 11 và 14 sẽ không bao giờ được chèn vào bên trái của 10, và đó là lý do tại sao các thuật toán không tìm kiếm ở đó. 9 cũng không đúng chỗ.

Insertion theo Wikipedia:

Chen bắt đầu như một tìm kiếm sẽ bắt đầu; nếu gốc không bằng giá trị, chúng tôi tìm kiếm các subtrees trái hoặc phải như trước. Cuối cùng, chúng ta sẽ đạt đến một nút bên ngoài và thêm giá trị là con phải hoặc trái của nó, tùy thuộc vào giá trị của nút. Nói cách khác, chúng tôi kiểm tra gốc và đệ quy chèn nút mới vào cây con trái nếu giá trị mới nhỏ hơn gốc, hoặc cây con phải nếu giá trị mới lớn hơn hoặc bằng gốc.

Bạn có thể nói rằng một cây nhị phân là một BST nếu nó có các đặc tính này (cũng từ Wikipedia):

1. Các cây con trái của một node chỉ chứa các nút với các phím dưới nút của Chìa khóa.
2. Dấu phụ phải của nút chỉ chứa các nút có khóa lớn hơn khóa của nút.
3. Cả hai subtrees trái và phải cũng phải là cây tìm kiếm nhị phân.

Answer 5

cây của bạn không phải là một cây tìm kiếm nhị phân