Các ứng dụng của cây nhị phân là gì?

Alice
Bob
Chloe
David
Edwina
Frank

do đó, khi đọc nó trở lại, kết thúc với cây sau:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

đó là hình thức thoái hóa. Nếu bạn đi tìm Frank trong cây đó, bạn sẽ phải tìm kiếm toàn bộ sáu nút trước khi bạn tìm thấy anh ta .Cây nhị phân trở nên thực sự hữu dụng cho việc tìm kiếm khi bạn cân đối chúng. Điều này tương quan đến việc xoay những cây con trải qua nút gốc của chúng sao cho chênh lệch chiều cao giữa hai cây con nhỏ hơn hoặc bằng 1. Thêm những tên trên một lần vào một cây cân đối sẽ cho bạn trình tự sau :

1.   Alice
    /     \
   =       =

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

Bạn thực sự có thể thấy toàn bộ các cây con quay sang trái (trong bước 3 và 6) khi các mục nhập được thêm vào và điều này cung cấp cho bạn một cây nhị phân cân bằng trong đó tra cứu trường hợp xấu nhất O(log N)thay vì O(N) mà dạng thoái hóa đưa ra. Không có điểm nào cao nhất NULL ( =) khác với mức thấp nhất nhiều hơn một cấp. Và, trong cây thức trên, bạn có thể tìm thấy Frank bằng cách chỉ nhìn vào ba nút ( Chloe, Edwinavà cuối cùng, Frank).

Tất nhiên, chúng hoàn toàn có thể trở nên hữu dụng hơn nữa khi bạn làm cho chúng cân đối cây đa chiều hơn là tress nhị phân. Điều đó có nghĩa là mỗi nút chứa nhiều hơn một mục ( về mặt kỹ thuật, chúng giữ N mục và con trỏ N + 1, cây nhị phân là trường hợp đặc biệt quan trọng của cây đa chiều 1 chiều với 1 mục và 2 con trỏ ) .Với cây ba chiều, bạn kết thúc với :

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

Điều này thường được sử dụng trong việc duy trì các khóa cho một chỉ mục của các mục. Tôi đã viết phần mềm cơ sở dữ liệu được tối ưu hóa cho phần cứng trong đó một nút có kích thước chính xác bằng một khối đĩa (giả sử là 512 byte) và bạn đặt càng nhiều khóa càng tốt vào một nút. Các con trỏ trong trường hợp này thực sự là các số ghi vào một tệp truy cập trực tiếp bản ghi có độ dài cố định tách biệt với tệp chỉ mục (vì vậy Xcó thể tìm thấy số bản ghi chỉ bằng cách tìm kiếm X * record_length).

Ví dụ : nếu con trỏ là 4 byte và size khóa là 10, số lượng khóa trong nút 512 byte là 36. Đó là 36 phím ( 360 byte ) và 37 con trỏ ( 148 byte ) cho tổng số 508 byte với 4 byte tiêu tốn lãng phí cho mỗi nút .Việc sử dụng những khóa đa chiều trình làng sự phức tạp của tìm kiếm hai pha ( tìm kiếm đa chiều để tìm nút đúng mực phối hợp với tìm kiếm tuần tự nhỏ ( hoặc nhị phân tuyến tính ) để tìm khóa đúng chuẩn trong nút ) nhưng lợi thế trong làm ít I / O đĩa hơn bù cho việc này .Tôi thấy không có nguyên do gì để làm điều này cho cấu trúc trong bộ nhớ, tốt hơn hết bạn nên gắn bó với cây nhị phân cân đối và giữ cho mã của bạn đơn thuần .

Ngoài ra, hãy nhớ rằng những lợi thế của O(log N)hơn O(N)không thực sự xuất hiện khi bộ dữ liệu của bạn nhỏ. Nếu bạn đang sử dụng cây đa chiều để lưu trữ mười lăm người trong sổ địa chỉ của bạn, điều đó có thể là quá mức cần thiết. Những lợi thế có được khi bạn lưu trữ thứ gì đó như mọi đơn hàng từ hàng trăm nghìn khách hàng của bạn trong mười năm qua.

Toàn bộ quan điểm của ký hiệu big-O là chỉ ra những gì xảy ra khi Ntiếp cận vô hạn. Một số người có thể không đồng ý nhưng thậm chí vẫn ổn khi sử dụng sắp xếp bong bóng nếu bạn chắc chắn các bộ dữ liệu sẽ ở dưới một kích thước nhất định, miễn là không có sẵn thứ gì khác 🙂

Đối với việc sử dụng khác cho cây nhị phân, có rất nhiều, ví dụ điển hình như :

• Các đống nhị phân trong đó các khóa cao hơn ở trên hoặc bằng với các phím thấp hơn thay vì bên trái của (hoặc bên dưới hoặc bằng và bên phải);
• Cây băm, tương tự như bảng băm;
• Cây cú pháp trừu tượng để biên dịch ngôn ngữ máy tính;
• Cây Huffman để nén dữ liệu;
• Cây định tuyến cho lưu lượng mạng.

Dựa vào mức độ lý giải mà tôi đã tạo cho những cây tìm kiếm, tôi rất thận trọng khi đi sâu vào nhiều cụ thể khác, nhưng điều đó đủ để nghiên cứu và điều tra chúng, nếu bạn mong ước .

Source: https://mindovermetal.org
Category: Ứng dụng hay