안 드 로 이 드 데이터 구조 07 - AVL 트 리

데이터 구조 07 - AVL 트 리
1. AVL 트 리 의 기본 개념
1. AVL 트 리
AVL 트 리 는 각 노드 의 왼쪽 트 리 와 오른쪽 트 리 의 높이 차 이 는 최대 1 과 같은 자기 평형 이 진 트 리 입 니 다.
AVL 트 리 는 일반적인 이 진 트 리 보다 검색 효율 이 높 지만 삽입 삭제 효율 이 낮 습 니 다.
2. 평형 인자
밸 런 스 인자 (BF: Balance Factor) 는 이 진 트 리 에 있 는 노드 의 왼쪽 트 리 깊이 에서 오른쪽 트 리 깊이 를 뺀 값 입 니 다.
3. 최소 불 균형 서브 트 리
최소 불 균형 서브 트 리 는 삽입 노드 에서 가장 가 깝 고 균형 인자 의 절대 치가 1 보다 큰 노드 가 뿌리 인 서브 트 리 입 니 다.
노드 A 를 추가 한 후에 나무의 깊이 가 + 1 이면 A 의 모든 부모 노드 의 균형 인자 의 절대 치 는 + 1 이 되 고 A 와 가장 가 까 우 며 균형 인자 의 절대 치가 1 보다 큰 노드 B 는 전체 나무의 불 균형 을 초래 하 는 요소 이다. B 의 모든 부모 노드 의 균형 인자 가 B 를 삽입 하기 전에 0 이 될 것 이기 때문이다.
2. AVL 트 리 의 조작
AVL 트 리 의 삽입 은 항상 회전 이 필요 합 니 다. 왼쪽 회전 과 오른쪽 회전 입 니 다.
1. 좌선
왼쪽 회전 은 노드 A 를 A 의 오른쪽 노드 B 의 왼쪽 노드 로 바 꾸 고 B 의 원래 왼쪽 노드 를 A 의 오른쪽 노드 로 바 꾸 는 것 이다. 즉, A 를 왼쪽으로 한 명 아래로 옮 기 는 것 이다.

public void leftRoate(Node node) {
    if (node == null) {
        return;
    }

    Node right = node.right;
    // 1. node           node     
    node.right = right.left;
    if (right.left != null) {
        right.left.parent = node;
    }

    // 2. node       node        
    right.parent = node.parent;
    if (node.parent == null) {
        root = right;
    } else if (node.parent.right == node) {
        node.parent.right = right;
    } else if (node.parent.left == node) {
        node.parent.left = right;
    }

    // 3. node  node          
    right.left = node;
    node.parent = right;
}

2. 우회전
오른쪽 회전 은 노드 A 를 A 의 왼쪽 노드 B 의 오른쪽 노드 로 바 꾸 고 B 의 원래 오른쪽 노드 를 A 의 왼쪽 노드 로 바 꾸 는 것 이다. 즉, A 를 오른쪽으로 한 명 이동 하 는 것 이다.

public void rightRoate(Node node) {
    if (node == null) {
        return;
    }

    Node left = node.left;
    // 1. node           node     
    node.left = left.right;
    if (left.right != null) {
        left.right.parent = node;
    }

    // 2. node       node        
    left.parent = node.parent;
    if (node.parent == null) {
        root = left;
    } else if (node.parent.left == node) {
        node.parent.left = left;
    } else if (node.parent.right == node) {
        node.parent.right = left;
    }

    // 3. node  node          
    left.right = node;
    node.parent = left;
}

3. AVL 트 리 의 삽입
AVL 트 리 의 삽입 은 매우 복잡 해서 세 단계 로 나 눌 수 있 습 니 다. 추가, 균형 검사, 균형 수정.
여기에 새로 추 가 된 노드 를 A 로 기록 하고 A 의 부모 노드 를 B 로 기록 하 며 찾 은 최소 불 균형 서브 트 리 를 C 로 기록 합 니 다.
1. 추가
첫 번 째 단 계 는 두 갈래 검색 트 리 의 삽입 과 같 습 니 다.
2. 밸 런 스 체크
(1) A 가 왼쪽 노드 라면 B 의 균형 인자 + 1;A 가 오른쪽 노드 라면 B 의 균형 인자 - 1.
(2) B 의 균형 인 자 를 판단 한다.

만약 에 = 0 이 전체 나무의 깊이 가 변 하지 않 았 다 는 것 을 설명 하면 B 의 모든 부모 노드 의 균형 요 소 는 영향 을 받 지 않 기 때문에 전체 나 무 는 균형 적 이 고 수정 할 필요 가 없다.

만약 에 = 1 또는 = - 1 이 나무의 깊이 가 변 했다 는 것 을 설명 하면 부모 노드 를 옮 겨 다 니 고 (1), (2) 의 조작 을 반복 한다. 균형 인자 의 절대 치 = 2 의 부모 노드, 즉 최소 불 균형 서브 트 리 C 를 찾 을 때 까지.

3. 밸 런 스 수정
마지막 단계 에서 찾 은 최소 불 균형 서브 트 리 C 를 수정 하면 4 가지 상황 으로 나 눌 수 있 습 니 다.

