자바 로 두 갈래 검색 트 리 구현

두 갈래 검색 트 리 의 정의

이 진 트 리 입 니 다

모든 노드 의 왼쪽 서브 트 리 에 있 는 모든 노드 의 값 은 이 노드 의 값 보다 작 습 니 다

모든 노드 의 오른쪽 서브 트 리 에 있 는 모든 노드 의 값 은 이 노드 의 값

보다 크다.

특징:이 진 트 리 의 중간 순 서 를 옮 겨 다 니 는 결 과 는 질서 가 있 습 니 다(오름차 순)!
두 갈래 검색 트 리 구현

두 갈래 검색 트 리 를 실현 하면 삽입,삭제,세 가지 측면 찾기

이 진 트 리 의 노드 는 수정 할 수 없습니다.수정 하면 검색 트 리 의 오류 가 발생 할 수 있 습 니 다

두 갈래 검색 트 리 의 정의 클래스

이 진 트 리 의 노드 류―class Node

이 진 트 리 의 속성 을 검색 합 니 다.이 진 트 리 를 찾 으 려 면 이 나무의 뿌리 노드 만 알 아야 합 니 다.

public class BST {
    static class Node {
        private int key;
        private Node left;
        private Node right;

        public Node(int key) {
            this.key = key;
        }
    }

    private Node root;//BST    
}

두 갈래 검색 트 리 찾기

이 진 트 리 검색 방향:

① 현재 노드 의 값 과 같 으 면 찾 을 수 있다

② 현재 노드 의 값 보다 작은 값 을 찾 으 려 면 현재 노드 의 왼쪽 트 리 로 가세 요

③ 찾 으 려 는 값 이 현재 노드 의 값 보다 크 면 현재 노드 의 오른쪽 하위 트 리 로 갑 니 다

결국 비 었 는데 도 찾 지 못 하면 이것key

이 존재 하지 않 는 다 는 뜻 이다.

/**
 *         
 *
 *   ：          ：
 * ①               ，  ，           
 * ②               ，  ，           
 *
 * @param key     key
 * @return boolean    
 */
public boolean find(int key) {
	Node cur = root;
	while (cur != null) {
		if (key < root.key) {
			cur = cur.left;
		} else if (key > root.key) {
			cur = cur.right;
		} else {
			return true;
		}
	}
	return false;
}

두 갈래 검색 트 리 삽입

이 진 트 리 의 삽입 사고:

사고방식 과 찾기 가 똑 같 습 니 다.다만 우리 가 이번에 진행 하고 자 하 는 것 은 삽입 작업 입 니 다.그러면 우 리 는parent노드 가 필요 합 니 다.현재 노드 의 부모 노드 를 항상 기록 해 야 합 니 다.즉,

① 삽입 할 값 이 현재 노드 의 값 과 같 으 면 삽입 할 수 없습니다key

② 삽입 할 값 이 현재 노드 의 값 보다 작 으 면 현재 노드 의 왼쪽 트 리 로 갑 니 다

③ 삽입 할 값 이 현재 노드 의 값 보다 크 면 현재 노드 의 오른쪽 하위 트 리 로 갑 니 다

최종 적 으로 비 어 있 으 면 중복 되 는 것 이 존재 하지 않 는 다 는 것 을 의미한다key.부모 노드 의 뒤쪽 에 꽂 으 면 된다.바로 적당 한 위치 이다.구체 적 으로 왼쪽 에 꽂 을 지 오른쪽 에 꽂 을 지 노드 의key와parent의key

를 비교 해 야 한다.

/**
 *          
 *
 *     ：
 *
 * @param key       
 */
public void insert(int key) {
	if (root == null) { //     ，  ，    
		root = new Node(key);
		return;
	}

	Node cur = root;
	Node parent = null; //parent  cur    
	while (true) {
		if (cur == null) { //      ，        ，     （      ）
			if (parent.key < key) {
				parent.right = new Node(key);
			} else {
				parent.left = new Node(key);
			}
			return;
		}

		if (key < cur.key) {
			parent = cur;
			cur = cur.left;
		} else if (key > cur.key) {
			parent = cur;
			cur = cur.right;
		} else {
			throw new RuntimeException("    ，    key");
		}
	}
}

