JAVA 실천 밸 런 스 이 진 트 리 (AVL 트 리)

머리말
균형 이 잡 힌 이 진 트 리 는 이 진 트 리 의 변종 으로 한쪽 으로 완전히 치 우 친 검색 트 리 는 어느 정도 검색 성능 에 영향 을 줄 수 있다.그러나 역사상 항상 신 이 부족 하지 않 고 극치, 완벽 (강박 증) 을 추구 하 는 신 들 은 균형 이 잡 힌 이 진 트 리 를 생각해 냈 다.
이번 에는 삽입, 단계별 로 두 가지 기능 만 보 여 줍 니 다.
앤 리 이 글 은 아주 좋 습 니 다. 특히 자체 애니메이션 효과 가 있 습 니 다!!http://blog.csdn.net/eson_15/article/details/51144079
이거 간단명료 해!!!http://www.cnblogs.com/skywang12345/p/3577479.html
왕 이 공개 수업 인 진 월, 하 흠 명 에서 균형 이 진 트 리 에 대한 설명:http://mooc.study.163.com/course/ZJU-1000033001?tid=1000044001#/info
밸 런 스 이 진 트 리
만약 한 그루 의 나무 가 비어 있 지 않 으 면, 임의의 노드 의 좌우 자나무 사이 의 높이 차 의 절대 치가 1 (< = 1) 을 초과 하지 않 는 다 면, 그것 은 바로 균형 이 진 트 리 이다.

좌우 서브 나무의 높이 차 의 절대 치 를 균형 인자

라 고 한다.
예 를 들다
밸 런 스 이 진 트 리 여 부 를 판단 합 니 다
그림 1

뿌리 노드 에 왼쪽 나무 가 없고 높이 는 0 이다.오른쪽 나무의 높이 는 2 이다.균형 인자 2 > 1, 요 구 를 만족 시 키 지 못 합 니 다.

다른 노드 는 더 이상 판단 할 필요 가 없다. 그림 1 은 균형 이 진 트 리 가 아니다.
그림 2

뿌리 노드 의 왼쪽 나무 높이 는 1 이 고 오른쪽 나무 높이 는 2 이다.균형 인 자 는 1 = 1 로 요 구 를 잠시 만족 시 킵 니 다 (임의의 노드 로 정의 하 는 것 을 기억 합 니 다).

노드 1 왼쪽 나무의 높이 는 0 이 고 오른쪽 나무의 높이 는 0 이 며 균형 인 자 는 0 < 1 로 요 구 를 만족시킨다.

노드 3 의 왼쪽 나무 높이 는 0 이 고 오른쪽 나무 높이 는 1 이 며 균형 인 자 는 1 = 1 로 요 구 를 만족시킨다.

노드 4 왼쪽 나무의 높이 는 0 이 고 오른쪽 나무의 높이 는 0 이 며 균형 인 자 는 0 < 1 로 요 구 를 만족시킨다.

모든 노드 판단 완료.그림 2 의 나 무 는 균형 이 잡 힌 이 진 트 리 라 고 단정 할 수 있다.

또 몇 가지 문제 가 있다
Q1: 균형 이 잡 힌 이 진 트 리 는 어떻게 쓰 는 지 다 알 아 요.
A1:
일반적인 이 진 트 리 에 노드 를 삽입 할 때 우 리 는 크기 로 만 위 치 를 판단 하고 나무의 형 태 를 상관 하지 않 습 니 다.
균형 이 잡 힌 이 진 트 리 에서 우 리 는 필요 하 다.

노드 를 삽입 할 때 노드 의 위 치 를 판단 한다

노드 를 삽입 한 후 임의의 노드 균형 인자 인지 < 1

인지 확인 합 니 다.

편차 가 발생 하면 나무의 형태 수정

Q2: 균형 인 자 를 어떻게 계산 합 니까?
A2:
균형 인자 = | 노드 의 왼쪽 트 리 높이 - 노드 의 오른쪽 트 리 높이 | |: 절대 값
Q3: 노드 트 리 의 높이 를 어떻게 확인 합 니까?
A3:
깊이 가 우선 이 라 고 들 어 보 셨 나 요?

