Java는 이진 검색 트리 검색, 삽입, 삭제 및 탐색에 대한 그래픽 세부 정보를 구현합니다.-java지도 시간-php.cn

이 글에서는 주로 Java로 구현된 이진 검색 트리의 검색, 삽입, 삭제, 순회 등을 소개합니다. 참조값이 아주 좋습니다.

최근 JDK1.8에서 HashMap의 구체적인 구현에 대해 읽어보고 싶은데 HashMap의 구현이 red-black을 사용하기 때문입니다. tree이므로 먼저 red-black tree에 대한 관련 지식을 복습할 필요가 있다고 생각하여 이번 에세이 메모를 작성하게 되었습니다. 혹시 틀린 부분이 있으면 지적해 주시기 바랍니다~

Red-black tree를 배우려면 이진 검색 트리로부터 학습이 필요하다고 생각합니다. 학습을 시작하려면 이 에세이에서는 이진 검색 트리의 검색, 삽입, 삭제, 순회 등을 구현하는 Java를 주로 소개합니다.

이진 검색 트리는 다음 네 가지 조건을 충족해야 합니다.

어떤 노드의 왼쪽 하위 트리가 비어 있지 않으면 해당 노드에 있는 모든 노드의 값이 왼쪽 하위 트리는 해당 루트 노드 값보다 작습니다.

어떤 노드의 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리에 있는 모든 노드의 값이 해당 루트 값보다 큽니다. node;

모든 노드의 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리입니다.

동일한 키 값을 가진 노드가 없습니다.

이진 검색 트리 예:

그림 1

그림 기반 다음 1에서는 이진 검색 트리의 관련 작업을 소개합니다.

우선 Node 객체와 관련된 클래스가 있어야 합니다.

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}

로그인 후 복사

Node 클래스에는 트리에서 해당 노드의 위치를 결정하는 데 사용되는 키 값이 포함되어 있습니다. 저장되며 두 참조의 왼쪽 및 오른쪽 하위 노드에 대한 포인트도 포함합니다.

다음으로 검색 트리의 해당 클래스를 살펴보겠습니다.

class Tree {
 Node root;//保存树的根
 public Node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
 }
 public void preOrder(Node rootNode) {//先序遍历树
 }
 public void inOrder(Node rootNode) {//中序遍历树
 }
 public void postOrder(Node rootNode) {//后序遍历树
 }
}

로그인 후 복사

클래스의 트리를 나타내는 프레임워크에는 검색, 삽입이 포함됩니다. , 순회 및 삭제 중 노드 삭제 작업이 가장 복잡한 해당 방법을 하나씩 소개합니다.

1. 노드 찾기

이진 검색 트리 정의의 특수성으로 인해 입력 키 값을 기준으로 루트부터 비교하면 됩니다. 보다 작은 경우 루트의 키 값을 루트의 왼쪽 하위 트리와 비교하고, 루트보다 큰 키 값을 루트의 오른쪽 하위 트리와 비교하는 식으로 발견되면 해당 노드를 찾습니다. 반환되고, 그렇지 않으면 null이 반환됩니다.

public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
}

로그인 후 복사

2. 노드 삽입

은 이진 검색의 특수성으로 인해 검색 작업과 유사합니다. 삽입된 노드도 루트 노드부터 비교해야 하며, 루트 노드보다 작으면 루트 노드의 왼쪽 하위 트리와 비교됩니다. 오른쪽 하위 트리가 비어 있거나 오른쪽 하위 트리가 비어 있을 때까지 해당 노드에 삽입합니다. 빈 위치의 경우 비교 과정에서 상위 노드의 정보 저장 여부와 위치에 주의해야 합니다. 삽입된 것은 부모 노드의 왼쪽 하위 트리 또는 오른쪽 하위 트리이므로 올바른 위치에 삽입될 수 있습니다.

public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
}

로그인 후 복사

3. 이진 검색 트리 순회

순회 작업은 일반 바이너리 순회와 완전히 동일합니다. 트리이므로 자세히 설명하지 않습니다.

public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }

로그인 후 복사

4. 지정된 노드를 삭제합니다.

이진 검색 트리에서 노드를 삭제하는 것은 복잡하며 다음 세 가지 상황으로 나눌 수 있습니다.

1. 삭제할 노드는 리프 노드이므로 직접 삭제할 수 있습니다.

public boolean delete(int key) {
 Node currentNode = root;//用来保存待删除节点
 Node parentNode = root;//用来保存待删除节点的父亲节点
 boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } 
 ......
 }

로그인 후 복사

2. 삭제할 노드에는 하위 노드가 하나만 있습니다

예를 들어 그림 1에서 키 값이 11인 노드를 삭제하려면 키 값이 13인 노드의 왼쪽 자식을 키 값이 12인 노드로 가리키기만 하면 노드 삭제 목적을 달성할 수 있습니다. 키 값이 11입니다.

위 분석을 통해 얻은 코드는 다음과 같습니다(위 삭제 메소드 뒤에 줄임표가 붙음).

else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } 
 ......

로그인 후 복사

3. 대기 노드 삭제에는 왼쪽 및 오른쪽 하위 노드가 모두 있습니다.

예를 들어 그림 1에서 키 값이 10인 노드를 삭제하면 키 값이 10인 노드를 순서대로 후속 노드(노드 11) 노드, 키 값이 10인 노드의 순차 후속 노드를 삭제합니다. 순차 순회 관련 규칙에 따라 키 값이 10은 오른쪽 하위 트리에서 가장 작은 키 값을 가진 노드여야 합니다. 따라서 순서대로의 후속 노드는 자식 노드를 포함하지 않거나 오른쪽 자식 노드를 하나만 포함해야 합니다. 위의 2. 그림 1에서 키 값이 10인 노드의 직접 순서 후속 노드는 11이고, 노드 11에는 오른쪽 자식 12가 포함되어 있습니다.

따라서 그림 1에서 키 값이 10인 노드를 삭제하는 작업은 다음 단계로 나누어집니다.

a. 키 값 10(즉, 오른쪽 하위 트리에서 가장 작은 값을 가진 노드 11)을 선택하고 이 직접 순서 후속 노드를 삭제합니다.

private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
}

로그인 후 복사

b. 삭제되었습니다. 값입니다. (2번의 경우 생략부호 뒤)

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

로그인 후 복사

지정 노드 삭제 작업이 종료됩니다.

마지막으로 전체 코드와 간단한 테스트 코드 및 테스트 결과가 제공됩니다.

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}
class Tree {
 Node root;
 public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
 }
 public boolean delete(int key) {
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {
 //要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
 }
 public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
 public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
 public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }
}
public class BinarySearchTreeApp {
 public static void main(String[] args) {
 Tree tree = new Tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 System.out.println("删除前遍历结果");
 tree.inOrder(tree.root);//中序遍历操作
 System.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inOrder(tree.root);
 }
}

로그인 후 복사

테스트 결과: