두 갈래 찾기 트리 (둘)

전편에서 우리는 두 갈래 나무의 성질, 저장 및 정의의 결점을 이야기했다. 이런 것들이 있으면 우리는 두 갈래 나무를 만들 수 있다.
우선, 우리가 정의한 저장 구조에 따라 만약에 우리가 전체 나무의 뿌리 결점을 알게 된다면 우리는 전체 나무의 모든 결점을 방문할 수 있다는 것을 안다. 따라서 두 갈래 나무의 종류를 다음과 같이 한다.

 1 /**
 2  *  
 3  * @author Alfred
 4  */
 5 public class BSTree {
 6     // 
 7     private Random rand = null;
 8     // 
 9     private TreeNode rootNode = null;
10     
11     /**
12      *  int A 
13      * @param A int 
14      */
15     public BSTree(int[] A){
16         rand = new Random();
17         createBSTree(A);
18     }
19     
20     /**
21      *  
22      * @param A int 
23      */
24     private void createBSTree(int[] A){}
25 }

코드에는 랜덤 클래스의 대상 (이 대상을 내가 추가했을 때, 없을 수도 있고, 원인 이후에 설명할 수도 있다) 과 루트 결점이 포함되어 있습니다. 우리는 정수의 수조로 두 갈래 찾기 트리를 만들 것을 가정합니다.우리는 두 갈래 찾기 나무가 두 갈래 찾기 나무의 성질을 만족시켜야 한다는 것을 알고 있다. 그러면 두 갈래 찾기 나무의 성질을 만족시키는 나무를 어떻게 구성해야 하는가.여기서 우리는 삽입 방법을 사용하여 정수 그룹 안의 정수를 우리가 구축하고자 하는 두 갈래 찾기 트리에 하나하나 삽입한다. 요소를 삽입할 때 두 갈래 찾기 트리의 성질을 만족시켜야 하기 때문에 우리는 두 가지 문제를 처리해야 한다.
　　1.삽입된 요소가 이미 수에 존재한다면 어떻게 처리해야 합니까?
　　2.어떻게 삽입해야 최악의 상황을 최대한 피할 수 있습니까?
첫 번째 문제에 대해 여기서 처리하는 것은 같은 결점을 하나의 위치에 존재하는 것이다. 즉, 나무의 한 결점으로 통합하는 것이다. 다음 결점의 정의를 보면 알 수 있듯이 정의의 데이터Num은 같은 결점의 개수를 기록하는 것이다.
두 번째 문제에 대해 먼저 최악의 상황이 무엇인지 상상해 보자. 최악의 상황은 수조가 이미 순서를 정한 것보다 구축된 두 갈래 찾기 트리가 하나의 직렬로 퇴화되는 것이다.그럼 어떻게 처리해야 하나요?만약 우리가 삽입할 때 정해진 순서에 따라 수조의 수를 얻는 것이 아니라 무작위로 수를 선택한다면, 우리는 가능한 한 최악의 상황을 피할 수 있을 것이다.
자, 삽입된 코드는 다음과 같습니다.

 1 /**
 2      *  
 3      * @param z  
 4      */
 5     public void TreeInsert(int z){
 6         TreeNode parentNode = null;
 7         TreeNode searchNode = rootNode;
 8         TreeNode insertNode = new TreeNode(z);
 9         //while 
10         while(searchNode != null){
11             parentNode = searchNode;
12             if(insertNode.getKey() < searchNode.getKey()){
13                 searchNode = searchNode.getLeft();
14             }else if(insertNode.getKey() == searchNode.getKey()){
15                 // key ， ， ...
16                 searchNode.incNumByOne();
17                 return;
18             }else{
19                 searchNode = searchNode.getRight();
20             }
21         }
22         
23         insertNode.setParent(parentNode);
24         if(parentNode == null){
25             rootNode = insertNode;
26         }else if(insertNode.getKey() < parentNode.getKey()){
27             // 
28             parentNode.setLeft(insertNode);
29         }else if(insertNode.getKey() == parentNode.getKey()){
30             // ， 。
31             parentNode.incNumByOne();
32             System.out.println("this is not supposed to be executed.");
33         }else{
34             // 
35             parentNode.setRight(insertNode);
36         }
37     }

삽입된 코드는 간단합니다. 첫 번째while 순환에서 우리가 삽입할 결점의 부결점을 찾은 다음에 삽입합니다.여기서 주의해야 할 점은 만약에 나무에 삽입할 원소와 하나 이상의 원소가 있다면 이곳의 처리는 같은 결점 위치에 놓는 것이다. 즉, 이 중복 결점의 데이터 Num만 추가하면 된다. 트리노드에서 정의한 게으름 피우는 방법은 여기에 도움이 된다.
그러면 어떻게 랜덤을 실현할 수 있을까요? 저도 특별히 좋은 방법을 생각하지 못했습니다. 제가 쓴 다음 코드를 참고할 수 있습니다.

 1 /**
 2      *  
 3      * @param A int 
 4      */
 5     private void createBSTree(int[] A){
 6         // List
 7         List<Integer> index = new LinkedList<Integer>();
 8         int i = 0;
 9         for(i = 0; i < A.length; i++){
10             index.add(i);
11         }
12         // 
13         for(i = 0; i < A.length; i++){
14             int j = 0;
15             if(index.size() > 1){
16                 // 
17                 j = rand.nextInt(index.size() - 1);
18             }
19             // 
20             TreeInsert(A[index.get(j)]);
21             // 
22             index.remove(j);
23         }
24     }

위의 코드에서 먼저 저장된 그룹 아래에 표시된List를 만든 다음에 삽입할 때 무작위로 이 목록에서 아래 표시를 선택하고 이 그룹 아래에 표시된 수를 꺼내 두 갈래 검색 트리에 삽입한 다음 다음 다음 다음 아래 표시를 목록에서 제거합니다. 그러면 다음 순환이 이번에 발생하는 아래 표시가 발생하지 않습니다.이렇게 하면 랜덤화된 구조의 두 갈래 찾기 트리를 실현할 수 있다.
자, 위에 쓴 몇 가지 방법이 있습니다. BSTree 클래스는 두 갈래 찾기 트리의 삽입 작업과 두 갈래 찾기 트리를 구축하는 임무를 완성했습니다.