private int getHeightRecursion(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getHeightRecursion(root.left);
        int right = getHeightRecursion(root.right);

        return (left > right ? left : right) + 1;
    }

먼저 왼쪽 우선 순 위 를 옮 겨 다 니 고 오른쪽 우선 순 위 를 옮 겨 다 니 세 요.
최대 치 를 취 하 는 것 은 왼쪽 노드 가 없고 오른쪽 노드 가 있 는 상황 이 발생 할 까 봐 0: 1 0 을 취 할 수 없습니다.
마지막 층 에서 1 층 으로 돌아 갈 때마다 한 층 씩 늘어난다.
마지막 결 과 는 깊이 다.
다음은 쓸데없는 말 일 수도 있다.
뿌리 노드 에서 마지막 왼쪽 노드 로 들 어가 도착 한 후에 돌아 오 면 매번 증가 합 니 다.
마지막 오른쪽 노드 에 들 어가 서 도착 한 후에 돌아 오 면 매번 증가 합 니 다.
마지막 층 에 도착 한 후 돌아 오 면 [있 음] 왼쪽 노드 (left = 1), [없 음] 오른쪽 노드 의 상황 (right = 0) 이 나타 날 수 있 습 니 다.
따라서 전체 재 귀 기간 에 좌우 높이 가 다 를 수 있다.
최대 치 를 취해 야 합 니 다.
+ 1 은 깊이 가 한 층 증가 함 을 나타 낸다.
만약 하나의 노드 만 있다 면 높이 는 1 이다.
재 귀적 탐색 서브 트 리 깊이 를 이해 하고 AVL 트 리 에서 어떻게 놀 수 있 는 지 살 펴 봤 다.
노드 가 고도 속성 을 가지 고 작업 을 삽입 할 때 기록 하도록 하면 균형 요 소 를 판단 할 때마다 추가 적 인 재 귀 를 하지 않 아 도 된다.

//  
class TreeNode<T extends Comparable<T>> {
        private T data;
        private TreeNode left;
        private TreeNode right;
        //      
        private int height;
        TreeNode(T data) {
            this.data = data;
        }
    }

//    
private int getHeightRecord(TreeNode tree) {
        if (tree != null) {
            return tree.height;
        }
        return 0;
    }

//        
private TreeNode insertNode(TreeNode root, T data) {
        if (root == null) {
            root = new TreeNode<>(data);
        } else {
            int cmp = data.compareTo(root.data);
            if (cmp < 0) {
                root.left = insertNode(root.left, data);
            } else if (cmp > 0) {
                root.right = insertNode(root.right, data);
            } else {
                System.out.println("       ");
            }
        }
        root.height = Math.max(getHeightRecord(root.left), getHeightRecord(root.right)) + 1;
        return root;
    }

