Java에서 처음부터 이진 검색 트리-java지도 시간-php.cn

Java에서 처음부터 이진 검색 트리

WBOY

풀어 주다： 2024-07-17 22:19:03

원래의

882명이 탐색했습니다.

Binary Search Tree from Scratch in Java

소개
BST(이진 검색 트리)는 각 노드가 왼쪽 자식과 오른쪽 자식이라고 하는 최대 2개의 자식을 갖는 이진 트리 유형입니다. 각 노드에 대해 왼쪽 하위 트리에는 노드 값보다 작은 값을 가진 노드만 포함되고 오른쪽 하위 트리에는 노드 값보다 큰 값을 가진 노드만 포함됩니다. BST는 효율적인 검색, 삽입, 삭제 작업에 사용됩니다.

이진 검색 트리를 사용하는 이유는 무엇인가요?
BST는 여러 가지 장점을 제공합니다:

효율적인 검색: 검색, 삽입, 삭제의 평균 시간 복잡도는 O(log n)입니다.
동적 항목 집합: 정적 배열과 달리 동적 작업을 지원합니다.
정렬된 요소: BST를 순서대로 순회하면 정렬된 순서로 요소가 생성됩니다.
BST 구축을 위한 단계별 가이드
1단계: 노드 구조 정의
첫 번째 단계는 트리에서 노드의 구조를 정의하는 것입니다. 각 노드에는 값, 왼쪽 하위 항목에 대한 참조, 오른쪽 하위 항목에 대한 참조라는 세 가지 속성이 있습니다.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

로그인 후 복사

2단계: 생성자를 사용하여 BST 클래스 생성
다음으로, 트리 루트에 대한 참조와 요소 삽입 방법을 포함하는 BST 클래스를 생성합니다.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

로그인 후 복사

3단계: 삽입 방법 구현
BST에 요소를 삽입하려면 새 노드의 올바른 위치를 찾아야 합니다. 삽입 방식은 일반적으로 재귀함수로 구현됩니다.

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertRec(root.left, value);
    } else if (value > root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

로그인 후 복사

시각화
삽입이 어떻게 작동하는지 더 잘 이해하기 위해 예를 살펴보겠습니다. BST에 50, 30, 70, 20, 40, 60, 80의 숫자 시퀀스를 삽입한다고 가정합니다.

로그인 후 복사

  50
 /
30

로그인 후 복사

  50
 /  \
30  70

로그인 후 복사

로그인 후 복사

40번 삽입:

로그인 후 복사

60개 삽입

  50
 /  \
30  70
/ \  /

로그인 후 복사

80번 삽입:

  50
 /  \
30  70
/ \  / \

로그인 후 복사

전체 코드
BST를 생성하고 요소를 삽입하는 전체 코드는 다음과 같습니다.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

로그인 후 복사

위 내용은 Java에서 처음부터 이진 검색 트리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!