이진 트리 또는 이진 검색 트리를 준비하는 방법

서곡

이 문서는 이진 검색 트리에 관한 것입니다. 나는 최근에 관한 기사를 썼습니다. 허프만 방식을 이용한 데이터 압축 거기서는 검색, 삽입, 삭제 방법이 관련이 없었기 때문에 이진 트리에 별로 관심을 두지 않았습니다. 이제 나는 나무에 관한 기사를 쓰기로 결정했습니다. 시작하자.

트리는 모서리로 연결된 노드로 구성된 데이터 구조입니다. 트리는 그래프의 특별한 경우라고 말할 수 있습니다. 다음은 예제 트리입니다.

이것은 이진 검색 트리가 아닙니다! 모든 것이 잘립니다!

전문 용어

루트

나무뿌리 - 이것은 최상위 노드입니다. 예제에서는 노드 A입니다. 트리에서는 루트에서 다른 노드로 연결되는 경로가 하나만 있습니다! 실제로 모든 노드는 이 노드에 해당하는 하위 트리의 루트로 간주될 수 있습니다.

부모/자손

루트를 제외한 모든 노드에는 다른 노드로 이어지는 정확히 하나의 간선이 있습니다. 현재 노드 위에 위치한 노드를 호출합니다. 부모의 이 노드. 현재 노드 아래에 위치하고 이에 연결된 노드를 호출합니다. 자손 이 노드. 예를 들어 보겠습니다. 노드 B를 선택하면 그 부모는 노드 A가 되고 자식은 노드 D, E, F가 됩니다.

시트

자식이 없는 노드를 트리의 리프(leaf)라고 합니다. 이 예에서 리프는 노드 D, E, F, G, I, J, K가 됩니다.

이것이 기본 용어입니다. 다른 개념에 대해서는 더 자세히 논의하겠습니다. 따라서 이진 트리는 각 노드가 XNUMX개 이하의 자식을 갖는 트리입니다. 짐작한 대로, 노드 B와 H에는 세 개 이상의 자식이 있으므로 예제의 트리는 이진 트리가 아닙니다. 다음은 이진 트리의 예입니다.

트리 노드에는 모든 정보가 포함될 수 있습니다. 이진 검색 트리는 다음과 같은 속성을 갖는 이진 트리입니다.

1. 왼쪽 및 오른쪽 하위 트리는 모두 이진 검색 트리입니다.
2. 임의의 노드 X의 왼쪽 하위 트리의 모든 노드는 노드 X 자체의 데이터 키 값보다 작은 데이터 키 값을 갖습니다.
3. 임의의 노드 X의 오른쪽 하위 트리에 있는 모든 노드는 노드 X 자체의 데이터 키 값보다 크거나 같은 데이터 키 값을 갖습니다.

열쇠 — 노드의 모든 특성(예: 숫자) 이 키에 해당하는 트리 요소를 찾으려면 키가 필요합니다. 이진 검색 트리의 예:

트리 보기

진행하면서 이해를 돕기 위해 일부(아마도 불완전한) 코드 조각을 제공할 것입니다. 전체 코드는 기사 끝 부분에 있습니다.

트리는 노드로 구성됩니다. 노드 구조:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...остальные методы узла
}

각 노드에는 두 개의 하위 항목이 있습니다. leftChild 및/또는 rightChild 하위 항목에 null 값이 포함될 가능성이 높습니다. 이 경우 숫자 데이터가 노드에 저장된 데이터라는 것을 깨달았을 것입니다. 키 - 노드 키.

우리는 매듭을 정리했습니다. 이제 나무에 대한 시급한 문제에 대해 이야기합시다. 이하에서 "트리"라는 단어는 이진 검색 트리의 개념을 의미합니다. 이진 트리 구조:

public class BinaryTree<T> {
     private Node<T> root;

    //методы дерева
}

클래스 필드로 트리의 루트만 필요합니다. 루트에서 getLeftChild() 및 getRightChild() 메서드를 사용하면 트리의 모든 노드에 접근할 수 있기 때문입니다.

트리의 알고리즘

수색

구성된 트리가 있다고 가정해 보겠습니다. 키 키가 있는 요소를 찾는 방법은 무엇입니까? 루트부터 트리 아래로 순차적으로 이동하고 키 값을 다음 노드의 키와 비교해야 합니다. 키가 다음 노드의 키보다 작으면 노드의 왼쪽 자손으로 이동합니다. 더 크고 오른쪽으로 키가 동일하면 원하는 노드가 발견됩니다! 관련 코드:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

current가 null이 되면 검색이 트리의 끝에 도달한 것입니다(개념적 수준에서 사용자는 트리의 존재하지 않는 위치(리프의 자손)에 있습니다).

균형 트리(노드가 어느 정도 고르게 분포되어 있는 트리)에서 검색 알고리즘의 효율성을 고려해 보겠습니다. 그러면 검색 효율성은 O(log(n))이 되고 로그는 밑이 2입니다. 보세요: 균형 트리에 n개의 요소가 있으면 이는 밑이 2인 수준의 log(n)가 있음을 의미합니다. 나무. 그리고 검색에서는 주기의 한 단계에서 한 단계 아래로 내려갑니다.

삽입

검색의 본질을 파악하면 삽입을 이해하는 것이 어렵지 않습니다. 검색에 설명된 하강 규칙에 따라 나무 잎으로 내려가 키에 따라 왼쪽 또는 오른쪽의 하위 항목이 되기만 하면 됩니다. 구현:

   public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

이 경우 현재 노드 외에 현재 노드의 부모에 대한 정보도 저장해야 한다. current가 null이 되면 상위 변수에 필요한 시트가 포함됩니다.
삽입의 효율성은 분명히 검색의 효율성(O(log(n)))과 동일합니다.