원 리 는 재 귀 탐색 과 마찬가지 로 이 조작 을 기록 했다.
노드 를 삽입 할 때 우 리 는 루트 노드 부터 적당 한 위 치 를 찾 아 삽입 합 니 다.[가장 깊 은 곳 에 도착 합 니 다.]
삽입 완료 후.[기록] 새로 삽 입 된 노드 의 높이 는 1 이다.
윗 층 으로 되돌아가다.
노드 가 새로 추 가 될 수 있 기 때문에 이 층 의 원래 기록 을 업데이트 합 니 다.
노드 의 height 속성 을 통 해 좌우 노드 의 높이 를 얻 고 최대 치 를 얻 습 니 다.
자신 자체 의 높이 1 을 더 하면 새로운 높이 다.다시 기록한다
Q3: 나무의 형 태 를 어떻게 수정 합 니까?
A3:
밸 런 스 상태 가 파괴 되면 네 가지 회전 을 통 해 나무의 형 태 를 수정 하 는 AVL 트 리 중 가장 까다 로 운 문제 다.각각 LL 회전, RR 회전, LR 회전, RL 회전 이다.
그 중에서 L 은 left, R 은 right 를 나타 낸다.
우 리 는 어떤 노드 의 균형 인자 가 2 에 도 달 했 을 때 나 무 는 이미 균형 을 잃 었 다 는 것 을 안다.그래서 한 노드 의 균형 인자 가 1 을 초과 할 때마다 나 는 이 노드 를 [파 괴 된 노드] 라 고 부른다.
다음은 개인 적 인 이해 입 니 다.
이런 LL, RR, LR, RL 은 모두 [파 괴 된 노드] 를 대상 으로 한다.
예 를 들 어 LL 은 [파 괴 된 노드] 의 [왼쪽 노드] 의 [왼쪽 노드] RL 을 말 하고 [파 괴 된 노드] 의 [오른쪽 노드] 의 [왼쪽 노드] 를 말한다.
글자 의 뜻 에서 회전 을 이해 하 는 것 을 명심 하 세 요.지정 한 노드 를 둘러싸 고 회전 합 니 다.내 가 어떤 노드 를 향상 시 키 겠 다 고 말 했 을 때 사실은 그 노드 를 중심 으로 회전 하 는 것 이다.
다음은 본론 으로 들 어가 4 대 회전.
LL 삽입 (왼쪽 회전):
[파 괴 된 노드] 의 [왼쪽 노드] 를 둘러싸 고 오른쪽으로 회전 합 니 다.
상황 1:
수정 방법: [파 괴 된 노드] 의 [왼쪽 노드] 를 뿌리 노드 로 승급 합 니 다.
상황 2:
수정 방법: 똑 같이 [파 괴 된 노드] 의 [왼쪽 노드] 를 뿌리 노드 로 향상 시 킵 니 다.
그러나 중요 한 것 은 [파 괴 된 노드] 의 [왼쪽 노드] 의 [오른쪽 노드] 이다. 위의 그림 에서 [노드 8] 과 같이 [좌우 노드] 라 고 부른다.
루트 노드 를 직접 올 리 면이때 뿌리 노드 에 세 개의 가지 가 있 을 것 이다. 이것 은 바람 직 하지 않다.
그래서 [노드 8] 을 이동 하여 [파 괴 된 노드] 의 [왼쪽 노드] 로 변경 합 니 다.([좌우 노드] 는 [파 괴 된 노드] 보다 작 을 것 이 고 [올 라 간 노드] 보다 클 것 이다)
그림 예시:

       2 ，       【    】               。
【  8】        【     】   

위 에서 언급 한 루트 노드 로 올 리 면 헷 갈 릴 수 있 고 [파 괴 된 노드] 로 올 라 가 는 [부모 노드] 로 이해 할 수 있 습 니 다.
종합 2 가지 상황:

1.   【     】 【    】    【   】

2. 【     】   【     】   。（         ）

3.      【     】 【    】   【     】   。（        ）

    private TreeNode singleLeftRotation(TreeNode tree) {
        //                 
        TreeNode root = tree.left;

        //            ，            
        tree.left = root.right == null ? null : root.right;

        //              
        root.right = tree;

        return root;
    }

RR 삽입 (오른쪽 회전):
[파 괴 된 노드] 의 [오른쪽 노드] 를 둘러싸 고 왼쪽으로 회전 합 니 다.
상황 1:
수정 방법: [파 괴 된 노드] 의 [오른쪽 노드] 를 뿌리 노드 로 승급 하면 됩 니 다.
상황 2:
수정 방법: [파 괴 된 노드] 의 [오른쪽 노드] 를 뿌리 노드 로 승급 가능.뿌리 노드 에 세 개의 가지 가 있 을 수 있 는데 이것 은 바람 직 하지 않다.
그래서 승급 후 [오른쪽 노드] 의 왼쪽 가 지 를 [파 괴 된 노드] 의 오른쪽으로 이동 합 니 다.(원인 은 [오른쪽 왼쪽 노드] 가 [파 괴 된 노드] 보다 크 고 [올 라 간 노드] 보다 작 을 것 이다)

   ，【    】6    【     】5   

종합 2 가지 상황:

1.   【     】 【    】    【   】

2. 【     】   【     】   。（         ）

3.      【     】 【    】   【     】   。（        ）

private TreeNode singleRightRotation(TreeNode tree) {
        //                 
        TreeNode root = tree.right;

        //            ，           
        tree.right = root.left == null ? null : root.left;

        //              
        root.left = tree;
        return root;
    }

LR 삽입 (좌 - 우 쌍 회전):
위의 그림 과 같이 [노드 7] 을 삽입 한 후에 [노드 9] 가 파괴 되 었 다.
또한 [노드 7] 은 [노드 9] 의 [왼쪽 노드] 의 [오른쪽 노드] 의 서브 노드 중 하나 이다.
LR 회전 수정 사용:

private TreeNode doubleLeftRightRotation(TreeNode tree) {
        tree.left = singleRightRotation(tree.left);
        return singleLeftRotation(tree);
    }

RL 삽입 (오른쪽 - 왼쪽 회전):
위의 그림 과 같이 [노드 9] 를 삽입 한 후에 [노드 7] 이 파괴 되 었 다.
또한 [노드 9] 는 [노드 7] 의 [오른쪽 노드] 의 [왼쪽 노드] 의 서브 노드 중 하나 이다.
RL 회전 수정 사용:

private TreeNode doubleRightLeftRotation(TreeNode tree) {
        tree.right = singleLeftRotation(tree.right);
        return singleRightRotation(tree);
    }

전체 코드 구현
테스트 와 실현 을 함께 놓 으 면 순 전 히 게으르다.

import java.util.ArrayDeque;
import java.util.ArrayList;
public class AVLTree<T extends Comparable<T>> {
    public static void main(String[] args) {
        System.out.println("  ：");
        int[] nodeValues = {9, 6, 10, 5, 8, 7, 11};
        AVLTree tree = initTreeAndShowData(nodeValues);
        System.out.println("  ：");
        tree.show(tree.root);

        System.out.println("  ：");
        nodeValues = new int[]{9};
        tree = initTreeAndShowData(nodeValues);
        System.out.println("  ：");
        tree.show(tree.root);

        System.out.println("  ：");
        nodeValues = new int[]{9, 3, 2, 1, 13, 80, 54, 26, 90, -3, 70, 24, 27, 8, 10};
        tree = initTreeAndShowData(nodeValues);
        System.out.println("  ：");
        tree.show(tree.root);

        System.out.println("  ：");
        nodeValues = new int[]{7, 5, 10, 8, 11, 9};
        tree = initTreeAndShowData(nodeValues);
        System.out.println("  ：");
        tree.show2(tree.root);
    }

    /**
     *               
     * @param nodeValues           
     * @return                
     */
    static AVLTree initTreeAndShowData(int[] nodeValues) {
        AVLTree tree = new AVLTree();
        for (int i = 0; i < nodeValues.length; i++) {
            tree.insert(nodeValues[i]);
            System.out.print(nodeValues[i] + " ");
        }
        System.out.println();
        return tree;
    }

    /****************************************************************************/

