데이터 구조 - 이 진 검색 트 리 (Binary SearchTree) 의 실현
특징.
트 리 의 임의의 노드 X 는 왼쪽 트 리 의 모든 노드 값 보다 크 고 오른쪽 트 리 의 모든 노드 값 보다 작 습 니 다.(트 리 의 요소 가 서로 다 르 고 똑 같은 요소 값 이 존재 하지 않 는 다 고 가정 합 니 다)
BinarySearchTree
이번 구현 에 서 는 트 리 에 저 장 된 요소 에 대해 Comparable 인 터 페 이 스 를 실현 해 야 한 다 는 요구 가 없습니다.Comparator 와 Comparable 인 터 페 이 스 를 동시에 결합 했다.사용 자 는 이 진 트 리 를 구성 할 때 사용자 정의 비교 기 를 입력 하거나 비교 기 를 사용 하지 않 고 저 장 된 요소 에서 Comparable 인 터 페 이 스 를 실현 할 수 있 습 니 다 (이때 Comparable 인 터 페 이 스 는 반드시 실현 되 어야 합 니 다).
구성원 변수
private BinaryNode root; //두 갈래 검색 트 리 의 뿌리 노드 private Comparator cmp; /요소 의 사용자 정의 비교 기
구조 기
두 개의 구조 기 가 있 는데 그 중 하 나 는 인삼 을 함유 한 구조 기로 사용자 정의 비교 기 에 들 어 갈 수 있다.구조 기 에 서 는 주로 나무 뿌리 노드 를 초기 화 합 니 다.
public BinarySearchTree(){
this(null);
}
public BinarySearchTree(Comparator<T> cmp){
this.cmp = null;
}
함수.
상용 함수
public void setComparator(Comparator<T> cmp){
this.cmp = cmp;
}
public boolean isEmpty(){
return root == null;
}
public void clearTree(){
root = null;
}
내부 비교 방법 으로 두 수의 크기 를 비교 하고 결 과 를 되 돌려 줍 니 다.방법 에 서 는 사용자 정의 비교 기 가 있 는 지 여 부 를 판단 하고, 사용자 정의 비교 기 를 사용 하여 두 개의 크기 를 비교 하지 않 으 면 Comparable 인터페이스의 comparaTo 함 수 를 사용 하여 비교 합 니 다.
@SuppressWarnings("unchecked")
private int innerCompareTo(T lhs, T rhs){
if(cmp != null)
return cmp.compare(lhs, rhs);
else
return ((Comparable<T>)lhs).compareTo(rhs);
}
contains (): 트 리 에 어떤 요소 가 포함 되 어 있 는 지 찾 아 재 귀적 인 방법 으로 2 분 검색 합 니 다.2 분 검색 법: 찾 아야 할 값 x 와 현재 노드 값 을 비교 하고 노드 값 보다 작 으 면 왼쪽 하위 트 리 에서 계속 검색 합 니 다.x 가 현재 노드 보다 크 면 오른쪽 하위 트 리 에서 검색 합 니 다.루트 노드 위치 까지 반복 합 니 다. 일치 하 는 값 을 검색 하지 않 으 면 트 리 에 x 값 이 포함 되 지 않 습 니 다.
public boolean contains(T x){
return contains(x, root);
}
private boolean contains(T x, BinaryNode<T> tree){
if(tree == null)
return false;
/* x , */
int result = innerCompareTo(x, tree.element);
if(result < 0)
return contains(x, tree.left);
else if(result > 0)
return contains(x, tree.right);
/* result = 0, */
else
return true;
}
insert (): 요 소 를 삽입 합 니 다.모든 요 소 는 나무의 새로운 잎 노드 로 나무 에 삽입 되 어 있다.삽입 작업 의 평균 시간 복잡 도 는 O (logN) 이지 만 질서 있 는 요소 가 삽입 작업 을 하면 최 악의 상황 이 될 수 있 습 니 다. 시간 복잡 도 는 O (logN) 이 고 퇴화 된 이 진 검색 트 리 (링크 로 변 함) 를 얻 을 수 있 습 니 다. 이 럴 때 삭제 든 검색 작업 시간 복잡 도 는 O (N) 가 됩 니 다.
public void insert(T x){
root = insert(x, root);
}
private BinaryNode<T> insert(T x, BinaryNode<T> tree){
/* , */
if(tree == null)
return new BinaryNode<T>(x);
int result = innerCompareTo(x, tree.element);
if(result < 0)
tree.left = insert(x, tree.left);
else if(result > 0)
tree.right = insert(x, tree.right);
else{
// ，
}
return tree;
}
remove (): 요소 x 를 삭제 합 니 다.두 갈래 검색 트 리 의 삭제 작업 은 비교적 간단 하 다.삭제 할 노드 는 주로 다음 과 같은 몇 가지 상황 입 니 다. 1. 이 노드 가 존재 하지 않 고 삭제 에 실 패 했 습 니 다.2. 삭제 할 노드 가 잎 결점 이면 이 노드 를 직접 삭제 합 니 다.3. 노드 를 삭제 할 때 한 아이 가 있 습 니 다. 이 노드 를 삭제 하면 아이의 노드 를 부모 노드 에 되 돌려 주면 됩 니 다.4. 삭제 할 노드 에 두 명의 아이 가 있 는데 이런 상황 에서 상대 적 으로 복잡 하 다.일반적인 해결 방법 은 오른쪽 하위 트 리 의 최소 값 으로 노드 값 을 교체 한 다음 에 오른쪽 하위 트 리 의 최소 값 을 삭제 하면 됩 니 다 (이때 오른쪽 하위 트 리 의 최소 값 노드 에 왼쪽 아이 가 없 으 면 2, 3 상황 이 되 기 때 문 입 니 다).그러나 이런 요 소 를 삭제 하 는 방법 은 여러 번 조작 한 후에 나무의 불 균형 을 초래 할 수 있다. 즉, 오른쪽 나무의 높이 가 보편적으로 낮다.따라서 우 리 는 오른쪽 트 리 의 최소 값 을 무 작위 로 삭제 하거나 왼쪽 트 리 의 최대 값 을 삭제 하 는 방식 을 취 할 수 있다.
public void remove(T x){
root = remove(x, root);
}
private BinaryNode<T> remove(T x, BinaryNode<T> tree){
/* */
if(tree == null)
return null;
int result = innerCompareTo(x, tree.element);
/* */
if(result < 0)
tree.left = remove(x, tree.left);
/* */
else if(result > 0)
tree.right = remove(x, tree.right);
/* 1. , ,
*
* ( , （ 2）)
*/
else if(tree.left != null && tree.right != null){
tree.element = findMax();
}
/* 2. ,
* -
* - ，
*/
else{
tree = (tree.left != null) ? tree.left : tree.right;
}
return tree;
}
findMin (): 최소 값 을 조회 합 니 다.트 리 의 최소 값 은 왼쪽 트 리 의 최소 요소 입 니 다.재 귀 실현 을 채택 하 다.findMax (): 최대 값 을 조회 합 니 다.트 리 의 최대 치 는 오른쪽 트 리 의 최대 요소 입 니 다.비 귀속 실현 을 채택 하 다.
public T findMin(){
return findMin(root);
}
private T findMin(BinaryNode<T> tree){
/* */
if(tree == null)
return null;
/* ， */
else if(tree.left != null)
return findMin(tree.left);
/* */
else
return tree.element;
}
public T findMax(){
return findMax(root);
}
private T findMax(BinaryNode<T> tree){
/* */
if(tree != null)
/* ,
* ps: tree , .
* , ！
* tree.right = tree.left .
*/
while(tree.right != null)
tree = tree.right;
return tree.element;
}
print (): 트 리 의 요소 값 을 순서대로 출력 합 니 다.중 서 를 옮 겨 다 니 는 방식 으로 이 루어 집 니 다.
public void print(){
print(root);
}
private void print(BinaryNode<T> tree){
if(tree == null)
return;
print(tree.left);
System.out.println(tree.element + " l:" + tree.left + " r:" + tree.right);
print(tree.right);
}
height (): 뒤쪽 으로 옮 겨 다 니 는 방식 으로 돌아 가 는 나무의 높이 를 구 합 니 다.
public int height(){
return height(root);
}
private int height(BinaryNode<T> tree){
if(tree == null)
return -1;
/* , , */
else
return 1 + Math.max(height(tree.left), height(tree.right));
}
내부 류
내부 클래스 는 이 진 트 리 의 노드 를 검색 합 니 다.노드 는 주로 데이터 와 왼쪽, 오른쪽 아이 노드 의 인용 을 유지 합 니 다.
private static class BinaryNode<T>{
public T element;
public BinaryNode<T> left;
public BinaryNode<T> right;
public BinaryNode(T ele){
this(ele, null, null);
}
public BinaryNode(T ele, BinaryNode<T> l, BinaryNode<T> r){
element = ele;
left = l;
right = r;
}
}
소스 코드
import java.util.Comparator;
/** * * @author Bingo * * @param <T> Comparable ， */
public class BinarySearchTree <T>{
/** * */
private BinaryNode<T> root;
/** * T */
private Comparator<T> cmp;
/** * */
public BinarySearchTree(){
this(null);
}
/** * * @param cmp */
public BinarySearchTree(Comparator<T> cmp){
this.cmp = null;
}
/** * * @param cmp */
public void setComparator(Comparator<T> cmp){
this.cmp = cmp;
}
public boolean isEmpty(){
return root == null;
}
public void clearTree(){
root = null;
}
public int height(){
return height(root);
}
/** * x * @param x * @return true， false */
public boolean contains(T x){
return contains(x, root);
}
/** * * @return */
public T findMin(){
return findMin(root);
}
/** * * @return */
public T findMax(){
return findMax(root);
}
/** * x * @param x */
public void insert(T x){
root = insert(x, root);
}
/** * x * @param x */
public void remove(T x){
root = remove(x, root);
}
/** * */
public void print(){
print(root);
}
/** * ( ) * @param x * @param tree * @return */
private boolean contains(T x, BinaryNode<T> tree){
if(tree == null)
return false;
/* x , */
int result = innerCompareTo(x, tree.element);
if(result < 0)
return contains(x, tree.left);
else if(result > 0)
return contains(x, tree.right);
/* result = 0, */
else
return true;
}
/** * . * . * @param tree * @return */
private T findMin(BinaryNode<T> tree){
/* */
if(tree == null)
return null;
/* ， */
else if(tree.left != null)
return findMin(tree.left);
/* */
else
return tree.element;
}
/** * * . * @param tree * @return */
private T findMax(BinaryNode<T> tree){
/* */
if(tree != null)
/* , * ps: tree , . * , ！ * tree.right = tree.left . */
while(tree.right != null)
tree = tree.right;
return tree.element;
}
/** * x， ， * @param x * @param tree * @return */
private BinaryNode<T> insert(T x, BinaryNode<T> tree){
/* , */
if(tree == null)
return new BinaryNode<T>(x);
int result = innerCompareTo(x, tree.element);
if(result < 0)
tree.left = insert(x, tree.left);
else if(result > 0)
tree.right = insert(x, tree.right);
else{
// ，
}
return tree;
}
/** * x * @param x * @param tree * @return */
private BinaryNode<T> remove(T x, BinaryNode<T> tree){
/* */
if(tree == null)
return null;
int result = innerCompareTo(x, tree.element);
/* */
if(result < 0)
tree.left = remove(x, tree.left);
/* */
else if(result > 0)
tree.right = remove(x, tree.right);
/* 1. , , * * ( , （ 2）) */
else if(tree.left != null && tree.right != null){
tree.element = findMax();
}
/* 2. , * - * - ， */
else{
tree = (tree.left != null) ? tree.left : tree.right;
}
return tree;
}
/** * , * @param tree */
private void print(BinaryNode<T> tree){
if(tree == null)
return;
print(tree.left);
System.out.println(tree.element + " l:" + tree.left + " r:" + tree.right);
print(tree.right);
}
/** * , */
private int height(BinaryNode<T> tree){
if(tree == null)
return -1;
/* , , */
else
return 1 + Math.max(height(tree.left), height(tree.right));
}
/** * * @param lhs * @param rhs * @return */
@SuppressWarnings("unchecked")
private int innerCompareTo(T lhs, T rhs){
if(cmp != null)
return cmp.compare(lhs, rhs);
else
return ((Comparable<T>)lhs).compareTo(rhs);
}
/** * ， * @author Bingo * * @param <T> */
private static class BinaryNode<T>{
public T element;
public BinaryNode<T> left;
public BinaryNode<T> right;
public BinaryNode(T ele){
this(ele, null, null);
}
public BinaryNode(T ele, BinaryNode<T> l, BinaryNode<T> r){
element = ele;
left = l;
right = r;
}
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
