Tìm hiểu về cấu trúc cây tìm kiếm nhị phân

Question

Tôi đang gặp khó khăn trong việc hiểu cách cây tìm kiếm nhị phân được xây dựng. Họ có yêu cầu dữ liệu ban đầu được sắp xếp để tìm ra gốc cao nhất?

Answer 1

Hình dạng một cây tìm kiếm nhị phân có phụ thuộc vào hai điều:

1. Thứ tự mà các yếu tố được chèn, và
2. hoạt động cân bằng gì, nếu có, cây làm trong suốt chèn.

Nếu bạn có cây tìm kiếm nhị phân thuần túy không có logic cân bằng lại, thứ tự các yếu tố được chèn vào sẽ có tác động mạnh đến hình dạng của cây. Ví dụ: lấy các giá trị 1, 2, 3, 4, 5, 6, 7. Nếu bạn chèn chúng vào thứ tự 4, 2, 6, 1, 3, 5, 7, bạn sẽ nhận được cây này:

 4 
    / \ 
    2  6 
    /\ /\ 
    1 3 5 7 

lý do cho điều này là chúng ta đi qua hàng loạt sau của cây:

 4 

    4 
/
    2 

    4 
/ \ 
    2  6 

    4 
/ \ 
    2  6 
/
1 

    4 
/ \ 
    2  6 
/\ 
1 3 

    4 
/ \ 
    2  6 
/\ /
1 3 5 

    4 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

Mặt khác, nếu bạn chèn các giá trị theo thứ tự 1, 2, 3, 4, 5, 6 , 7, bạn sẽ có được cây này:

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

Thú vị, chèn các phần tử vào BST theo thứ tự sắp xếp là o ne của các tồi tệ nhất những điều bạn có thể làm cho cây, vì nó làm cho cây cấu trúc tuyến tính. Bạn đang tốt hơn chọn một hoán vị ngẫu nhiên của các yếu tố để chèn, hoặc (nếu tất cả chúng được biết đến trước) phân loại chúng và sử dụng các thuật toán đệ quy sau đây về trình tự sắp xếp:

• Nếu không có các yếu tố, Bạn xong việc rồi.
• Nếu không:
  • Chèn trung vị vào BST.
  • Đệ quy chèn nửa phần tử đầu tiên vào BST.
  • Đệ quy chèn nửa sau của các phần tử vào BST.

Hy vọng điều này sẽ hữu ích!