    /**
     *        
     */
    class TreeNode<T extends Comparable<T>> {
        private T data;
        private TreeNode left;
        private TreeNode right;
        private int height;
        TreeNode(T data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    private TreeNode root;

    AVLTree() {
        root = null;
    }

    /**
     *          
     * @param data             
     */
    public void insert(T data) {
        root = insertNode(root, data);
    }

    /**
     *           
     * @param root       
     * @param data         
     * @return           
     */
    private TreeNode insertNode(TreeNode root, T data) {
        if (root == null) {
            root = new TreeNode<>(data);
        } else {
            //               
            int cmp = data.compareTo(root.data);

            if (cmp < 0) {
                root.left = insertNode(root.left, data);
                //           1
                if (isLargerThanOne(root)) {
                    if (data.compareTo(root.left.data) < 0) {
                        //   
                        root = singleLeftRotation(root);
                    } else {
                        // -   
                        root = doubleLeftRightRotation(root);
                    }
                }
            } else if (cmp > 0) {
                root.right = insertNode(root.right, data);
                if (isLargerThanOne(root)) {
                    if (data.compareTo(root.right.data) > 0) {
                        //   
                        root = singleRightRotation(root);
                    } else {
                        // -   
                        root = doubleRightLeftRotation(root);
                    }
                }
            } else {
                System.out.println("       ");
            }
        }
        //      
        root.height = Math.max(getHeightRecord(root.left), getHeightRecord(root.right)) + 1;
        return root;
    }


    private boolean isLargerThanOne(TreeNode tree) {
        return Math.abs(getHeightRecord(tree.left) - getHeightRecord(tree.right)) > 1;
    }

    /**
     *                
     * @param tree       
     * @return            
     */
    private TreeNode singleLeftRotation(TreeNode tree) {
        //                 
        TreeNode root = tree.left;
        //            ，            
        tree.left = root.right == null ? null : root.right;
        //              
        root.right = tree;
        return root;
    }

    /**
     *                
     * @param tree       
     * @return            
     */
    private TreeNode singleRightRotation(TreeNode tree) {
        //                 
        TreeNode root = tree.right;
        //            ，           
        tree.right = root.left == null ? null : root.left;
        //              
        root.left = tree;
        return root;
    }

    /**
     *   LR  
     * @param tree       
     * @return            
     */
    private TreeNode doubleLeftRightRotation(TreeNode tree) {
        tree.left = singleRightRotation(tree.left);
        return singleLeftRotation(tree);
    }

    /**
     *   RL  
     * @param tree       
     * @return            
     */
    private TreeNode doubleRightLeftRotation(TreeNode tree) {
        tree.right = singleLeftRotation(tree.right);
        return singleRightRotation(tree);
    }

    /**
     *   tree   
     * @param tree      
     * @return     null，  0，      
     */
    private int getHeightRecord(TreeNode tree) {
        if (tree != null) {
            return tree.height;
        }
        return 0;
    }

    /**
     *           ，        
     * @param node        
     */
    public void show(TreeNode node) {
        ArrayDeque nodes = new ArrayDeque<>();
        int i = 0, n = 0;
        boolean isFirst = true;
        TreeNode t;
        nodes.add(node);
        while (nodes.size() != 0) {
            t = nodes.remove();
            System.out.print(t.data + "\t");
            if (++i == 2 << n || isFirst) {
                i = 0;
                n = isFirst ? n : n + 1;
                isFirst = false;
                System.out.println();
            }
            if (t.left != null) {
                nodes.add(t.left);
            }
            if (t.right != null) {
                nodes.add(t.right);
            }
        }
        System.out.println();
    }
    /**
     *           ，       
     * @param node        
     */
    public void show2(TreeNode node) {
        ArrayList nodes = new ArrayList();
        TreeNode t;
        nodes.add(0, node);
        int size = nodes.size();
        while (size != 0) {
            t = nodes.remove(0);
            if (t.left != null) {
                nodes.add(t.left);
            }
            if (t.right != null) {
                nodes.add(t.right);
            }

            if ((size = nodes.size()) != 0 && t.height == nodes.get(0).height) {
                System.out.print(t.data + "\t");
            } else {
                System.out.println(t.data);
            }
        }
    }

    /**
     *        ，         
     * @param tree    
     * @return      
     */
    private int getHeightRecursion(TreeNode tree) {
        if (tree == null) {
            return 0;
        }
        int left = getHeightRecursion(tree.left);
        int right = getHeightRecursion(tree.right);
        return (left > right ? left : right) + 1;
    }
}

결실
출력 결 과 를 단계별 로 전시 하 다.

  ：
9 6 10 5 8 7 11 
  ：
8   
6   10  
5   7   9   11  

  ：
9 
  ：
9   

  ：
9 3 2 1 13 80 54 26 90 -3 70 24 27 8 10 
  ：
13  
3   54  
1   9   26  80  
-3  2   8   10  24  27  70  90  

  ：
7 5 10 8 11 9 
  ：
8
7   10
5   9   11

END