제거

제거는 나무에서 수행해야 할 가장 어려운 작업입니다. 먼저 삭제할 요소를 찾아야 한다는 것은 분명합니다. 하지만 그러면 어쩌죠? 단순히 참조를 null로 설정하면 이 노드가 루트인 하위 트리에 대한 정보가 손실됩니다. 나무 제거 방법은 세 가지 경우로 나누어진다.

첫 번째 사례. 삭제 중인 노드에 하위 항목이 없습니다.

삭제되는 노드에 자식이 없으면 이는 리프라는 의미입니다. 따라서 해당 상위 항목의 leftChild 또는 rightChild 필드를 null로 설정하면 됩니다.

두 번째 사례. 삭제할 노드에 자식이 하나 있습니다.

이 경우도 그리 복잡하지 않습니다. 우리의 예로 돌아가 보겠습니다. 키가 14인 요소를 삭제해야 한다고 가정해 보겠습니다. 이 요소는 키가 10인 노드의 오른쪽 자손이므로 해당 하위 항목(이 경우 오른쪽 요소) 중 하나는 10보다 큰 키를 갖게 됩니다. 트리에서 쉽게 "잘라낼" 수 있고, 상위 노드를 삭제 중인 노드의 하위 노드에 직접 연결할 수 있습니다. 즉, 키 10을 사용하여 노드를 노드 13에 연결합니다. 부모의 왼쪽 자식인 노드를 삭제해야 하는 경우 상황은 비슷합니다. 스스로 생각해보십시오 - 정확한 비유입니다.

세 번째 사례. 노드에는 두 개의 자식이 있습니다.

가장 어려운 경우입니다. 새로운 예를 살펴보겠습니다.

후계자 찾기

키가 25인 노드를 삭제해야 한다고 가정해 보겠습니다. 그 자리에 누구를 넣어야 할까요? 그의 추종자(후손 또는 후손) 중 한 사람은 다음과 같아야 합니다. 후임(제거되는 노드를 대신할 사람)

누가 후계자가 되어야 하는지 어떻게 이해하나요? 직관적으로 이것은 삭제되는 노드에서 다음으로 큰 키를 갖는 트리의 노드입니다. 알고리즘은 다음과 같습니다. 오른쪽 자손으로 이동한 다음(이미 후속 키가 삭제되는 노드의 키보다 크다고 말했기 때문에 항상 오른쪽 자손으로 이동해야 함) 그런 다음 이 오른쪽 자손의 왼쪽 자손 체인을 통과해야 합니다. . 예제에서는 키가 35인 노드로 이동한 다음 왼쪽 자식 체인을 통해 리프로 내려갑니다. 이 경우 이 체인은 키가 30인 노드로만 구성됩니다. 엄밀히 말하면 우리는 찾고 있습니다. 우리가 찾고 있는 노드보다 큰 노드 집합에서 가장 작은 노드에 대해.

후속 검색 방법 코드:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;//родитель преемника
        Node<T> successor = deleteNode;//преемник
        Node<T> current = successor.getRightChild();//просто "пробегающий" узел
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //на выходе из цикла имеем преемника и родителя преемника
        if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
            parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
            successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
        }
        return successor;
    }

삭제 메소드의 전체 코드:

public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;//В зависимости от того, является ли  удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {//второй случай
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {//третий случай
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

복잡성은 O(log(n))로 근사화될 수 있습니다.

트리에서 최대값/최소값 찾기

트리에서 최소/최대 값을 찾는 방법은 분명합니다. 각각 트리의 왼쪽/오른쪽 요소 체인을 따라 순차적으로 이동해야 합니다. 시트에 도달하면 최소/최대 요소가 됩니다.

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

복잡도 - O(log(n))

대칭 바이패스

순회는 어떤 작업을 수행하기 위해 트리의 각 노드를 방문하는 것입니다.

재귀 대칭 순회 알고리즘:

1. 왼쪽 자식에 대해 작업 수행
2. 스스로 행동을 해보세요
3. 올바른 하위 항목에 대해 작업 수행

코드 :

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

결론

마지막으로! 제가 설명하지 못한 부분이나 의견이 있다면 댓글로 남겨주세요. 약속대로 완전한 코드를 제공합니다.

Node.java:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

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

    public void setLeftChild(Node<T> newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node<T> newNode) {
        rightChild = newNode;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

PS

O(n)으로의 변성

많은 분들이 눈치채셨을 것입니다. 나무를 불균형하게 만들면 어떻게 될까요? 예를 들어, 키가 증가하는 노드를 트리에 1,2,3,4,5,6... 놓으면 트리는 연결된 목록과 어느 정도 비슷해집니다. 그리고 그렇습니다. 트리는 트리 구조를 잃어 데이터 액세스의 효율성을 잃게 됩니다. 검색, 삽입, 삭제 작업의 복잡도는 연결리스트의 복잡도(O(n))와 동일해집니다. 내 생각에는 이것이 이진 트리의 가장 중요한 단점 중 하나입니다.

등록된 사용자만 설문 조사에 참여할 수 있습니다. 로그인제발

저는 허브에 오래 머물지 않았는데, 어떤 주제에 관한 어떤 기사를 더 보고 싶은지 알고 싶습니다.

• 데이터 구조

• 알고리즘(DP, 재귀, 데이터 압축 등)

• 데이터 구조와 알고리즘을 실생활에 적용

• Java로 Android 애플리케이션 프로그래밍

• Java로 웹 애플리케이션 프로그래밍

2명의 사용자가 투표했습니다. 1명의 사용자가 기권했습니다.

출처: www.habr.com