단 방향 우회전 RR: C 의 왼쪽 부분 노드 의 왼쪽 부분 트 리 에 노드 를 삽입 하기 때문에 C 의 균형 인 자 는 1 에서 2 로 증가 하여 C 를 뿌리 로 하 는 부분 트 리 가 균형 을 잃 으 면 C 의 우회전 작업 을 해 야 한다.

단 방향 좌선 LL: C 의 오른쪽 하위 노드 의 오른쪽 하위 트 리 에 노드 를 삽입 하기 때문에 C 의 균형 인 자 는 - 1 에서 - 2 로 바 뀌 어 C 를 뿌리 로 하 는 하위 트 리 가 균형 을 잃 으 면 C 의 좌선 작업 을 한 번 해 야 한다.

왼쪽 에서 오른쪽으로 LR: C 의 왼쪽 부분 노드 의 오른쪽 부분 트 리 에 노드 를 삽입 하기 때문에 C 의 균형 인 자 는 1 에서 2 로 증가 하여 C 를 뿌리 로 하 는 부분 트 리 가 균형 을 잃 으 면 두 번 회전 을 해 야 한다. 먼저 C 의 왼쪽 부분 을 좌회전 한 다음 에 C 를 우회전 해 야 한다.

오른쪽 에서 왼쪽 RL: C 의 오른쪽 부분 노드 의 왼쪽 부분 트 리 에 노드 를 삽입 하기 때문에 C 의 균형 요 소 는 - 1 에서 - 2 로 바 뀌 어서 C 를 뿌리 로 하 는 부분 트 리 가 균형 을 잃 으 면 두 번 회전 을 해 야 한다. 먼저 C 의 오른쪽 부분 을 우회전 한 다음 에 C 를 좌회전 해 야 한다.

4. 코드 구현
요소 추가:

public void put(E data) {
    Node now = new Node(data);
    if (root == null) {
        root = now;
        return;
    }

    Node parent = root;
    //   :          
    while (parent != null) {
        if (data.compareTo(parent.data) < 0) {
            if (parent.left == null) {
                parent.left = now;
                now.parent = parent;
                break;
            } else {
                parent = parent.left;
            }
        } else if (data.compareTo(parent.data) > 0) {
            if (parent.right == null) {
                parent.right = now;
                now.parent = parent;
                break;
            } else {
                parent = parent.right;
            }
        } else {
            return;
        }
    }

    //     ，    
    while (parent != null) {
        //            ，          +1
        if (data.compareTo(parent.data) < 0) {
            parent.bran++;
            //            ，          -1
        } else {
            parent.bran--;
        }

        if (parent.bran == 0) {
            break;
        } else if (Math.abs(parent.bran) == 2) {
            //       
            fixAfterInsertion(parent);
            break;
        } else {
            parent = parent.parent;
        }
    }
}

수정 위치:

private void fixAfterInsertion(Node parent) {
    if (parent.bran == 2) {
        leftBranch(parent);
    }
    if (parent.bran == -2) {
        rightBranch(parent);
    }
}

왼쪽 트 리 동작:

public void leftBranch(Node node) {
    if (node == null) {
        return;
    }

    Node left = node.left;
    //    
    if (left.bran == LH) {
        rightRoate(node);
        //       0
        node.bran = EH;
        left.bran = EH;

        //   ，   。
    } else if (left.bran == RH) {
        Node lr = left.right;
        leftRoate(left);
        rightRoate(node);
        //2    ，left  lr     ，node  lr     
        if (lr.bran == LH) {
            node.bran = RH;
            left.bran = EH;
            lr.bran = EH;
        } else if (lr.bran == RH) {
            node.bran = EH;
            left.bran = LH;
            lr.bran = EH;
            // lr      
        } else if (lr.bran == EH) {
            node.bran = EH;
            left.bran = EH;
            lr.bran = EH;
        }
    }
}

오른쪽 하위 트 리 조작:

public void rightBranch(Node node) {
    if (node == null) {
        return;
    }

    Node right = node.right;
    //    
    if (right.bran == RH) {
        leftRoate(node);
        //       0
        node.bran = EH;
        right.bran = EH;
        //   ，   。
    } else if (right.bran == LH) {
        Node rl = right.left;
        rightRoate(right);
        leftRoate(node);
        //2    ，right  rl     ，node  rl     
        if (rl.bran == LH) {
            node.bran = EH;
            right.bran = RH;
            rl.bran = EH;
        } else if (rl.bran == RH) {
            node.bran = LH;
            right.bran = EH;
            rl.bran = EH;
            // rl      
        } else if (rl.bran == EH) {
            node.bran = EH;
            right.bran = EH;
            rl.bran = EH;
        }
    }
}

4. AVL 트 리 의 삭제
AVL 트 리 에서 삭제 하면 삭제 할 노드 를 아래로 한 잎 노드 로 회전 시 킨 다음 에 이 잎 노드 를 직접 잘라 서 완성 할 수 있 습 니 다.
코드 없 음...
5. AVL 트 리 찾기
AVL 트 리 찾기 는 이 진 트 리 찾기 와 같 습 니 다.
마지막.
코드 주소:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/datastructure/tree/TreeAVL.java
데이터 구조 와 알고리즘 테마:https://www.jianshu.com/nb/25128590
좋아요, 좋아요, 감사합니다!