1. 개념
이진 검색 트리는 또한 이진 분류 트리가됩니다. 노드에 두 개의 자식 노드가 있으면 만족해야한다는 특성이 있습니다. 왼쪽 하위 노드의 값은 노드 값보다 작아야하며 오른쪽 하위 노드의 값은 노드 값보다 크기가 커야합니다. 비 기본 유형의 비교를 위해 비교기 인터페이스를 구현할 수 있습니다. 이 기사에서는 int 유형 데이터가 작동에 사용됩니다.
이진 트리를 구현하려면 증가로 시작해야합니다. 나무를 만들어서 만 다른 작업을 사용할 수 있습니다.
2. 이진 검색 트리의 구성
이진 나무의 증가에 대해 이야기 할 때 먼저 노드를 나타내는 클래스를 구축해야합니다. 노드의 클래스에는 몇 가지 속성, 노드 값, 부모 노드, 왼쪽 노드 및 노드의 오른쪽 노드가 있습니다. 코드는 다음과 같습니다
정적 클래스 노드 {노드 부모; 노드 왼치; 노드 우측 차일; int val; public node (노드 부모, 노드 왼쪽 차일드, 노드 오른치, int val) {super (); this.parent = 부모; this.leftChild = LeftChild; this.rightchild = Rightchild; this.val = val; } public node (int val) {this (null, null, null, val); } public node (노드 노드, int val) {this (노드, null, null, val); }}여기서 우리는 내부 클래스 쓰기 방법을 사용합니다. 노드 값을 구축 한 후 전체 트리를 구축합니다. 트리에는 먼저 루트 노드가 있어야하며 나머지 하위 노드로 확장해야합니다. 이 트리에는 기본 루트 노드 루트 및 트리의 요소 크기와 같은 몇 가지 속성이 있습니다. 이 두 속성을 사용하는 경우 비교기 속성이 추가 될 수 있거나 기본 구현이 제공 될 수 있습니다. 특정 코드는 다음과 같습니다
공개 클래스 SearchBinaryTree {개인 노드 루트; 개인 INT 크기; public searchBinaryTree () {super (); }}3. 추가
요소를 추가 할 때는 루트 노드의 초기화를 고려해야합니다. 일반적으로 두 가지 유형이 있습니다.이 클래스의 생성자가 초기화되면 루트 노드 루트가 초기화됩니다. 두 번째는 첫 번째 요소가 추가 될 때 루트 노드를 추가하는 것입니다. 둘 다 이론적으로 작동하지만 일반적으로 두 번째 게으른 하중 형태를 사용합니다.
요소를 추가 할 때 고려해야 할 몇 가지 상황이 있습니다.
1. 추가 할 때 루트가 초기화되는지 여부를 결정하십시오. 초기화되지 않으면 초기화됩니다. 루트 노드에 값을 할당하고 하나의 크기를 추가하십시오.
2. 바이너리 트리 검색 트리는 루트 노드 값이 왼쪽 노드보다 크고 오른쪽 노드보다 작음을 만족시키기 때문에 삽입 된 값은 먼저 루트 노드와 비교해야합니다. 큰 경우 오른쪽 하위 트리에서 검색하십시오. 작은 경우 왼쪽 하위 트리에서 검색하십시오. 어린이 노드까지.
여기에서 삽입 구현은 하나의, 재귀, 2, 반복 (즉, 루프 모드를 통해)의 두 가지 유형을 채택 할 수 있습니다.
3.1. 재귀 버전 삽입
public boolean add (int val) {if (root == null) {root = new Node (val); 크기 ++; 진실을 반환하십시오. } node node = getAdapternode (root, val); 노드 newnode = 새로운 노드 (val); if (node.val> val) {node.leftchild = newnode; newnode.parent = 노드; } else if (node.val <val) {node.rightchild = newnode; newnode.parent = 노드; } else {// 시간에 대한 처리 없음} size ++; 19 반환 true; } /*** 노드의 상위 노드를 삽입 할 수 있습니다. 부모 노드는 다음 상태 중 하나를 만족합니다.* 1. 부모 노드는 하위 노드* 2입니다. * 5. 부모 노드가 비어 있으면* 위 5 건 중 하나가 만족되면 재귀 적으로 중지됩니다. * @param node * @param val * @return */ private node getAdapternode (Node Node, int val) {if (node == null) {return node; } // 왼쪽 하위 트리에 삽입하지만 왼쪽 하위 트리가 없습니다. if (node.val> val && node.leftchild == null) {return node; } // 오른쪽 서브 트리에 삽입하지만 오른쪽 하위 트리는 없으며 (node.val <val && node.rightchild == null) {return node; } // 오른쪽 서브 트리에 삽입하지만 오른쪽 하위 트리는 없으며 (node.val <val && node.rightchild == null) {return node; } // 오른쪽 서브 트리에 삽입하지만 오른쪽 하위 트리는 없으며 (node.val <val && node.rightchild == null) {return node; } // 오른쪽 하위 트리에 삽입하지만 오른쪽 하위 트리는 없으며 (node.leftchild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftChild! = null) {return getAdaptAnde (node.leftChild, Val); } else if (node.val <val && node.rightchild! = null) {return getAdaptAnde (node.rightchild, val); } else {return 노드; }}재귀를 사용하고 먼저 재귀의 종말점을 찾은 다음 전체 문제를 하위 문제로 바꿉니다. 위의 코드에서 논리는 대략적으로 다음과 같습니다. 먼저 루트 노드가 초기화되는지 여부를 결정하고 초기화되지 않으면 초기화되고 완료되면 기능을 사용하여 조정 된 노드를 얻습니다. 그런 다음 값을 삽입하십시오.
3.2. 반복 버전
Public Boolean Put (int val) {return putval (루트, val); } private boolean putval (노드 노드, int val) {if (node == null) {// 루트 노드 초기화 = 새 노드 (val); 루트 = 노드; 크기 ++; 진실을 반환하십시오. } 노드 온도 = 노드; 노드 P; int t; / ** * 루프 반복을 통해 최상의 노드를 얻으십시오. */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftChild; } else if (t <0) {temp = temp.rightchild; } else {temp.val = val; 거짓을 반환합니다. }} while (temp! = null); 노드 NewNode = 새 노드 (P, val); if (t> 0) {p.leftchild = newnode; } else if (t <0) {p.rightchild = newnode; } size ++; 진실을 반환하십시오. }원리는 실제로 재귀와 동일하며, 이는 최고의 노드를 얻고 해당 노드에서 작동하는 것입니다.
성능 측면에서, 그것은 확실히 최고의 반복 버전이므로 일반적으로 데이터에서 작동하는 반복 버전입니다.
4. 삭제
이진 검색 트리의 작동에서 삭제가 가장 복잡하며 고려해야 할 상황이 상대적으로 많다고 말할 수 있습니다. 기존의 방식으로 바이너리 검색 트리에서 노드를 삭제하면 다음 네 가지 상황을 확실히 생각할 것입니다.
1. 삭제할 노드에는 위 그림의 D, E 및 G 노드에 표시된 것처럼 왼쪽 및 오른쪽 하위 노드가 없습니다.
2. 삭제할 노드는 노드 B와 같은 왼쪽 하위 노드 만 있습니다.
3. 삭제할 노드는 F 노드와 같은 오른쪽 하위 노드입니다.
4. 삭제할 노드에는 왼쪽 자식 노드와 A 및 C 노드와 같은 오른쪽 하위 노드가 모두 있습니다.
처음 세 가지 상황에서는 비교적 간단하지만 네 번째 상황은 복잡하다고 말할 수 있습니다. 첫 번째를 분석합시다
예를 들어 노드 D가 삭제되면 노드 B의 왼쪽 하위 노드를 NULL로 설정할 수 있고 노드 G가 삭제되면 노드 F의 오른쪽 하위 노드를 NULL로 설정할 수 있습니다. 어느 쪽을 설정 해야하는지, 삭제 된 노드가 어느쪽에 있는지 확인하십시오.
노드 b를 삭제하는 두 번째 방법은 노드 a의 왼쪽 노드를 노드 D로 설정하면 노드 d의 부모 노드를 A로 설정하면됩니다.
세 번째 유형은 두 번째 유형과 동일합니다.
앞에서 언급 한 바와 같이 약간 복잡한 네 번째 유형은 예를 들어 C 노드를 삭제하는 것입니다. F 노드의 부모 노드를 노드 A로 설정하고 F 노드의 왼쪽 노드를 노드 e로 설정하고 a의 오른쪽 노드를 노드 F로 설정하고 (즉, e의 상위 노드를 노드 F로 설정하고, 즉 F 노드 C 노드를 대체하고, 직접 대체). 그래서 어떤 것을 사용해야합니까? 삭제 노드가 루트 노드 인 경우 어떻게 삭제해야합니까?
네 번째 경우에는 다음과 같이 생각할 수 있습니다. C 또는 노드의 후속 노드를 찾고 후속 노드를 삭제하고 후속 노드의 값을 C 또는 노드 값으로 설정하십시오. 후속 노드의 개념을 먼저 보충합시다.
전체 트리의 노드의 후속 노드는 만족해야합니다. 노드의 가치가있는 노드 세트에서 가장 작은 값을 가진 노드는 후속 노드입니다. 물론 후속 노드는 없을 수 있습니다.
그러나 네 번째 경우에는 후속 노드가 존재하고 오른쪽 하위 트리에 있어야하며, 하위 노드가 하나만 있거나 하위 노드가없는 경우 중 하나를 충족시킵니다. 후속 노드가 C 노드보다 크고 C 노드의 왼쪽 및 오른쪽 하위 섹션이 존재하기 때문에 특정 이유는 이에 대해 생각할 수 있습니다. 오른쪽 하위 트리의 왼쪽 하위 섹션에 존재해야합니다. 예를 들어, C의 후속 노드는 F이고 A의 후속 노드는 E입니다.
위의 분석을 통해 구현은 비교적 간단하며 코드는 다음과 같습니다.
public boolean delete (int val) {노드 노드 = getNode (val); if (node == null) {return false; } node parent = node.parent; 노드 LeftChild = node.leftChild; 노드 rightchild = node.rightchild; // 다음의 모든 부모 노드는 비어 있습니다. 이는 삭제 된 노드가 루트 노드임을 의미합니다. (leftchild == null && rightchild == null) {// hild nodes if (parent! = null) {if (parent.leftchild == node) {parent.leftchild = null; } else if (parent.rightchild == 노드) {parent.rightchild = null; }} else {// 상위 노드가 존재하지 않으므로 삭제 된 노드가 루트 노드 root = null입니다. } node = null; 진실을 반환하십시오. } else if (leftchild == null && rightchild! = null) {// 오른쪽 노드 만 if (parent! = null && parent.val> val) {// 노드 위치는 부모 노드의 왼쪽입니다. } else if (parent! = null && parent.val <val) {// 상위 노드가 있고 노드 위치는 부모 노드 부모의 오른쪽입니다. } else {root = rightchild; } node = null; 진실을 반환하십시오. } else if (leftchild! = null && rightchild == null) {// 왼쪽 노드 만 if (parent! = null && parent.val> val) {// 상위 노드가 있고 노드 위치는 부모 노드의 왼쪽입니다. } else if (parent! = null && parent.val <val) {// 상위 노드가 있고 노드 위치는 부모 노드 부모의 오른쪽입니다. } else {root = LeftChild; } true를 반환합니다. } else if (leftChild! = null && rightchild! = null) {// 두 하위 노드에는 Node convertor = getSuccessor (node); //이 경우 후속 노드 int temp = contintor.val이 있어야합니다. 부울 삭제 = 삭제 (임시); if (delete) {node.val = temp; } confleror = null; 진실을 반환하십시오. } false를 반환합니다. } /*** 노드 노드의 후속 노드를 찾으십시오* 1. 먼저 노드에 오른쪽 하위 트리가 있는지 여부를 결정하십시오. 그렇다면 오른쪽 노드의 왼쪽 하위 트리에서 후속 노드를 찾으십시오. 그렇지 않은 경우 다음 단계로 진행하십시오* 2. 노드의 상위 노드를 찾으십시오. 상위 노드의 오른쪽 노드가 노드와 동일하면 부모 노드가 널이거나 노드와 같지 않은 오른쪽 노드를 찾을 때까지 부모 노드 *를 계속 찾으십시오. * 이유, 후속 노드는 노드보다 커야합니다. 오른쪽 하위 트리가있는 경우, 후속 노드는 오른쪽 하위 트리에 있어야합니다. 이것이 첫 번째 단계의 이유입니다* 올바른 하위 트리가 없으면 노드의 할아버지 노드 (즉, 노드의 상위 노드 또는 부모 노드 위의 부모 노드)가있을 수도 있습니다. * 반복적으로 검색하면 노드를 반환하고 아니오가 있으면 null * @param node * @return */ private node getSuccessor (node node) {if (node.rightchild! = null) {node rightchild = node.rightchild; while (rightchild.leftchild! = null) {rightchild = rightchild.leftchild; } Return Rightchild; } node parent = node.parent; while (parent! = null && (node == parent.rightchild)) {node = parent; 부모 = parent.parent; } 반환 부모; }특정 논리는 위의 분석을 참조하십시오. 나는 여기서 텍스트를 설명하지 않을 것입니다.
이 구현 외에도 알고리즘 소개에 또 다른 구현이 제공됩니다.
공개 부울 제거 (int val) {노드 노드 = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. 왼쪽 노드가 존재하지 않으면 오른쪽 노드가 두 가지 상황을 포함하여 존재할 수 있습니다. 두 노드 모두 존재하지 않으며 오른쪽 노드 만 이식 (노드, 노드. } else if (node.rightchild == null) {// 2. 좌파 자식이 존재하며 오른쪽 노드는 이식이 없습니다 (노드, 노드 .leftChild). } else {// 3. 두 노드에는 노드 후속기가 있습니다. 이식 (후임자, 후임자. rightchild); // 후임자를 후임자의 올바른 자식 노드로 바꾸십시오. rightchild = node.rightchild; // 후속 노드의 오른쪽 노드에 노드 노드의 오른쪽 하위 트리를 후속 노드에 따라 후임자와 후임자와 유사합니다. 이식 (노드, 후임자); 후계자 .leftchild = node.leftchild; 후계자 .leftChild.parent = 후임자; } true를 반환합니다. } /*** 노드 노드* @param root node node* @param node 노드를 삭제하기 위해 하위 노드 노드 하위 노드 하위 노드 하위 노드 아동 void Transplant (node node, node child) { /*** 1을 삭제하기 위해 하위 노드 노드* @param root node node로 교체하십시오. { /*** 1. 그 다음에 노드가 존재하지 않는지* 2로 교체하지 않습니다. 단계* 2. 노드 노드가 상위 노드의 자녀임을 결정합니다 (즉, 노드가 오른쪽 노드인지 왼쪽 노드인지 결정)* 결과를 얻은 후 하위 노드를 노드 노드로 교체 한 후 노드 노드가 왼쪽 노드 인 경우, 자식이 왼쪽 노드가되면 오른쪽 노드가됩니다. 노드*/ if (node.parent == null) {this.root = child; } else if (node.parent.leftchild == 노드) {node.parent.leftchild = child; } else if (node.parent.rightchild == 노드) {node.parent.rightchild = child; } if (child! = null) {child.parent = node.parent; }}5. 검색
검색은 또한 비교적 간단하지만 실제로는 추가 될 때 구현되었습니다. 실제 상황 에서이 부분은 별도의 방법에서 추출 할 수 있습니다. 코드는 다음과 같습니다
공개 노드 getNode (int val) {노드 온도 = 루트; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftChild; } else if (t <0) {temp = temp.rightchild; } else {return temp; }} while (temp! = null); 널 리턴; }6. 이진 검색 트리 트래버스
이진 검색 트리의 특성을 이해 한 후, 그 중간 순서 트래버스는 중소형에서 큰 것까지 순서대로 배열된다는 것이 분명합니다. 다음은 여기에 제공된 중간 순서 트래버스 코드입니다
public void print () {print (root); } private void print (노드 루트) {if (root! = null) {print (root.leftChild); System.out.println (root.val); // 위치가 중간에 있으면 순서가 중간에 있습니다. 그것이 정면에 있다면, 그것은 선례에있다. 그렇지 않으면 후속 인쇄 (root.rightchild); }} 요약
위는 편집기가 소개 한 이진 검색 트리 함수의 Java 구현입니다. 모든 사람에게 도움이되기를 바랍니다. 궁금한 점이 있으면 메시지를 남겨주세요. 편집자는 제 시간에 모든 사람에게 답장 할 것입니다!