데이터 구조의 '이 진 트 리'

두 갈래 검색 트 리
이 진 트 리 는 이 진 트 리 나 이 진 트 리 라 고도 합 니 다. 빈 트 리 이거 나 다음 과 같은 몇 가 지 를 만족 시 킵 니 다. 1. 임의의 노드 의 왼쪽 트 리 가 비어 있 지 않 으 면 왼쪽 트 리 의 모든 노드 의 값 은 뿌리 노드 의 값 보다 작 습 니 다.2. 임의의 노드 의 오른쪽 하위 트 리 가 비어 있 지 않 으 면 오른쪽 하위 트 리 의 모든 노드 의 값 이 뿌리 노드 의 값 보다 크다.3. 임의의 노드 의 왼쪽, 오른쪽 트 리 도 각각 이 진 트 리 로 나 뉜 다.4. 키 가 같은 노드 가 없습니다.
두 갈래 검색 트 리 의 실현
1. 두 갈래 검색 트 리 의 저장 구조

public class BinarySearchTree {
    public static  Node root;
    public BinarySearchTree(){
        this.root = null;
    }
}
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
        left = null;
        right = null;
    }
}

2. 이 진 트 리 의 삽입 a. 2 분 반복 해서 삽입 할 곳 을 찾 습 니 다.b. 삽 입 된 값 이 현재 값 보다 적 고 현재 왼쪽 노드 가 비어 있 으 면 왼쪽 노드 는 새 노드 를 가리킨다.c. 만약 에 삽 입 된 값 이 현재 의 값 보다 크 고 현재 오른쪽 노드 가 비어 있다 면 오른쪽 노드 는 새로운 노드 를 가리킨다.

public void insert(int id){
    Node newNode = new Node(id);
    if(root == null){
        root = newNode;
        return;
    }
    Node current = root;
    Node parent = null;
    while(true){
        parent = current;
        if(id < current.data){
            current = current.left;
            if(current == null){
                parent.left = newNode;
                return;
            }
        } else {
            current = current.right;
            if(current == null){
                parent.right = newNode;
                return;
            }
        }
    }
}

3. 이 진 트 리 의 삭제 a. 노드 를 잎 노드 로 삭제 할 때 노드 를 직접 삭제 합 니 다.b. 노드 가 왼쪽 트 리 만 삭제 할 때 왼쪽 트 리 를 다시 연결 합 니 다.c. 노드 가 오른쪽 하위 트 리 만 삭제 할 때 오른쪽 하위 트 리 를 다시 연결 합 니 다.d. 노드 를 삭제 할 때 왼쪽 트 리 도 있 고 오른쪽 트 리 도 있 을 때 삭제 노드 를 교체 할 수 있 는 노드 를 찾 습 니 다.이 진 트 리 의 성질 로 인해 왼쪽 나무의 값 은 뿌리 노드 의 값 보다 작고 오른쪽 나무의 값 은 뿌리 노드 의 값 보다 크다.그래서 오른쪽 트 리 의 가장 왼쪽 노드 는 삭 제 된 노드 를 교체 한 다음 에 오른쪽 트 리 를 다시 연결 하 는 것 이다.제 d 점 의 그림 예:

public boolean delete(int id) {
    Node parent = root;
    Node current = root;
    boolean isLeftChild = false;
    while (current.data != id) {
        parent = current;
        if (current.data > id) {
            isLeftChild = true;
            current = current.left;
        } else {
            isLeftChild = false;
            current = current.right;
        }
        if (current == null) {
            return false;
        }
    }
    //          ，     
    if (current.left == null && current.right == null) {
        if (current == root) {
            root = null;
        }
        if (isLeftChild == true) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    }
    //          
    else if (current.right == null) {
        if (current == root) {
            root = current.left;
        } else if (isLeftChild) {
            parent.left = current.left;
        } else {
            parent.right = current.left;
        }

    }
    //          
    else if (current.left == null) {
        if (current == root) {
            root = current.right;
        } else if (isLeftChild) {
            parent.left = current.right;
        } else {
            parent.right = current.right;
        }
    }
    //          ，     
    else if (current.left != null && current.right != null) {
        //          
        Node successor = getSuccessor(current);
        if (current == root) {
           root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    public Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

4. 이 진 트 리 찾기

public boolean find(int id) {
    Node current = root;
    while (current != null) {
        if (current.data == id) {
            return true;
        } else if (current.data > id) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return false;
    }

총결산
이것 은 질서 있 는 나무 이기 때문에 반 으로 나 누 어 찾 을 수 있 습 니 다. 매번 찾 을 때마다 일치 하 는 값 이 아니라면 반 의 값 을 제거 할 수 있 습 니 다.그래서 일반적인 시간 복잡 도 는 O (log n) 이다.만약 에 이 나무 가 경사 나무 로 퇴화 한다 면 선형 표 가 많 지 않 을 것 이다. 그의 시간 복잡 도 는 바로 O (n) 이다.
이 진 트 리 의 최 악의 시간 복잡 도 는 O (n) 이지 만 일부 개선 을 통 해 최 악의 시간 복잡 도 를 O (log n) 로 낮 출 수 있다. 예 를 들 어 AVL 트 리, 빨 간 검 은 나무 등 이다.빨간색 과 검은색 나 무 는 절대적 인 균형 이 필요 하지 않 기 때문에 삽입 과 삭제 효율 이 높 아야 한다. JDK 1.8 에서 해시 표 에 8 개 노드 이상 저장 되 어 있 는 링크 는 바로 사용 하 는 빨간색 과 검은색 나무 이다.
그래서 이 진 트 리 는 검색 에 있어 서 매우 빠 르 고 높 은 조회 효율 이 필요 할 때 추천 합 니 다.
PS: 청산 녹 수 는 먼지 에서 시작 되 고 박학 다 식 은 근면 보다 비싸다.저 술 있어 요. 사연 있어 요?위 챗 공식 번호: "먼지 제거 잡담".코드 에 대해 이야기 하 는 것 을 환영 합 니 다.