Java 이진 검색 트리 예제 분석

Concept

이진 검색 트리는 빈 트리이거나 다음 속성을 갖는 이진 트리입니다.
1. 왼쪽 하위 트리가 비어 있지 않으면 값은 ​​왼쪽 하위 트리에 있는 모든 노드의 값은 루트 노드의 값보다 작습니다.
2. 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리에 있는 모든 노드의 값이 루트 노드의 값보다 큽니다.
3. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리입니다.

직접 연습

준비 작업: 트리 노드 클래스와 이진 검색 트리 클래스를 정의합니다.

이진 트리의 검색 기능 검색

아래와 같이 이진 트리를 구성했다고 가정해 보겠습니다.

우리가 생각하고 싶은 첫 번째 질문은 특정 값이 내부에 있는지 여부를 찾는 방법입니다.

위 논리를 바탕으로 검색 방법을 개선해 보겠습니다.

이진 트리의 삽입 연산 검색

위 논리를 바탕으로 노드를 삽입하는 코드를 작성해 보겠습니다.

이진 트리에서 노드 삭제 작업 검색 - 난이도

다시 분석해 보겠습니다. curDummy와 parentDummy가 "희생양"을 찾는 방법입니다.

일반 프로그램 - 이진 검색 트리 구현 시뮬레이션

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}


public class BinarySearchTree {
    TreeNode root;

    //在二叉树中 寻找指定 val 值的节点
    // 找到了，返回其节点地址；没找到返回 null
    public TreeNode search(int key){
        TreeNode cur = this.root;
        while(cur != null){
            if(cur.val == key){
                return cur;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                cur = cur.left;
            }
        }
        return null;
    }
    // 插入操作
    public boolean insert(int key){
        if(this.root == null){
            this.root = new TreeNode(key);
            return true;
        }
        TreeNode cur = this.root;
        TreeNode parent = null;
        while(cur!=null){
            if(key > cur.val){
                parent  = cur;
                cur = cur.right;
            }else if(cur.val == key){
                return false;
            }else{
                parent  = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(key);
        if(parent .val > key){
            parent.left = node;
        }else{
            parent.right = node;
        }
        return true;
    }
    // 删除操作
    public void remove(int key){
        TreeNode cur = root;
        TreeNode parent = null;
        // 寻找 删除节点位置。
        while(cur!=null){
            if(cur.val == key){
                removeNode(cur,parent);// 真正删除节点的代码
                break;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
    }
    // 辅助删除方法：真正删除节点的代码
    private void removeNode(TreeNode cur,TreeNode parent){
        // 情况一
        if(cur.left == null){
            if(cur == this.root){
                this.root = this.root.right;
            }else if( cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
            // 情况二
        }else if(cur.right == null){
            if(cur == this.root){
                this.root = root.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
            // 情况三
        }else{
            // 第二种方法：在删除节点的右子树中寻找最小值，
            TreeNode parentDummy = cur;
            TreeNode curDummy = cur.right;
            while(curDummy.left != null){
                parentDummy = curDummy;
                curDummy = curDummy.left;
            }
            // 此时 curDummy 指向的 cur 右子树
            cur.val = curDummy.val;
            if(parentDummy.left != curDummy){
                parentDummy.right = curDummy.right;
            }else{
                parentDummy.left = curDummy.right;
            }

        }
    }
   // 中序遍历
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {10,8,19,3,9,4,7};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("插入重复的数据 9：" + binarySearchTree.insert(9));
        System.out.println();// 换行
        System.out.print("插入不重复的数据 1：" + binarySearchTree.insert(1));
        System.out.println();// 换行
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        binarySearchTree.remove(19);
        System.out.print("删除元素 19 ：");
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("查找不存在的数据50 ：");
        System.out.println(binarySearchTree.search(50));
        System.out.print("查找存在的数据 7：");
        System.out.println(binarySearchTree.search(7));
    }
}

성능 분석

   삽입 및 삭제 작업을 모두 먼저 검색해야 하며 검색 효율성은 각 작업의 성능을 나타냅니다. 이진 검색 트리 성능에서.
 
 n개의 노드가 있는 이진 검색 트리의 경우 각 요소를 찾을 확률이 동일하면 이진 검색 트리의 평균 검색 길이는 이진 검색에서 노드 깊이의 함수입니다. 즉, 노드가 깊을수록 비교 횟수가 많아집니다.
 
  그러나 동일한 키 코드 세트에 대해 각 키 코드의 삽입 순서가 다를 경우 서로 다른 구조의 이진 검색 트리를 얻을 수 있습니다.

왼쪽과 오른쪽을 보장할 수 있다면 이진 검색 트리의 자식 트리 높이의 차이는 1을 초과하지 않습니다. 하이밸런스 조건을 충족시켜 보세요.
이것은 AVL 트리(높이 균형 이진 검색 트리)가 됩니다. AVL 트리에는 단점도 있습니다. 자주 회전해야 한다는 것입니다. 효율성이 많이 낭비됩니다.
이 시점에서 더 많은 회전을 피하기 위해 레드-블랙 트리가 탄생합니다.

Java 클래스 집합 간의 관계

TreeMap과 TreeSet은 Java에서 검색 트리를 사용하여 구현된 Map 및 Set입니다. 실제로 Red-Black 트리가 사용되며 Red-Black 트리는 대략 균형 잡힌 이진 검색 트리입니다. 이진 검색 트리 + 색상 및 레드-블랙 트리 속성 검증을 기반으로 레드-블랙 트리의 내용에 대해 블로거는 이를 학습한 후 블로그에 작성합니다.

위 내용은 Java 이진 검색 트리 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!