Cây tìm kiếm nhị phân - một cơ sở dữ liệu có cấu trúc chứa các nút, hai liên kết đến các nút khác, phải và trái. Các nút là một đối tượng của lớp có dữ liệu và NULL là dấu hiệu đánh dấu phần cuối của cây.
Nó thường được gọi là BST, có tính chất đặc biệt: các nút lớn hơn nút gốc nằm ở bên phải của nó và các nút nhỏ hơn ở bên trái.
Lý thuyết chung và thuật ngữ
Trong cây tìm kiếm nhị phân, mỗi nút, không bao gồm gốc, được kết nối bằng một cạnh có hướng từ nút này sang nút khác, được gọi là nút cha. Mỗi nút trong số chúng có thể được kết nối với một số nút tùy ý, được gọi là nút con. Các nút không có "con" được gọi là lá (nút ngoài). Các phần tử không phải là lá được gọi là bên trong. Các nút có cùng cha mẹ là anh chị em ruột. Nút trên cùng được gọi là nút gốc. Trong BST, chỉ định một phần tử cho mỗi nút và đảm bảo chúng có bộ thuộc tính đặc biệt cho chúng.
Thuật ngữ cây:
- Độ sâu của một nút là số cạnh được xác định từ gốc đến nó.
- Chiều cao của một nút là số cạnh được xác định từ nó đến lá sâu nhất.
- Chiều cao của cây được xác định bởi chiều cao của rễ.
- Cây tìm kiếm nhị phân là một thiết kế đặc biệt, nó cung cấp tỷ lệ chiều cao và số lượng nút tốt nhất.
- Độ cao h với N nút nhiều nhất là O (log N).
Bạn có thể dễ dàng chứng minh điều này bằng cách đếm các nút ở mỗi cấp, bắt đầu từ gốc, giả sử rằng nó chứa số lớn nhất trong số chúng: n=1 + 2 + 4 +… + 2 h-1 + 2 h=2 h + 1 - 1 Giải điều này cho h ta được h=O (log n).
Lợi ích của gỗ:
- Phản ánh các mối quan hệ cấu trúc của dữ liệu.
- Được sử dụng để biểu thị phân cấp.
- Đảm bảo cài đặt và tìm kiếm hiệu quả.
- Cây là dữ liệu rất linh hoạt, cho phép bạn di chuyển các cây con với nỗ lực tối thiểu.
Phương pháp tìm kiếm
Nói chung, để xác định xem một giá trị có nằm trong BST hay không, hãy bắt đầu cây tìm kiếm nhị phân ở gốc của nó và xác định xem nó có đáp ứng các yêu cầu hay không:
- tận gốc;
- nằm trong cây con bên trái của gốc;
- trong cây con bên phải của gốc.
Nếu không có thanh ghi cơ sở nào được thỏa mãn, một tìm kiếm đệ quy được thực hiện trong cây con tương ứng. Thực tế có hai tùy chọn cơ bản:
- Cây trống - trả về sai.
- Giá trị nằm trong nút gốc - trả về true.
Cần lưu ý rằng cây tìm kiếm nhị phân với lược đồ đã phát triển luôn bắt đầu tìm kiếm dọc theo con đường từ gốc đến lá. Trong trường hợp xấu nhất, nó sẽ đi đến tận chiếc lá. Vì vậy, thời gian xấu nhất tỷ lệ với độ dài của đường đi dài nhất từ gốc đến lá, chính là chiều cao của cây. Nói chung, đây là lúc bạn cần biết mất bao lâu để tra cứu dưới dạng một hàm của số lượng giá trị được lưu trữ trong cây.
Nói cách khác, có mối quan hệ giữa số lượng nút trong BST và chiều cao của cây, tùy thuộc vào "hình dạng" của nó. Trong trường hợp xấu nhất, các nút chỉ có một nút con và cây tìm kiếm nhị phân cân bằng về cơ bản là một danh sách được liên kết. Ví dụ:
50
/
10
15
30
/
20
Cây này có 5 nút và chiều cao=5. Việc tìm các giá trị trong phạm vi 16-19 và 21-29 sẽ yêu cầu đường dẫn sau từ gốc đến lá (nút chứa giá trị 20), tức là., nó sẽ mất thời gian tỷ lệ thuận với số lượng nút. Tốt nhất là tất cả đều có 2 con, và các lá nằm ở độ sâu như nhau.
Cây tìm kiếm nhị phân này có 7 nút và chiều cao=3. Nói chung, một cây như thế này (cây đầy đủ) sẽ có chiều cao xấp xỉ log 2 (N), trong đó N là số nút trong cây. Giá trị của log 2 (N) là số lần (2) N có thể bị chia trước khi đạt 0.
Tổng kết: thời điểm cần tìm kiếm khủng nhất trong BST là O (chiều cao cây). Trường hợp xấu nhất cây "tuyến tính" là O (N), trong đó N là số nút trong cây. Tốt nhất, cây "hoàn chỉnh" là O (log N).
BST nhị phân chèn
Tự hỏi không biết nên ở đâunút mới nằm trong BST, bạn cần hiểu logic, nó phải được đặt ở nơi người dùng tìm thấy nó. Ngoài ra, bạn cần nhớ quy tắc:
- Không được phép trùng lặp, cố gắng chèn một giá trị trùng lặp sẽ tạo ra một ngoại lệ.
- Phương thức chèn công khai sử dụng phương thức "trợ giúp" đệ quy trợ giúp để thực sự chèn.
- Một nút chứa giá trị mới luôn được chèn dưới dạng một lá trong BST.
- Phương thức chèn public trả về void, nhưng phương thức helper trả về BSTnode. Nó thực hiện điều này để xử lý trường hợp nút được chuyển tới nó là null.
Nói chung, phương thức trợ giúp chỉ ra rằng nếu cây tìm kiếm nhị phân ban đầu trống, kết quả là một cây có một nút. Nếu không, kết quả sẽ là một con trỏ đến cùng một nút đã được chuyển làm đối số.
Xóa trong thuật toán nhị phân
Như bạn có thể mong đợi, việc xóa một phần tử liên quan đến việc tìm một nút có chứa giá trị cần xóa. Có một số điều trong mã này:
- BST sử dụng phương pháp xóa quá tải, trợ giúp. Nếu phần tử bạn đang tìm không có trong cây, thì phương thức trợ giúp cuối cùng sẽ được gọi với n==null. Đây không được coi là một lỗi, cây chỉ đơn giản là không thay đổi trong trường hợp này. Phương thức trình trợ giúp xóa trả về một giá trị - một con trỏ đến cây được cập nhật.
- Khi một lá bị loại bỏ, việc loại bỏ khỏi cây tìm kiếm nhị phân sẽ đặt con trỏ con tương ứng của cha của nó thành null hoặc gốc thành null nếu lá bị loại bỏ lànút là gốc và không có nút con.
- Lưu ý rằng lệnh gọi xóa phải là một trong các lệnh sau: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete (n. getRight (), key)). Do đó, trong cả ba trường hợp, phương thức xóa chỉ trả về null là đúng.
- Khi tìm kiếm nút chứa giá trị cần xóa thành công, có ba lựa chọn: nút bị xóa là một lá (không có con), nút bị xóa có một con, nó có hai trẻ em.
- Khi nút bị xóa có một nút con, bạn chỉ cần thay thế nó bằng một nút con, trả về một con trỏ cho nút con.
- Nếu nút cần xóa có 0 hoặc 1 nút con, thì phương thức xóa sẽ "đi theo đường dẫn" từ nút gốc đến nút đó. Vì vậy, thời gian xấu nhất tỷ lệ thuận với chiều cao của cây, cho cả tìm kiếm và chèn.
Nếu nút cần xóa có hai nút con, các bước sau được thực hiện:
- Tìm nút cần xóa, theo đường dẫn từ gốc đến nút đó.
- Tìm giá trị nhỏ nhất của v trong cây con bên phải, tiếp tục theo đường dẫn đến chiếc lá.
- Loại bỏ một cách đệ quy giá trị của v, theo cùng một đường dẫn như trong bước 2.
- Vì vậy, trong trường hợp xấu nhất, đường dẫn từ gốc đến lá được thực hiện hai lần.
Thứ tự của các chuyến đi
Traversal là một quá trình truy cập tất cả các nút trong một cây. Bởi vì cây tìm kiếm nhị phân C là một cấu trúc dữ liệu phi tuyến tính, không có truyền tải duy nhất. Ví dụ: đôi khi một số thuật toán duyệtđược nhóm thành hai loại sau:
- độ sâu vượt qua;
- lần đầu tiên vượt qua.
Chỉ có một loại băng qua chiều rộng - vượt qua mức. Các nút truy cập truyền tải này ở cấp độ thấp hơn và trái, trên cùng và phải.
Có ba loại giao cắt độ sâu khác nhau:
- Vượt qua Đơn đặt hàng trước - trước tiên hãy đến thăm phụ huynh và sau đó là trẻ em bên trái và bên phải.
- Vượt qua Đơn đặt hàng - thăm trẻ bên trái, sau đó đến phụ huynh và trẻ em bên phải.
- Qua Đơn đặt hàng - thăm con bên trái, sau đó đến con bên phải, rồi đến cha mẹ.
Ví dụ cho bốn phép duyệt của cây tìm kiếm nhị phân:
- Đặt trước - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Hình thể hiện thứ tự các nút được truy cập. Số 1 là nút đầu tiên trong một đường truyền cụ thể và 7 là nút cuối cùng.
Các đường truyền chung này có thể được biểu diễn dưới dạng một thuật toán duy nhất, giả sử rằng mỗi nút được truy cập ba lần. Chuyến tham quan Euler là một cuộc dạo chơi quanh một cây nhị phân nơi mỗi cạnh được coi như một bức tường mà người dùng không thể vượt qua. Trong bước đi này, mỗi nút sẽ được truy cập ở bên trái, bên dưới hoặc bên phải. Chuyến tham quan Euler, thăm các nút ở bên trái, khiến giới từ bị bỏ qua. Khi các nút bên dưới được truy cập, chúng sẽ được duyệt theo thứ tự. Và khi các nút ở bên phải được truy cập - lấybỏ qua từng bước.
Điều hướng và gỡ lỗi
Để điều hướng cây dễ dàng hơn, hãy tạo các hàm trước tiên kiểm tra xem chúng là con bên trái hay bên phải. Để thay đổi vị trí của một nút, phải dễ dàng truy cập vào con trỏ tại nút cha. Việc triển khai đúng một cây là rất khó, vì vậy bạn cần biết và áp dụng các quy trình gỡ lỗi. Cây tìm kiếm nhị phân có triển khai thường có các con trỏ không thực sự chỉ ra hướng di chuyển.
Để tìm ra tất cả điều này, một hàm được sử dụng để kiểm tra xem cây có thể đúng hay không và giúp tìm ra nhiều lỗi. Ví dụ, nó kiểm tra xem nút cha có phải là nút con hay không. Với khẳng định (is_wellformed (root)), nhiều lỗi có thể bị bắt sớm. Sử dụng một vài điểm ngắt nhất định trong hàm này, bạn cũng có thể xác định chính xác con trỏ nào sai.
Hàm Konsolenausgabe
Chức năng này chuyển toàn bộ cây vào bảng điều khiển và do đó rất hữu ích. Thứ tự mà mục tiêu đầu ra của cây được thực hiện là:
- Để thực hiện việc này, trước tiên bạn cần xác định thông tin nào sẽ được xuất qua nút.
- Và bạn cũng cần biết chiều rộng và chiều cao của cây là bao nhiêu để chừa khoảng trống.
- Các hàm sau tính toán thông tin này cho cây và mỗi cây con. Vì bạn chỉ có thể ghi từng dòng vào bảng điều khiển, bạn cũng sẽ cần in từng dòng trên cây.
- Bây giờ chúng ta cần một cách khác để rút tiềntoàn bộ cây, không chỉ từng dòng.
- Với sự trợ giúp của hàm kết xuất, bạn có thể đọc cây và cải thiện đáng kể thuật toán đầu ra, liên quan đến tốc độ.
Tuy nhiên, chức năng này sẽ khó sử dụng trên cây lớn.
Sao chép hàm tạo và hàm hủy
Bởi vì cây không phải là một cấu trúc dữ liệu tầm thường, tốt hơn nên triển khai một hàm tạo sao chép, một hàm hủy và một toán tử gán. Hàm hủy dễ thực hiện một cách đệ quy. Đối với những cây rất lớn, nó có thể xử lý "đống đổ tràn". Trong trường hợp này, nó được lập công thức lặp đi lặp lại. Ý tưởng là loại bỏ chiếc lá đại diện cho giá trị nhỏ nhất của tất cả các lá, vì vậy nó nằm ở phía bên trái của cây. Việc cắt bỏ những chiếc lá đầu tiên sẽ tạo ra những chiếc lá mới và cây sẽ thu nhỏ lại cho đến khi cuối cùng không còn tồn tại.
Phương thức tạo bản sao cũng có thể được thực thi đệ quy, nhưng hãy cẩn thận nếu trường hợp ngoại lệ được ném ra. Nếu không, cây sẽ nhanh chóng trở nên khó hiểu và dễ bị lỗi. Đó là lý do tại sao phiên bản lặp lại được ưu tiên. Ý tưởng là đi qua cây cũ và cây mới, như bạn làm trong trình hủy, sao chép tất cả các nút nằm trong cây cũ nhưng không phải nút mới.
Với phương pháp này, việc triển khai cây tìm kiếm nhị phân luôn ở trạng thái lành mạnh và có thể bị hủy bởi bộ hủy ngay cả khi ở trạng thái chưa hoàn chỉnh. Nếu một ngoại lệ xảy ra, tất cả những gì bạn cần làm là ra lệnh cho bộ hủy xóa cây bán thành phẩm. điều hành viên phân côngcó thể dễ dàng thực hiện bằng cách sử dụng Sao chép & Hoán đổi.
Tạo cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân tối ưu sẽ cực kỳ hiệu quả nếu được quản lý đúng cách. Một số quy tắc cho cây tìm kiếm nhị phân:
- Một nút cha có nhiều nhất 2 nút con.
- Nút con bên trái luôn nhỏ hơn nút cha.
- Một nút con hợp lệ luôn lớn hơn hoặc bằng nút cha.
Mảng sẽ được sử dụng để xây dựng cây tìm kiếm nhị phân:
- Một mảng số nguyên cơ sở gồm bảy giá trị theo thứ tự không được sắp xếp.
- Giá trị đầu tiên trong mảng là 10, vì vậy bước đầu tiên trong việc xây dựng cây là tạo một nút gốc 10, như được hiển thị ở đây.
- Với một tập hợp các nút gốc, tất cả các giá trị khác sẽ là con của nút này. Tham khảo các quy tắc, bước đầu tiên cần thực hiện để thêm 7 vào cây là so sánh nó với nút gốc.
- Nếu giá trị 7 nhỏ hơn 10, nó sẽ trở thành nút con bên trái.
- Nếu giá trị 7 lớn hơn hoặc bằng 10, nó sẽ di chuyển sang phải. Vì 7 được biết là nhỏ hơn 10, nó được chỉ định là nút con bên trái.
- Thực hiện một cách đệ quy các phép so sánh cho từng phần tử.
- Theo cùng một mẫu, thực hiện so sánh tương tự với giá trị thứ 14 trong mảng.
- So sánh giá trị 14 với nút gốc 10, biết rằng 14 là nút con đúng.
- Dạo qua mảng,đến với 20.
- Bắt đầu bằng cách so sánh mảng với 10, chọn mảng nào lớn hơn. Vì vậy, hãy di chuyển sang bên phải và so sánh nó với 14, anh ấy hơn 14 tuổi và không có con ở bên phải.
- Bây giờ có giá trị là 1. Theo cùng một mẫu với các giá trị khác, so sánh 1 với 10, di chuyển sang trái và so sánh với 7 và cuối cùng là con 1 bên trái của nút thứ 7.
- Nếu giá trị là 5, hãy so sánh nó với 10. Vì 5 nhỏ hơn 10, hãy chuyển sang bên trái và so sánh nó với 7.
- Biết rằng 5 nhỏ hơn 7, hãy tiếp tục xuống cây và so sánh 5 với 1 giá trị.
- Nếu 1 không có nút con và 5 lớn hơn 1, thì 5 là nút con hợp lệ của 1 nút.
- Cuối cùng chèn giá trị 8 vào cây.
- Khi 8 nhỏ hơn 10, hãy di chuyển nó sang trái và so sánh với 7, 8 lớn hơn 7, vì vậy hãy di chuyển nó sang phải và hoàn thành cây, làm cho 8 trở thành con thích hợp của 7.
Nhận và đánh giá sự sang trọng đơn giản của cây tìm kiếm nhị phân tối ưu. Giống như nhiều chủ đề trong lập trình, sức mạnh của cây tìm kiếm nhị phân đến từ khả năng phân giải dữ liệu thành các thành phần nhỏ có liên quan. Từ bây giờ, bạn có thể làm việc với toàn bộ tập dữ liệu một cách có tổ chức.
Các vấn đề tiềm ẩn về tìm kiếm nhị phân
Cây tìm kiếm nhị phân rất tuyệt, nhưng có một số lưu ý cần lưu ý. Chúng thường chỉ hiệu quả nếu chúng được cân bằng. Cây cân bằng là cây trong đósự khác biệt giữa chiều cao của các cây con của bất kỳ nút nào trong cây nhiều nhất là một. Hãy xem một ví dụ có thể giúp làm rõ các quy tắc. Hãy tưởng tượng rằng mảng bắt đầu là có thể sắp xếp.
Nếu bạn cố gắng chạy thuật toán cây tìm kiếm nhị phân trên cây này, nó sẽ hoạt động chính xác như thể nó chỉ lặp qua mảng cho đến khi tìm thấy giá trị mong muốn. Sức mạnh của tìm kiếm nhị phân nằm ở khả năng nhanh chóng lọc ra các giá trị không mong muốn. Khi cây không cân đối, nó sẽ không mang lại lợi ích như cây cân bằng.
Điều rất quan trọng là phải kiểm tra dữ liệu mà người dùng đang làm việc với khi tạo cây tìm kiếm nhị phân. Bạn có thể tích hợp các quy trình như ngẫu nhiên hóa mảng trước khi triển khai cây tìm kiếm nhị phân cho các số nguyên để cân bằng.
Ví dụ tính toán tìm kiếm nhị phân
Chúng ta cần xác định loại cây nào sẽ cho kết quả nếu 25 được chèn vào cây tìm kiếm nhị phân sau:
10
/
/
5 15
/ /
/ /
2 12 20
Khi chèn x vào cây T chưa chứa x, khóa x luôn được đặt trong một lá mới. Liên quan đến điều này, cây mới sẽ trông giống như:
10
/
/
5 15
/ /
/ /
2 12 20
25
Bạn sẽ nhận được loại cây gì nếu bạn chèn số 7 vào cây tìm kiếm nhị phân sau?
10
/
/
5 15
/ /
/ /
2 12 20
Trả lời:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Cây tìm kiếm nhị phân có thể được sử dụng để lưu trữ bất kỳ đối tượng nào. Ưu điểm của việc sử dụng cây tìm kiếm nhị phân thay vì danh sách được liên kết là nếu cây được cân bằng hợp lý và giống cây "đầy đủ" hơn là cây "tuyến tính", các thao tác chèn, tìm kiếm và xóa đều có thể được triển khai để chạy trong O (log N) thời gian.
