Tổng quan về hệ thống thông tin địa lý (GIS)
Hệ thống thông tin địa lý (GIS) là một lĩnh vực công nghệ thông tin, ra đời từ những năm 1960 và đã có sự phát triển mạnh mẽ trong những năm gần đây.
GIS được áp dụng để đồng bộ hóa các lớp thông tin không gian (bản đồ) với thông tin thuộc tính, hỗ trợ nghiên cứu, quy hoạch và quản lý các hoạt động theo lãnh thổ.
Ngày nay, GIS đã trở thành công cụ thiết yếu hỗ trợ quyết định trong nhiều lĩnh vực như kinh tế-xã hội, an ninh, quốc phòng và ứng phó thảm họa thiên tai Công nghệ này giúp các cơ quan chính phủ, nhà quản lý và doanh nghiệp đánh giá hiện trạng các quá trình và thực thể tự nhiên thông qua việc thu thập, quản lý, truy vấn, phân tích và tích hợp thông tin trên nền bản đồ số với tọa độ chính xác.
Hệ thống Thông tin Địa lý (GIS) là một hệ thống tích hợp giữa con người và công nghệ máy tính cùng các thiết bị ngoại vi, cho phép lưu trữ, xử lý, phân tích và hiển thị thông tin địa lý Mục tiêu chính của GIS là phục vụ cho nghiên cứu và quản lý trong các lĩnh vực khác nhau.
GIS là một công cụ quan trọng để thu thập, lưu trữ, biến đổi và hiển thị thông tin không gian, phục vụ cho các mục đích cụ thể.
GIS, dưới góc độ phần mềm, xử lý thông tin không gian và phi không gian, đồng thời thiết lập các mối quan hệ không gian giữa các đối tượng Các chức năng phân tích không gian chính là yếu tố tạo nên bản sắc riêng của GIS.
Xét về ứng dụng trong quản lý nhà nước, GIS là công nghệ xử lý dữ liệu tọa độ, giúp chuyển đổi chúng thành thông tin hỗ trợ quyết định cho các nhà quản lý.
Xét dưới góc độ hệ thống, GIS là hệ thống gồm các hợp phần: Phần cứng, Phần mềm, Cơ sở dữ liệu và Cơ sở tri thức chuyên gia
TÇng §-êng quèc lé hè
Thuỷ lợi Cây trồng KhÝ hËu
Giám sát Lập bản đồ Đo đạc t3 t2 t1
Hệ thông tin địa lý
Hệ thống GIS lưu trữ thông tin thế giới thực thành các tầng bản đồ chuyên đề có khả năng liên kết địa lý với nhau, phục vụ nhu cầu của các nhóm người sử dụng khác nhau Chẳng hạn, Sở giao thông công chính tập trung vào hệ thống đường phố, trong khi Sở Nhà đất chú trọng đến khu dân cư và công sở, và Sở Thương mại quan tâm đến phân bố khách hàng Việc tách bản đồ thành các tầng không chỉ đơn giản mà còn linh hoạt và hiệu quả, giúp giải quyết nhiều vấn đề thực tiễn như theo dõi giao thông và lập kế hoạch lưu thông Ngoài ra, quá trình mã hóa địa lý (geocoding) cho phép liên kết dữ liệu bên ngoài với dữ liệu bản đồ, ví dụ như ánh xạ thông tin bán hàng theo mã bưu điện hoặc chỉ ra địa chỉ khách hàng trên bản đồ.
Hình 1.2 Các hoạt động chính của GIS
1.1.2 Các thành phần của hệ thống thông tin địa lý
Công nghệ GIS gồm 5 hợp phần cơ bản là:
- Chính sách và cách thức quản lý (Policy and Management)
Hình 1.3 Các hợp phần thiết yếu cho công nghệ GIS
The essential components of a digital workspace include computers, plotters, printers, digitizers, scanners, and various data storage devices such as floppy diskettes, optical cartridges, and CD-ROMs.
Hình 1.4 Các thành phần thiết bị cơ bản của GIS
Phần mềm là tập hợp các lệnh và chỉ thị điều khiển phần cứng máy tính thực hiện nhiệm vụ cụ thể Phần mềm hệ thống thông tin địa lý (GIS) có thể là một hoặc nhiều phần mềm kết hợp Để sử dụng hiệu quả trong kỹ thuật GIS, phần mềm cần có các tính năng cơ bản nhất định.
Nhập và kiểm tra dữ liệu là quá trình chuyển đổi thông tin từ dạng bản đồ sang dạng số tương thích, bao gồm tất cả các khía cạnh liên quan đến biến đổi dữ liệu trong lĩnh vực quan sát.
Lưu trữ và quản lý cơ sở dữ liệu liên quan đến việc kết nối thông tin vị trí (topology) và thông tin thuộc tính (attributes) của các đối tượng địa lý như điểm và đường trên bề mặt trái đất Hai loại thông tin này được tổ chức và liên kết thông qua các thao tác trên máy tính, nhằm giúp người sử dụng hệ thống dễ dàng tiếp cận và hiểu biết.
Xuất dữ liệu là quá trình trình bày và báo cáo kết quả phân tích cho người sử dụng, bao gồm các định dạng như bản đồ (MAP), bảng biểu (TABLE), biểu đồ và lưu đồ (FIGURE) Những thông tin này có thể được hiển thị trên máy tính, máy in hoặc máy vẽ, giúp người dùng dễ dàng tiếp cận và hiểu rõ hơn về dữ liệu.
- Biến đổi dữ liệu (Data transformation): biến đổi dữ liệu gồm hai lớp điều hành nhằm mục đích khắc phục lỗi từ dữ liệu và cập nhật chúng
Giao tiếp với người dùng là yếu tố quan trọng nhất trong bất kỳ hệ thống thông tin nào Các giao diện người dùng được thiết kế dựa trên mục đích của ứng dụng, nhằm tối ưu hóa trải nghiệm và hiệu quả sử dụng.
Các phần mềm GIS tiêu chuẩn và phổ biến hiện nay tại khu vực Châu Á bao gồm ARC/INFO, MAPINFOR, IL WIS, WINGIS, SPANS, và IDRISIW Hiện tại, có rất nhiều phần mềm máy tính chuyên biệt dành cho GIS, đáp ứng nhu cầu quản lý và phân tích dữ liệu địa lý.
+ Phần mềm dùng cho lưu trữ, xử lý số liệu thông tin địa lý: ACR/INFO, SPAN, ERDAS-Imagine, IL WIS, MGE/MICROSTATION, IDRISIW
+ Phần mềm dùng cho lưu trữ, xử lý và quản lý các thông tin địa lý: ER-MAPPER, ATLASGIS, ARCVIEW, MAPINFO
Cơ sở dữ liệu không gian
Con người xây dựng mô hình của hiện thực, phản ánh một số khía cạnh chọn lọc từ thế giới xung quanh Mô hình này cung cấp một cái nhìn đầy đủ về hệ thống từ một góc độ cụ thể, được hình thành qua quá trình trừu tượng hóa một cách thông minh Cơ sở dữ liệu không gian được phát triển từ các mô hình này, nhằm mô tả trạng thái và bản chất của thực tại.
Hình 1.6 Minh hoạ mô hình hoá
* Định nghĩa CSDL không gian:
Cơ sở dữ liệu không gian là tập hợp dữ liệu tham chiếu không gian, có vai trò như mô hình của hiện thực:
+ CSDL là mô hình hiện thực theo nghĩa nó biểu diễn tập lựa chọn hay xấp xỉ các hiện tượng
+ Các hiện tượng lựa chọn này được xem là quan trọng, đủ để biểu diễn đặc trưng dưới dạng số cho hiện tại, quá khứ và tương lai
1.2.1 Tổ chức các mẩu tin trong tệp
Dữ liệu trên đĩa được tổ chức thành: trường (field), mẩu tin (record), tệp
Trong mô hình quan hệ, trường thể hiện đặc tính của một quan hệ hoặc thực thể Mỗi mẩu tin đại diện cho một hàng trong bảng quan hệ, bao gồm các trường tương ứng với các thuộc tính của bảng Tệp là tập hợp các mẩu tin mô tả một quan hệ, và có thể bao gồm các tập hợp khác liên quan đến các quan hệ khác nhau.
Hình 1.7 Ánh xạ các mẩu tin từ Country, City và River vào các trang đĩa
Để biểu diễn các mẩu tin trong một cấu trúc tệp, cần hiểu rằng một thể hiện của một quan hệ là tập hợp các mẩu tin Vấn đề quan trọng là cách tổ chức các mẩu tin này trong tệp Có nhiều phương pháp tổ chức khác nhau để thực hiện điều này.
Tổ chức tệp đống (Heap File Organization) cho phép lưu trữ các mẩu tin một cách ngẫu nhiên trong tệp mà không cần thứ tự cụ thể, phù hợp cho các bảng như River Tuy nhiên, phương pháp này không hiệu quả cho việc tìm kiếm mẩu tin theo khóa, vì cần phải quét toàn bộ mẩu tin trong tệp, dẫn đến việc kiểm tra tất cả các trang đĩa chứa dữ liệu Ngược lại, việc chèn mẩu tin mới vào cuối tệp diễn ra một cách đơn giản và nhanh chóng.
Sequential file organization involves storing data records in a sequential manner, arranged according to the search key value of each record This method ensures that records are easily accessible and efficiently managed, making it a fundamental approach in data storage systems.
Tổ chức tệp tuần tự được thiết kế để xử lý hiệu quả các mẩu tin theo thứ tự khoá tìm kiếm, cho phép tìm lại nhanh chóng các mẩu tin Để thực hiện điều này, các mẩu tin được "xích" lại với nhau bằng các con trỏ, với mỗi con trỏ trỏ tới mẩu tin kế tiếp theo thứ tự khoá tìm kiếm Hơn nữa, việc lưu trữ vật lý các mẩu tin theo thứ tự khoá tìm kiếm giúp tối ưu hoá số khối truy xuất trong quá trình xử lý tệp tuần tự.
Tổ chức tệp tuần tự cho phép đọc các mẩu tin theo thứ tự đã sắp xếp, điều này rất hữu ích cho việc trình bày thông tin và cải thiện hiệu suất của các thuật toán xử lý truy vấn.
Tệp được tổ chức bằng cách sắp xếp các mẩu tin theo trường khóa đã chỉ định Ví dụ, hình 1.7 minh họa một tệp sắp xếp các mẩu tin trong bảng City dựa trên trường khóa là tên thành phố.
Hình 1.8 Tổ chức tệp có thứ tự cho bảng City
Tổ chức tệp băm (Hashed File Organization) sử dụng hàm băm tính toán trên thuộc tính của mẩu tin để xác định vị trí của mẩu tin trong khối của tệp Cách tổ chức này có mối liên hệ chặt chẽ với cấu trúc chỉ mục, giúp tối ưu hóa quá trình truy xuất dữ liệu.
Tệp băm tổ chức các mẩu tin thành những thùng (buckets) thông qua một hàm băm (hashed function), ánh xạ giá trị trên một trường khóa được chọn, như tên thành phố Hình 1.8 minh họa hàm băm với 4 thùng, mỗi thùng lưu trữ trên một trang đĩa khác nhau Hàm băm trả về giá trị 1 cho tên có độ dài nhỏ hơn hoặc bằng 6 ký tự, 2 cho tên có độ dài 7 hoặc 8 ký tự, 3 cho tên có độ dài 9 hoặc 10 ký tự, và 4 cho tên có độ dài lớn hơn 11 ký tự, giúp ánh xạ tên thành phố vào các thùng từ 1 đến 4.
Hình 1.9 Tổ chức hàm băm cho bảng City
Tổ chức tệp cụm (Clustering File Organization) cho phép lưu trữ các mẩu tin từ nhiều quan hệ khác nhau trong cùng một tệp, giúp tối ưu hóa hiệu suất truy xuất dữ liệu Các mẩu tin có mối liên hệ được lưu trữ trong cùng một khối, đảm bảo mỗi hoạt động I/O sẽ trả về các mẩu tin liên quan từ tất cả các quan hệ, từ đó nâng cao hiệu quả của các truy vấn SQL.
SELECT Account_Number,Customer_Number, Customer_Street, ustomer_City
WHERE Depositor.Customer_Name = Customer.Customer_name;
Truy vấn này tính một phép nối của các quan hệ Depositor và Customer
Hệ thống cần tìm bộ Customer có giá trị Customer_Name tương ứng với mỗi bộ của Depositor, lý tưởng nhất là thông qua chỉ mục Tuy nhiên, chúng ta sẽ tập trung vào việc truyền dữ liệu từ đĩa vào bộ nhớ Trong trường hợp xấu nhất, mỗi mẩu tin nằm trong một khối khác nhau, dẫn đến việc phải đọc từng khối để lấy thông tin cần thiết Chúng tôi sẽ trình bày một cấu trúc tệp được thiết kế nhằm tối ưu hóa hiệu quả cho các truy vấn liên quan đến Depositor.Customer.
Cấu trúc lưu trữ Depositor cho mỗi Customer_Name gần bộ Customer tương ứng giúp tối ưu hóa việc xử lý truy vấn Khi một bộ dữ liệu Customer được truy cập, toàn bộ khối dữ liệu sẽ được tải vào bộ nhớ chính, bao gồm cả các bản ghi Depositor cần thiết Nếu một Customer có nhiều tài khoản nhưng không đủ để lấp đầy một khối, các bản ghi Depositor sẽ được lưu trữ trong khối tiếp theo Cách tổ chức tệp này, gọi là gom cụm (clustering), cho phép đọc nhiều bản ghi chỉ với một lần truy xuất khối, từ đó nâng cao hiệu quả xử lý truy vấn.
Cấu trúc tệp gom cụm không mang lại lợi ích bằng việc tổ chức lưu mỗi quan hệ trong một tệp riêng, đặc biệt đối với một số truy vấn nhất định.
Việc xác định thời điểm gom cụm dữ liệu phụ thuộc vào loại truy vấn mà nhà thiết kế cơ sở dữ liệu dự đoán sẽ xảy ra thường xuyên nhất Sử dụng gom cụm một cách hợp lý có thể nâng cao hiệu suất đáng kể trong việc xử lý các truy vấn.
1.2.2 Chỉ mục không gian (Spatial indexing )
Mở đầu
Dữ liệu từ hệ thống thông tin địa lý (GIS) cho phép lưu trữ thông tin về các vùng trên trái đất thông qua các bản đồ chứa các đặc điểm nổi bật Bản đồ này thường là hình ảnh hai chiều, trong đó một số điểm được xác định là đối tượng quan tâm Những điểm này có thể được lưu trữ trong nhiều cấu trúc dữ liệu đặc biệt để phục vụ cho các mục đích phân tích và nghiên cứu.
Hình 2.1 Bản đồ mẫu để biểu diễn bởi các cấu trúc cây
Nếu N là gốc của cây và P là cha của N, thì P sẽ là cấp độ quan tâm trên N Các điểm được đánh dấu bởi địa danh như Banja Luka và Brcko Thay vì chỉ tập trung vào các điểm quan tâm, ứng dụng cũng có thể chú ý đến vùng bản đồ.
Cấu trúc dữ liệu cần thiết phải có khả năng lưu trữ thông tin về các vùng Hình 2.1b) minh họa bản đồ với các vùng quan tâm được thể hiện rõ ràng.
Chương này chỉ ra cách biểu diễn dữ liệu bản đồ trên hình 2.1 bằng các loại cây k-d, cây tứ phân và cây R.
Cây k-d (k-d Trees)
Cây k-d được thiết kế để lưu trữ dữ liệu điểm k-chiều, như minh họa trong hình 2.1a, và không được sử dụng cho dữ liệu vùng Cụ thể, cây 2-d lưu trữ dữ liệu điểm 2-chiều, trong khi cây 3-d lưu trữ dữ liệu điểm 3-chiều Ví dụ này tập trung vào dữ liệu điểm 2-d và sau đó mở rộng khái niệm sang dữ liệu điểm 3-d.
Trong cây 2-d, mỗi nút có cấu trúc bản ghi nhất định với kiểu như sau: nodetype = record INFO: infotype;
Trường INFO có thể được định nghĩa theo nhiều kiểu khác nhau tùy thuộc vào ứng dụng cụ thể Ví dụ, nó có thể là một chuỗi ký tự mô tả địa danh hoặc một bản ghi bao gồm các trường như name (kiểu chuỗi) và population (kiểu số nguyên).
Trường XVAL, YVAL biểu thị tọa độ điểm kết hợp với nút
Các trường LLINK và RLINK trỏ đến hai cành
Giả sử T trỏ đến gốc của cây 2-d Nếu N là nút trong cây, thì mức của N được xác định qui nạp như sau:
Cây 2-d là cây nhị phân bất kỳ nếu thoả mãn điều kiện sau:
1 Nếu N là nút trong cây và level(N) là chẵn thì mỗi nút M trong cành rẽ nhánh từ N.LLINK có tính chất M.XVAL < N.XVAL, mỗi nút P trong cành rẽ nhánh từ N.RLINK có tính chất P.XVAL N.XVAL
2 Nếu N là nút trong cây và level(N) là lẻ thì mỗi nút M trong cành rẽ nhánh từ N.LLINK có tính chất M.YVAL < N.YVAL, mỗi nút P trong cành rẽ nhánh từ N.RLINK có tính chất P.YVAL N.YVAL
2.2.2 Chèn và tìm kiếm trong cây 2-d
Việc chèn nút N vào cây do T trỏ tới được phát biểu phi hình thức như sau:
Kiểm tra sự thống nhất giữa N và T ở các trường XVAL và YVAL Nếu thống nhất, ghi đè T và kết thúc; nếu không, rẽ trái nếu N.XVAL < T.XVAL, ngược lại rẽ phải Giả sử P là nút con đang khảo sát, nếu N và P thống nhất XVAL và YVAL, ghi đè P và kết thúc; nếu không, rẽ trái nếu N.YVAL < P.YVAL, hoặc rẽ phải trong trường hợp ngược lại Lặp lại quy trình, rẽ nhánh theo XVAL ở mức chẵn và theo YVAL ở mức lẻ trong cây.
Hình 2.2 Lưới bản đồ với kích thước 64x64
Hình 2.2 minh họa lưới bản đồ với gốc tọa độ (0, 0) nằm ở góc dưới trái Mỗi tế bào có kích thước 8, dẫn đến kích thước tổng thể của bản đồ là 64x64 Trong trường hợp này, chúng ta cần xây dựng một cây 2-d với trường INFO chỉ chứa tên địa điểm.
Danh sách các địa điểm như sau đây:
Khởi động cây là rỗng Hình 2.3 là trình tự chèn vào cây Các cây này được xây dựng như sau đây:
Hình 2.3 Trình tự chèn vào cây 2-d
1 Khi chèn Banja Luka vào cây có một nút với INFOnja Luka, XVAL, YVALE Nút này biểu diễn toàn bộ vùng bản đồ Tổng quát, mỗi nút N biểu diễn vùng Reg(N) Các trường XVAL và YVAL của nút N xác định điểm trong Reg(N) Điểm (N.XVAL, N.YVAL) chia Reg(N) thành 2 phần bằng
Mức 3 cách vẽ đường thẳng đứng qua điểm trong vùng (nếu nút ở mức chẵn) hay vẽ đường nằm ngang qua điểm trong vùng (nếu nút ở mức lẻ)
2 Khi chèn Derventa, phải so sánh các trường XVAL của nó với trường này của Banja Luka Chúng ta rẽ phải vì tọa độ x (40) của Derventa lớn hơn của
Banja Luka (19) chia đôi vùng bằng đường thẳng đứng, với mọi điểm bên phải có tọa độ x lớn hơn hoặc bằng 19, trong khi bên trái có tọa độ nhỏ hơn 19 Derventa đại diện cho vùng bên phải của đường thẳng đứng a trong hình 2.4.
3 Khi chèn Teslic, trước hết ta so sánh trường XVAL của Teslic và Banja Luka Trường này của Teslic là 38, của Banja Luka là 19, vậy ta phải rẽ phải
So sánh YVAL giữa Testic và Derventa cho thấy YVAL của Testic là 38, trong khi YVAL của Derventa là 50, dẫn đến việc phải rẽ trái Hình 2.3c minh
Hình 2.4 Mô tả phép chèn cây k-d trên bản đồ
4 Khi chèn Tuzla, trước hết phải so sánh XVAL của Tuzla và Banja Luka Giá trị XVAL của Tuzla là 54, còn của Banja Luka là 19, vậy phải rẽ phải Sau đó so sánh YVAL của Tuzla (40) và Derventa (50), vậy phải rẽ trái Tiếp tục so sánh XVAL của Tuzla (54) và Teslic (38), vậy phải rẽ phải (hình 2.3d)
5 Cuối cùng, khi chèn thành phố Sinj, ta phải so sánh XVAL của Sinj và Banja Luka Ta rẽ trái vì tọa độ x của Sinjnhor hơn của Banja Luka Kết quả được mô tả trên hình 2.3d và 2.3e
Trong trường hợp tồi nhất thì độ cao của cây 2-d với k nút là (k-1), việc tìm kiếm nút cho trước sẽ mất O(k) lần
Công việc phức tạp nhất trong cây 2 chiều là huỷ bỏ một điểm có tọa độ (x, y) Đầu tiên, cần xác định nút N trong cây T sao cho N.XVAL=x và N.YVAL=y Nếu nút N là nút lá, quá trình huỷ bỏ sẽ được thực hiện.
Để xóa nút N trong cây, cần thực hiện việc đặt NIL cho các liên kết LLINK và RLINK của nút cha N, sau đó giải phóng vùng nhớ của N Tuy nhiên, nếu N là một nút trong cây, quy trình trở nên phức tạp hơn Trong trường hợp này, cần xem xét cây con có gốc tại N.LLINK (gọi là Tl) hoặc tại N.RLINK.
Để thực hiện việc huỷ bỏ nút N trong cây, chúng ta cần tìm nút R từ T l hoặc Tr có khả năng thay thế nút N và có thể lần lượt bị loại bỏ khỏi cây con Các bước của thuật toán này sẽ được thực hiện một cách tuần tự và logic.
Bước 1: Tìm nút ứng viên thay thế R trong Ti với i{l, r}
Bước 2: Thay thế tất cả các trường không liên kết của N bằng các trường của R Bước 3: Loại bỏ đệ quy R khỏi Ti, với i thuộc {l, r}, do đệ quy này có điểm dừng vì Ti có độ cao nhỏ hơn cây T.
Cây tứ phân điểm (Point Quadtrees)
Cây tứ phân điểm là một cấu trúc dữ liệu tương tự như cây 2-d, nhưng nó phân chia một vùng không gian thành 4 phần thay vì 2 Cụ thể, nút N trong cây tứ phân sẽ vẽ cả đường thẳng đứng và đường nằm ngang qua điểm (N.XVAL, N.YVAL), tạo ra bốn góc: NW (Tây Bắc), SW (Tây Nam), NE (Đông Bắc) và SE (Đông Nam) Mỗi góc này tương ứng với một nhánh của nút N, cho phép cây bốn nhánh xác định 4 cành Để thực hiện các thao tác trên cây tứ phân, trước tiên cần định nghĩa cấu trúc nút cho một nút của cây tứ phân.
NW, SW, NE, SE : qtnodetype; end
2.3.1 Chèn và tìm kiếm trong cây tứ phân điểm
Bây giờ chúng ta hãy khảo sát tập 5 điểm (Banja Luka, Derventa, Teslic,
Cây 2-d của Tuzla và Sinj sẽ được thể hiện thông qua cây tứ phân, như minh họa trong Hình 2.6 Quá trình xây dựng cây tứ phân được mô tả cụ thể trong bài viết.
1 Khởi đầu cây tứ phân là rỗng, việc chèn Banja Luka tạo ra nút gốc của cây được gán nhãn với cặp (19, 45)
2 Việc chèn Derventa tạo ra vùng miêu tả bởi Banja Luka được phân thành 4 phần thông qua việc vẽ một đường nằm ngang và một đường thẳng đứng qua (19, 45) Derventa, ở vị trí (40, 50), nằm trong góc phần tư NE, do vậy Banja Luka có con NE là Derventa
Hình 2.5 Bản đồ mẫu để xây dựng cây tứ phân điểm
Hình 2.6 Tiến trình chèn vào cây tứ phân điểm
3 Việc chèn Teslic được tiến hành như sau: Teslic nằm theo hướng Đông Nam của Banja Luka Do vùng này hiện tại chưa có điểm nào nên chúng ta đặt Teslic làm con SE của Banja Luka
4 Việc chèn Tuzla phức tạp hơn Chúng ta thấy rằng Tuzla nằm ở SE của
Banja Luka, khu vực phía đông nam, được chia thành bốn phần bởi các đường ngang và dọc, tạo nên một cấu trúc rõ ràng trong khu vực này.
Teslic điểm Teslic Với kết quả bốn phần được tạo ra, Tuzla ở góc SE và như vậy Tuzla trở thành nút con SE của Teslic
5 Cuối cùng, việc chèn Sinj là không quá phức tạp bởi vì nó nằm ở SW của Banja Luka Do hiện tại con trỏ này là rỗng nên ta đặt nút này chứa thông tin liên quan đến Sinj
Chiều cao tối đa của một cây tứ phân chứa n nút là n-1, điều này cho thấy thời gian tìm kiếm và chèn nút trong cây này luôn nhỏ hơn tổng số nút hiện có.
2.3.2 Thao tác xoá trên cây tứ phân điểm
Khi xóa nút N từ cây tứ phân có gốc T, quy trình tương tự như khi thực hiện với cây 2-d để tìm nút thay thế cho các nút không phải lá Đối với các nút lá, việc xóa diễn ra đơn giản: chúng ta chỉ cần cập nhật trường liên kết của nút cha của N để trỏ tới NIL và giải phóng không gian lưu trữ.
Việc xoá trong cây tứ phân là một quá trình phức tạp, như được minh họa trong hình 2.7 Mỗi nút trong cây tứ phân đại diện cho một vùng, và cách định nghĩa vùng này khác với cây 2-d Trong cây 2-d, việc kết hợp các ràng buộc như x≥c1, x
