[Algorithm] Binary Search Tree - Successor, Predecessor

Successor, Predecessor

지금 까지 Binary Search Tree의 정의, Insert, Search에 대해서 알아봤다.

그럼 왜? Delete를 먼저 구현하지 않고 Successor, Predecessor 를 먼저 구현해보는것일까?

그것은 Delete를 할때 여러가지 조건이 있고 Delete를 안정적으로하기 위해서 필요하기 때문이다.

 

Successor 란?

• 선택한 노드의 오른쪽 서브트리중 가장 작은값을 가지는 노드를 의미한다.
• 50 을 선택하면 일단 50 노드의 오른쪽 서브트리를 찾는다 
• 그중 가장 최소값 즉 왼쪽으로 계속 이동하면서 작은 값을 찾는다.
• 그말인 즉슨 선택한 노드보다 크면서 제일 작은값이다.

 

 

Successor 의 코드구현

   public Node getSuccessor(Node node, boolean findMode) {
        if (node == null)
        {
            System.out.println("Node is NULL");
            return node;
        }

        if (node.right == null) {
            System.out.println("Cannot find successor");
            return node;
        }

        Node successorNode = node.right;
        Node parentNode = node;
        while (successorNode.left != null) {
            parentNode = successorNode;
            successorNode = successorNode.left;
        }

        // 나중에 delete 를 할때 사용 현재는 사용안함.
        if (!findMode) {
            parentNode.left = successorNode.right;
        }
        return successorNode;
    }

 

Predecessor 란?

선택한 노드의 키보다 작으면서 가장큰 값을 가지는 노드 

Successor의 반대.

 

선택한 노드의 왼쪽 으로 이동후 가장 큰값을 찾는다.

 

 

 

 

Predecessor 의 코드구현

    public Node getPredecessor(Node node, boolean findMode)  {
        if (node == null)
        {
            System.out.println("Node is NULL");
            return node;
        }

        if (node.left == null) {
            System.out.println("Cannot find predecessor");
            return node;
        }

        Node predecessorNode = node.left;
        Node parentNode = node;
        while (predecessorNode.right != null) {
            parentNode = predecessorNode;
            predecessorNode = predecessorNode.right;
        }

		// delete 할때 사용하기 위한 코드 현재는 무시한다.
        if (!findMode) {
            parentNode.right = predecessorNode.left;
        }
        return predecessorNode;
    }

 

 

 

참고사항

구현중 원래 노드의 부트리가 없으면 부모를 찾아가는 코드를 뺐다.

추후 구현 할 예정

 

 

 

선행학습

https://vprog1215.tistory.com/72

Binary Search Tree - Insert

https://vprog1215.tistory.com/73

Binary Search Tree - Search

 

 

전체코드

구현코드:

https://github.com/rnrl1215/algorithm-base/tree/master/src/main/java/algorithm/binarysearchtree

 

테스트코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/test/java/BinarySearchNodeTest.java