두 갈래 검색 트 리 삭제

두 갈래 검색 트 리 의 삭제 사고방식:(상세 한 사고방식 은 주석 참조)

우선 존재 여부key노드 를 먼저 찾 아야 하고 존재 하면 삭제 하고 존재 하지 않 으 면 삭제 오류

존재 한다 면 세 가지 상황 으로 나 뉜 다.

① 삭제 할 노드,왼쪽 아이 없 음

I:삭제 할 노드 는 루트 노드 입 니 다.root = delete.right;II:삭제 할 노드 는 부모 노드 의 왼쪽 아이 입 니 다.parent.left = delete.right;Ⅲ:삭제 할 노드 는 부모 노드 의 오른쪽 아이 입 니 다.parent.right = delete.right;

② 삭제 할 노드,오른쪽 아이 없 음

I:삭제 할 노드 는 루트 노드 입 니 다.root = delete.left;II:삭제 할 노드 는 부모 노드 의 왼쪽 아이 입 니 다.parent.left = delete.left;Ⅲ:삭제 할 노드 는 부모 노드 의 오른쪽 아이 입 니 다.parent.right = delete.left;

③ 삭제 할 노드 는 왼쪽 아이 도 있 고 오른쪽 아이 도 있다.

이때 우 리 는 전체 이 진 트 리 중 첫 번 째 로 삭제 할 노드 보다 큰 노드 를 찾 은 다음 에 그들 두 사람의 값 을 바 꾸 고 마지막 으로 찾 은 노드 를 삭제 해 야 한다.
I:찾 은 노드 의 부모 노드 는 삭제 할 노드 입 니 다.delete.key = find.key;findParent.right = find.right;II:찾 은 노드 의 부모 노드 는 삭제 할 노드 가 아 닙 니 다.delete.key = find.key;findParent.left = find.right;

/**
 *       
 *
 *     ：
 *
 * @param key       
 */
public void remove(int key) {
	if (root == null) {
		throw new RuntimeException("   ，    ！");
	}
	Node cur = root;
	Node parent = null;
	//    key     
	while (cur != null) {
		if (key < cur.key) {
			parent = cur;
			cur = cur.left;
		} else if (key > cur.key) {
			parent = cur;
			cur = cur.right;
		} else {
			break;
		}
	}
	if (cur == null) {
		throw new RuntimeException("   key，  key   ");
	}

	//cur        
	//parent            
	/*
         *   1：             
         *   
         * ①          
         * ②           
         *         
         */
	if (cur.left == null) {
		if (cur == root) { //①          
			root = cur.right;
		} else if (cur == parent.left) { //②               
			parent.left = cur.right;
		} else { //③                 
			parent.right = cur.right;
		}
	}
	/*
         *   2:             
         *
         *   :             
         */
	else if (cur.right == null) { //①          
		if (cur == root) {
			root = cur.left;
		} else if (cur == parent.left) { //②               
			parent.left = cur.left;
		} else { //③                 
			parent.right = cur.left;
		}
	}
	/*
        *   3:                  
        *
        *   :
        *         ,                   ,   ,      ,              
        *   :
        * ①      
        * ②     
        * ③                ,      ,         
        * ④         
        * ⑤    
        *
         */
	else {
		Node nextParent = cur; //     ,           
		Node next = cur.right; //  next        ,                  
		while (next.left != null) {
			nextParent = next;
			next = next.left;
		}
		cur.key = next.key; //    ,      
		if (nextParent == cur) { //              ,                 (    next     )
			nextParent.right = next.right;
		} else { //             , next      ,     .
			nextParent.left = next.right;
		}
	}

}

자 바 를 이용 한 두 갈래 검색 트 리 구현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 두 갈래 검색 트 리 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!