PHP에서 이진 트리를 구현하는 방법(코드 예)

이진 트리는 컴퓨터 과학의 기본 데이터 구조로, 컴퓨터 과학에서 검색 및 정렬을 위해 사용되는 등 가장 일반적인 트리 구조이며, 컴퓨터 과학의 다른 많은 분야에서도 사용됩니다. PHP는 동적 웹 개발을 지원하는 널리 사용되는 서버측 스크립팅 언어입니다. 이번 글에서는 PHP를 이용하여 바이너리 트리를 구현하는 방법을 소개하겠습니다.

이진 트리란 무엇인가요?

이진 트리는 여러 노드로 구성되며 각 노드에는 최대 2개의 하위 노드가 있습니다. 세 가지 속성이 있습니다:

• 노드 값
• 왼쪽 하위 트리 포인터
• 오른쪽 하위 트리 포인터

이진 트리는 다음 범주로 나뉩니다.

• 전체 이진 트리: 리프 노드를 제외하고 다른 노드에는 두 개의 하위 노드가 있습니다.
• 완전 이진 트리: 이진 트리의 깊이가 d이면 d번째 레벨을 제외한 다른 레벨은 모두 가득 차고, d번째 레벨에서는 모든 리프 노드가 왼쪽의 연속적인 위치에 있습니다
• 이진 검색 트리: 왼쪽 하위 트리 모든 노드는 루트 노드 값보다 작고 오른쪽 하위 트리의 모든 노드 값은 루트 노드 값보다 큽니다

이진 트리를 구현하려면

클래스를 사용하여 이진 트리 구조를 정의할 수 있습니다. 각 노드는 다음 속성을 가진 개체입니다.

• value: 노드 값
• left: 왼쪽 하위 트리 포인터
• right: 오른쪽 하위 트리 포인터

노드를 나타내는 클래스를 만듭니다.

class Node {
    public $value;
    public $left;
    public $right;
    function __construct($value){
        $this -> value = $value;
        $this -> left = null;
        $this -> right = null;
    }
}

다음으로 이진 트리를 나타내는 클래스를 만들어야 합니다.

class BinarySearchTree {
    public $root;
    function __construct() {
        $this -> root = null;
    }
}

다음으로 이진 트리에 대해 다음 메서드를 정의합니다.

• insert(value): 이진 트리에 값 삽입
• search(value): 이진 트리에서 값 찾기
• delete(value) : 이진 트리에서 값 삭제

Insert Node

Insert Node 방법은 새 노드를 올바른 위치에 삽입합니다. 트리가 비어 있으면 새 노드는 루트 노드입니다. 그렇지 않으면 루트 노드에서 현재 노드의 값을 비교하기 시작합니다.

• 새 노드의 값이 현재 노드의 값보다 작으면 새 노드를 왼쪽 하위 트리에 삽입합니다.
• 새 노드의 값이 현재 노드의 값보다 크면 새 노드를 오른쪽 하위 트리에 삽입합니다.
• 새 노드의 값이 현재 노드의 값과 같으면 해당 노드가 이미 존재하므로 삽입할 필요가 없습니다.

삽입 방법에 대한 코드는 다음과 같습니다.

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value < $current -> value) {
                if ($current -> left == null) {
                    $current -> left = $newNode;
                    return;
                } else {
                    $current = $current -> left;
                }
            } else if ($value > $current -> value) {
                if ($current -> right == null) {
                    $current -> right = $newNode;
                    return;
                } else {
                    $current = $current -> right;
                }
            } else {
                return;
            }
        }
    }
}

Find Node

Find Node 방법은 간단한 재귀 방법입니다. 루트 노드부터 시작하여 노드 값을 비교합니다. 값이 같으면 현재 노드를 반환합니다. 그렇지 않고 노드의 값이 찾고 있는 값보다 작으면 왼쪽 하위 트리를 계속 검색합니다. 값이 찾고 있는 값보다 크면 오른쪽 하위 트리를 계속 검색하세요.

find 메소드의 코드는 다음과 같습니다.

function search($value) {
    $current = $this -> root;
    while ($current != null) {
        if ($value == $current -> value) {
            return $current;
        } else if ($value < $current -> value) {
            $current = $current -> left;
        } else {
            $current = $current -> right;
        }
    }
    return null;
}

Delete Node

노드 삭제 메소드는 전체 구현에서 가장 복잡한 메소드 중 하나입니다. 노드 삭제 방법은 노드의 하위 항목 수에 따라 다릅니다. 다음과 같은 상황이 있을 수 있습니다.

• 노드는 리프 노드이며 하위 노드가 없습니다. 노드를 직접 삭제합니다.
• 노드에는 하위 노드가 하나만 있습니다. 하위 노드를 이 노드로 바꿉니다.
• 노드에는 두 개의 하위 노드가 있습니다. 노드의 오른쪽 하위 트리에서 최소값을 찾아 해당 노드로 최소값을 바꾸고 오른쪽 하위 트리에서 최소값을 제거합니다.

삭제 메소드의 코드는 다음과 같습니다.

function delete($value) {
    $current = $this -> root;
    $parent = null;
    while ($current != null) {
        if ($value == $current -> value) {
            if ($current -> left == null && $current -> right == null) {
                if ($parent == null) {
                    $this -> root = null;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = null;
                    } else {
                        $parent -> right = null;
                    }
                }
            } else if ($current -> left == null) {
                if ($parent == null) {
                    $this -> root = $current -> right;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> right;
                    } else {
                        $parent -> right = $current -> right;
                    }
                }
            } else if ($current -> right == null) {
                if ($parent == null) {
                    $this -> root = $current -> left;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> left;
                    } else {
                        $parent -> right = $current -> left;
                    }
                }
            } else {
                $replacementNode = $current -> right;
                while ($replacementNode -> left != null) {
                    $replacementNode = $replacementNode -> left;
                }
                $removeValue = $replacementNode -> value;
                $this -> delete($replacementNode -> value);
                $current -> value = $removeValue;
            }
            return;
        } else if ($value < $current -> value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

결론

이제 PHP에서 이진 트리를 구현하는 방법을 배웠습니다. 이진 트리는 컴퓨터 과학의 기본 데이터 구조이며 많은 알고리즘과 응용 프로그램이 이를 포함합니다. 노드를 삽입하는 방법, 노드를 찾는 방법, 노드를 삭제하는 방법을 배웠습니다. 또한 이 클래스를 확장하여 다른 실용적인 메서드를 구현할 수도 있습니다.

위 내용은 PHP에서 이진 트리를 구현하는 방법(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!