AVL tree 2 chiều

[DICKU]

Xin chào mọi người.
Mình đang làm một bài toán có sử dụng AVL Tree 2 chiều(không có tài liệu về nó). Vd 1 chiều lưu giá trị x và 1 chiều lưu giá trị y. Theo mình hiểu thì 1 nút trong cây ban đầu chứa x lại là một nút gốc trong cây khác chứa y.
Nếu là 1 chiều thì trong sách rất nhiều, nhưng 2 chiều không thấy nói gì cả. Mình chưa biết cách cài đặt cấu trúc cho AVL Tree 2 chiều thế nào cũng như những thao tác thêm xóa, sửa và tìm kiếm.
Bạn nào đã làm qua hay hiểu biết về AVL Tree có thể cho mình một đề xuất CTDL hay không? Hoặc có tài liệu gì thì share cho mình với.
mong nhận sự giúp đỡ.

[dq_ninh]

Xin chào mọi người.
Mình đang làm một bài toán có sử dụng AVL Tree 2 chiều(không có tài liệu về nó). Vd 1 chiều lưu giá trị x và 1 chiều lưu giá trị y. Theo mình hiểu thì 1 nút trong cây ban đầu chứa x lại là một nút gốc trong cây khác chứa y.
Nếu là 1 chiều thì trong sách rất nhiều, nhưng 2 chiều không thấy nói gì cả. Mình chưa biết cách cài đặt cấu trúc cho AVL Tree 2 chiều thế nào cũng như những thao tác thêm xóa, sửa và tìm kiếm.
Bạn nào đã làm qua hay hiểu biết về AVL Tree có thể cho mình một đề xuất CTDL hay không? Hoặc có tài liệu gì thì share cho mình với.
mong nhận sự giúp đỡ.


Tại sao lại không có tài liệu về AVL Tree? Bạn nói giỡn chơi hoài. AVL là một cây nhị phân thăng bằng. Có nghĩa là chiều cao của cây trái và cây phải chỉ có thể khác nhau tối đa là một. Và "2 chiều?" Có phải bạn muốn nói đến double rotation? Nếu đúng vậy (2 chiều = double rotation), thì 2 chiều chỉ là cách nói của một AVT đã phạm lỗi cân bằng thôi.

Tài liệu về AVL tree, hay còn gọi là cây nhị phân thăng bằng, thì có cả một rừng trên mạng. Nếu muốn tìm thêm về "2 chiều", thì google "AVL tree double rotation"

Vào đây để nghiên cứu source code:
http://www.codeproject.com/KB/architecture/avl_cpp.aspx?display=Print

Bài này có nói về double rotation (mà bạn gọi là 2 chiều) và cách làm cho nó cân bằng lại khi double rotation xảy ra:
http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

[DICKU]

Trước hết cám ơn bạn, nhưng ý mình không phải là quay 2 lần "double rotate" mà là 2 chiều two-dimensional AVL tree.
vd: http://www.emilstefanov.net/Projects/RangeSearchTree.aspx
nhưng là sử dụng cây AVL chứ không phải range search tree
hình khác:

http://upnhanh.sieuthinhanh.com/userimages/images/sieuthiNHANH2009081122233mdg5njyzmw55917.jpeg

[dq_ninh]

Man... Cái món này thấy khó nuốt quá...Tôi có chương mục với Safari.net, có cả hàng trăm ngàn cuốn sách, vậy mà vào tìm cũng không ra được một quyển.

Dưới đây có hai cái links, hy vọng nó giúp được chút chút.


http://www.adass.org/adass/proceedings/adass94/barrettp.html

http://www.codeproject.com/KB/architecture/binarytreeintro.aspx?display=Print

[cal]

@DICKU:
Lãnh vực này quá hẹp, không thấy tài liệu.
Có được 1 paragraph liên quan: http://books.google.com/books?id=KrQdmLjTSaQC&pg=PA66#v=onepage&q=&f=false

Theo cấu trúc dữ liệu của Vaishnavi:
- giả sử cần lưu giá trị x (chiều 1), y (chiều 2)
- Gồm 1 cây AVL (chỉ duy nhất 1 cây) lưu giá trị của chiều thứ 1, mỗi node của nó có thêm một child (ngoài left và right) là 1 cây AVL lưu giá trị của chiều thứ 2.

Đại khái cần 2 struct sau:



struct YNode {
float y;
struct YNode *left, *right;
};

struct XNode {
float x;
struct XNode *left, *right;
struct YNode *ytree; // chỉ đến nút gốc của 1 cây AVL lưu (các) giá trị y.
};

Các tác vụ thêm, xóa, sửa, tìm kiếm tương tự cây AVL. Chuyện này chắc bro hình dung được rồi.

[DICKU]

Thanks các bạn nhiều.