Module 8 - AVL

왜 AVL?

BST 에 worst case O(n)을 방지하기 위해서

inside of BST

updating height and BF

BF 가 1 이상 차이날때 unbalanced

AVL SINGLE ROTATIONS

알고리즘

remove (1)

1을 없애주면 unbalance 가 되니 4를 끓어올리고 2 를 4의 left child 로 바꾼다 5 와 3 은 그대로

Double rotation

오른쪽 child 가 left heavy 일때 필요

예시) B 를 A 의 right child 로 만든 후 left rotation 진행

 

vice versa

예시

right heavy => left heavy 이기 때문에 right => left rotation 사용

68 기준으로 right rotation 후 50 준으로 left rotation 

원래 62 의 left child 였던 54 도 같이 챙겨가는 모습

rotation type

public class BST {
  private class BSTNode {
    int data; 
    BSTNode left;
    BSTNode right;
  }
  private BSTNode root;
  private int size;

  /**
   * Counts the number of nodes within the given range.
   *
   * Example:
   *        4|
   *      /  |\
   *     2   | 6
   *    / \  |/ \
   *   1   3 5   7
   *         |
   * Here, the threshold is 5, so the method should return 5
   * (1, 2, 3, 4, 5) all are less than or equal to 5. Don’t forget efficiency.
   *
   * @param t the threshold to count values <= t
   * @return the final count of nodes within the bounds
   */
  public int countThresh(int t) {
    return countThresh(t, root);
  }

	private int countThresh(int t, BSTNode curr) {
    if (curr == null) {
        return 0;
    }
    if (curr.data > t) {
        return countThresh(t, curr.left);
    } else if (curr.data == t) {
        return 1 + countThresh(t, curr.left);
    } else {
        return 1 + countThresh(t, curr.left) + countThresh(t, curr.right);
    }
	}
}