Cây nhị phân tìm kiếm cân bằng ― chỉ lưu trữ dữ liệu trong lá

Question

Tôi đã mua một cuốn sách nhỏ về hình học tính toán và khi đọc nó ở đây và ở đó tôi thường tình cờ sử dụng loại cây nhị phân đặc biệt này. Những cây này được cân bằng và chỉ lưu trữ dữ liệu trong các nút rời, các nút bên trong chỉ nên lưu trữ các giá trị để hướng dẫn tìm kiếm xuống các lá.

Những hình ảnh cho thấy một cây dụ, nơi những chiếc lá là hình chữ nhật và các nút bên trong là vòng tròn.

Tôi có hai câu hỏi về điều đó:

1. lợi thế là không lưu trữ dữ liệu trong các nút bên trong là gì?
2. Với mục đích học tập, tôi muốn thực hiện một cây như vậy, do đó tôi nghĩ nên sử dụng cây AVL làm cơ sở, nhưng phải không?

Cuối cùng nhưng không kém phần quan trọng tôi muốn nhấn mạnh thực tế rằng tôi đang xử lý nội dung đó vì tôi muốn tìm hiểu điều gì đó, vì vậy mọi nguồn tài nguyên hữu ích đều được hoan nghênh. Cảm ơn bạn trước, liên quan ....

Answer 1

quảng cáo 1: Nói chung không có lợi thế là không lưu trữ dữ liệu trong các nút bên trong. Ví dụ, cây RB cũng là cây cân bằng và lưu trữ dữ liệu của nó vào các nút bên trong thay vì các lá (xem: http://en.wikipedia.org/wiki/Red-black_tree)

ad 2: IMHO chắc chắn nhất là. (Một ý tưởng tốt)

Answer 2

1. có một số cấu trúc dữ liệu cây đó, do thiết kế, yêu cầu không có dữ liệu được lưu trữ trong các nút bên, chẳng hạn như Huffman code trees và B+ trees. Trong trường hợp cây Huffman, yêu cầu là không có hai lá nào có cùng tiền tố (tức là đường dẫn đến nút 'A' là 101 trong khi đường dẫn đến nút 'B' là 10). Trong trường hợp cây B + nó xuất phát từ thực tế là nó được tối ưu hóa cho tìm kiếm khối (điều này cũng có nghĩa là mỗi nút nội bộ có rất nhiều trẻ em, và cây thường chỉ có một vài cấp độ sâu).
2. Chắc chắn! Một cây AVL không phải là cực kỳ phức tạp, vì vậy nó là một ứng cử viên tốt cho việc học tập.

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

Answer 3

Một lợi ích duy nhất để giữ dữ liệu trong các nút lá (ví dụ: cây B +) là việc quét/đọc dữ liệu cực kỳ đơn giản. Các nút lá được liên kết với nhau. Vì vậy, để đọc các mục tiếp theo khi bạn đang ở "cuối" (phải hoặc trái) của dữ liệu trong một nút lá nhất định, bạn chỉ cần đọc liên kết/con trỏ đến nút tiếp theo (hoặc trước đó) và nhảy đến trang lá tiếp theo .

Với cây B nơi dữ liệu nằm trong mọi nút, bạn phải đi qua cây để đọc dữ liệu theo thứ tự. Đó chắc chắn là một quy trình được xác định rõ nhưng được cho là phức tạp hơn và thường đòi hỏi nhiều thông tin tiểu bang hơn.

Answer 4

Thông thường có các loại cây nhị phân khác với dữ liệu ở lá thay vì các nút bên trong, nhưng khá phổ biến đối với các cây TÌM nhị phân.

Một lý do bạn có thể muốn làm điều này là giáo dục - thường là EASIER để triển khai cây tìm kiếm nhị phân theo cách này, theo cách truyền thống. Tại sao? Hầu như hoàn toàn là do xóa.Việc xóa một chiếc lá thường rất dễ dàng, trong khi việc xóa một nút bên trong thì khó khăn hơn. Nếu dữ liệu của bạn chỉ ở lá, thì bạn luôn ở trong trường hợp dễ dàng!

Thật đáng để suy nghĩ về nơi các phím trên các nút bên trong đến từ đó. Thường thì chúng là bản sao của các khóa cũng nằm ở các lá (có dữ liệu). Sau đó, nếu khóa ở lá bị xóa, chìa khóa ở các nút bên trong vẫn có thể treo xung quanh.

Answer 5

Tôi đang đọc cùng một cuốn sách và họ nói rằng nó có thể được thực hiện theo cách, lưu trữ dữ liệu ở bên ngoài hoặc tại các nút nội bộ.

Cây họ sử dụng là Đỏ-đen.

Trong mọi trường hợp, đây là một bài viết lưu trữ dữ liệu tại các nút nội bộ của một cây đen đỏ và sau đó liên kết các nút dữ liệu này với nhau dưới dạng danh sách.

Cân bằng cây tìm kiếm nhị phân với một danh sách gấp đôi được liên kết trong C++ bởi Arjan van den Boogaard

http://archive.gamedev.net/archive/reference/programming/features/TStorage/default.html