Màn dạo đầu
Bài viết này là về cây tìm kiếm nhị phân. Gần đây tôi đã viết một bài báo về Ở đó tôi không thực sự chú ý đến cây nhị phân, bởi vì các phương pháp tìm kiếm, chèn, xóa không phù hợp. Bây giờ tôi quyết định viết một bài báo về cây cối. Có lẽ chúng ta sẽ bắt đầu.
Cây là một cấu trúc dữ liệu bao gồm các nút được kết nối bởi các cạnh. Có thể nói rằng cây là trường hợp đặc biệt của đồ thị. Đây là một cây ví dụ:
Đây không phải là cây tìm kiếm nhị phân! Tất cả mọi thứ là dưới cắt!
Thuật ngữ
Gốc
Gốc cây là nút trên cùng. Trong ví dụ, đây là nút A. Trong cây, chỉ có một đường dẫn có thể dẫn từ gốc đến bất kỳ nút nào khác! Trong thực tế, bất kỳ nút nào cũng có thể được coi là gốc của cây con tương ứng với nút này.
Cha mẹ/con cái
Tất cả các nút ngoại trừ nút gốc có chính xác một cạnh dẫn đến một nút khác. Nút phía trên nút hiện tại được gọi là cha mẹ nút này. Một nút nằm bên dưới nút hiện tại và được kết nối với nó được gọi là hậu duệ nút này. Hãy lấy một ví dụ. Lấy nút B, thì nút cha của nó sẽ là nút A và các nút con của nó sẽ là nút D, E và F.
Lá
Nút không có nút con được gọi là lá của cây. Trong ví dụ, các nút D, E, F, G, I, J, K sẽ là các lá.
Đây là thuật ngữ cơ bản. Các khái niệm khác sẽ được thảo luận sau. Vì vậy, cây nhị phân là cây mà mỗi nút sẽ có không quá hai nút con. Như bạn đã đoán, cây trong ví dụ sẽ không phải là cây nhị phân, bởi vì các nút B và H có nhiều hơn hai nút con. Đây là một ví dụ về cây nhị phân:
Các nút của cây có thể chứa bất kỳ thông tin nào. Cây tìm kiếm nhị phân là cây nhị phân có các thuộc tính sau:
- Cả cây con bên trái và bên phải đều là cây tìm kiếm nhị phân.
- Tất cả các nút của cây con bên trái của một nút X tùy ý có giá trị khóa dữ liệu nhỏ hơn giá trị khóa dữ liệu của chính nút X.
- Tất cả các nút của cây con bên phải của một nút X tùy ý đều có giá trị khóa dữ liệu lớn hơn hoặc bằng giá trị khóa dữ liệu của chính nút X đó.
Ключ - một số đặc điểm của nút (ví dụ: một số). Cần có khóa để có thể tìm thấy phần tử của cây tương ứng với khóa này. Ví dụ về cây tìm kiếm nhị phân:
xem cây
Khi tôi tiếp tục, tôi sẽ bao gồm một số đoạn mã (có lẽ không đầy đủ) để cải thiện sự hiểu biết của bạn. Code đầy đủ sẽ ở cuối bài viết.
Cây được tạo thành từ các nút. Cấu trúc nút:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
Mỗi nút có hai nút con (rất có thể các nút con leftChild và/hoặc rightChild sẽ là null). Bạn có thể hiểu rằng trong trường hợp này, dữ liệu số là dữ liệu được lưu trữ trong nút; phím - phím nút.
Chúng tôi đã tìm ra nút thắt, bây giờ hãy nói về những vấn đề cấp bách về cây xanh. Sau đây, từ "cây" sẽ có nghĩa là khái niệm cây tìm kiếm nhị phân. Cấu trúc cây nhị phân:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Là một trường lớp, chúng ta chỉ cần gốc của cây, bởi vì từ gốc, sử dụng các phương thức getLeftChild() và getRightChild(), bạn có thể đến bất kỳ nút nào của cây.
thuật toán cây
tìm kiếm
Giả sử bạn có một cái cây được xây dựng. Làm cách nào để tìm phần tử bằng phím key? Bạn cần di chuyển tuần tự từ gốc xuống cây và so sánh giá trị của khóa với khóa của nút tiếp theo: nếu khóa nhỏ hơn khóa của nút tiếp theo thì chuyển sang con cháu bên trái của nút, nếu nhiều hơn - ở bên phải, nếu các phím bằng nhau - tìm thấy nút mong muốn! Mã có liên quan:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Nếu hiện tại trở thành null, thì phép lặp đã đi đến cuối cây (ở mức khái niệm, bạn đang ở một vị trí không tồn tại trong cây - con của một chiếc lá).
Xem xét hiệu quả của thuật toán tìm kiếm trên cây cân bằng (cây trong đó các nút được phân bố đồng đều hơn hoặc ít hơn). Sau đó, hiệu quả tìm kiếm sẽ là O(log(n)) và logarit cơ số 2. Hãy xem: nếu có n phần tử trong một cây cân bằng, thì điều này có nghĩa là sẽ có log(n) cấp cơ sở 2 của cây. Và trong quá trình tìm kiếm, đối với một bước của chu kỳ, bạn đi xuống một cấp độ.
chèn
Nếu bạn đã nắm được bản chất của tìm kiếm thì sẽ không khó để bạn hiểu được phần chèn. Bạn chỉ cần đi xuống lá của cây (theo quy tắc gốc được mô tả trong tìm kiếm) và trở thành hậu duệ của nó - trái hoặc phải, tùy thuộc vào phím. Thực hiện:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Trong trường hợp này, ngoài nút hiện tại, cần lưu trữ thông tin về cha của nút hiện tại. Khi hiện tại trở thành null, biến cha sẽ chứa trang tính mà chúng ta cần.
Hiệu quả chèn rõ ràng sẽ giống như hiệu quả tìm kiếm - O(log(n)).
Xóa
Xóa là thao tác phức tạp nhất sẽ cần được thực hiện với một cây. Rõ ràng là trước tiên cần phải tìm phần tử mà chúng ta sẽ loại bỏ. Nhưng sau đó thì? Nếu chúng ta chỉ đặt tham chiếu của nó là null, thì chúng ta sẽ mất thông tin về cây con có gốc là nút này. Phương pháp loại bỏ cây được chia thành ba trường hợp.
Trường hợp đầu tiên. Nút bị xóa không có con.
Nếu nút bị xóa không có nút con, điều đó có nghĩa đó là nút lá. Do đó, bạn có thể chỉ cần đặt các trường leftChild hoặc rightChild của cha mẹ thành null.
Trường hợp thứ hai. Nút bị xóa có một nút con
Vụ này cũng không khó lắm. Hãy quay lại ví dụ của chúng ta. Giả sử chúng ta cần xóa một phần tử có khóa 14. Đồng ý rằng vì nó là nút con bên phải của nút có khóa 10, nên bất kỳ phần tử con nào của nó (trong trường hợp này là nút bên phải) sẽ có khóa lớn hơn 10, vì vậy bạn có thể dễ dàng “cắt” nó khỏi cây và kết nối nút cha trực tiếp với nút con của nút bị xóa, tức là kết nối nút có khóa 10 với nút 13. Tình huống sẽ tương tự nếu chúng ta phải xóa một nút là nút con bên trái của nút cha. Hãy tự mình nghĩ về nó - một sự tương tự chính xác.
Trường hợp thứ ba. Nút có hai con
Trường hợp khó khăn nhất. Hãy xem một ví dụ mới.
Tìm kiếm người kế nhiệm
Giả sử chúng ta cần xóa nút bằng khóa 25. Chúng ta sẽ đặt ai vào vị trí của nó? Một trong những người theo ông (con cháu hoặc hậu duệ của con cháu) phải trở thành người kế vị(người sẽ thay thế nút bị xóa).
Làm thế nào để bạn biết ai nên là người kế vị? Theo trực giác, đây là nút trong cây có khóa lớn nhất tiếp theo từ nút bị xóa. Thuật toán như sau. Bạn cần đi đến nút con bên phải của nó (luôn luôn đến nút bên phải, vì người ta đã nói rằng khóa của nút kế vị lớn hơn khóa của nút bị xóa), sau đó đi qua chuỗi nút con bên trái của nút bên phải này đứa trẻ. Trong ví dụ này, chúng ta phải đi đến nút có khóa 35, sau đó đi xuống chuỗi con bên trái của nó đến lá - trong trường hợp này, chuỗi này chỉ bao gồm nút có khóa 30. Nói đúng ra, chúng tôi đang tìm kiếm nút nhỏ nhất trong tập hợp các nút lớn hơn nút mong muốn.
Mã phương pháp tìm kiếm người kế nhiệm:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
Mã hoàn chỉnh của phương thức xóa:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Độ phức tạp có thể xấp xỉ bằng O(log(n)).
Tìm cực đại/cực tiểu trong cây
Rõ ràng, làm thế nào để tìm giá trị tối thiểu / tối đa trong cây - bạn cần lần lượt đi qua chuỗi các phần tử bên trái / bên phải của cây; khi bạn đến lá, nó sẽ là phần tử tối thiểu/tối đa.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Độ phức tạp - O(log(n))
Bỏ qua đối xứng
Traversal là một lần truy cập vào từng nút của cây để làm điều gì đó với nó.
Thuật toán duyệt đối xứng đệ quy:
- Thực hiện một hành động trên con bên trái
- Thực hiện một hành động với chính mình
- Thực hiện một hành động trên đúng đứa trẻ
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Kết luận
Cuối cùng! Nếu tôi không giải thích điều gì đó hoặc có bất kỳ nhận xét nào, thì tôi đang chờ nhận xét. Như đã hứa, đây là mã hoàn chỉnh.
Nút.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
Cây nhị phân.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Thoái hóa thành O(n)
Nhiều bạn có thể nhận thấy: nếu bạn làm cho cây trở nên mất cân đối thì sao? Ví dụ: đặt các nút trong cây bằng các khóa tăng dần: 1,2,3,4,5,6... Khi đó cây sẽ phần nào gợi nhớ đến danh sách liên kết. Và vâng, cây sẽ mất cấu trúc cây và do đó làm giảm hiệu quả truy cập dữ liệu. Độ phức tạp của các thao tác tìm kiếm, chèn và xóa sẽ giống như độ phức tạp của danh sách liên kết: O(n). Theo tôi, đây là một trong những nhược điểm quan trọng nhất của cây nhị phân.
Chỉ những người dùng đã đăng ký mới có thể tham gia khảo sát. , xin vui lòng.
Tôi đã không truy cập Habré trong một thời gian khá dài và tôi muốn biết bạn muốn xem thêm những bài viết nào về chủ đề nào?
-
Cấu trúc dữ liệu
-
Các thuật toán (DP, đệ quy, nén dữ liệu, v.v.)
-
Ứng dụng cấu trúc dữ liệu và giải thuật trong thực tế cuộc sống
-
Lập trình ứng dụng android bằng Java
-
Lập trình ứng dụng web Java
2 người dùng bình chọn. 1 người dùng đã bỏ phiếu trắng.
Nguồn: www.habr.com