밸 런 스 이 진 트 리 조정

 
  
一、平衡二叉树的构造
 
  
在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树
 
  
1.调整方法
 
  
（1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点
 
  
（2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。
 
  
2.调整方式
 
  
（1）LL型
 
  
LL型：插入位置为左子树的左结点，进行向右旋转
 
  
 
    
  
 
  
 
   由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。 
  
 
  
 
   （2）RR型 
  
 
  
 
   RR型：插入位置为右子树的右孩子，进行向左旋转 
  
 
  
 
   
 
     
   
 
   
 
    由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。 
   
 
   
 
    （3）LR型 
   
 
   
 
    LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。 
   
 
   
 
    
 
      
    
 
      
   
 
    由于在A的左子树B的右子树上插入了结点F，A的平衡因子由1变为了2，成为不平衡的最小二叉树根结点。第一次旋转A结点不动，先将B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。 
  
 
  
 
   （4）RL型 
  
 
  
 
   RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转；处理情况与LR类似。 
  
 
  
 
    
  
 
  
 
     
  
 
  
 
   
   
 
    
   
     
  
                               1，   3   ，             1  1，  ,           ，           ，  ，            ,
  

  
             
  
        
  

  
1. 균형 이 잡 힌 이 진 트 리 의 구조
이 진 트 리 에 결점 을 삽입 한 후 균형 이 진 트 리 로 조정 합 니 다.균형 이 잡 힌 이 진 트 리 에 새로운 결점 을 삽입 하면 균형 이 잡 힌 이 진 트 리 의 균형 성 을 깨 뜨 린 다.우선 새로운 결점 을 삽입 한 후 균형 을 잃 은 가장 작은 녀석 의 나무 뿌리 결점 의 지침 을 찾 아야 한다.그 다음 에 이 서브 트 리 에서 노드 간 의 링크 관 계 를 조정 하여 새로운 균형 서브 트 리 로 만 듭 니 다.균형 을 잃 은 최소 서브 트 리 가 균형 서브 트 리 로 조 정 된 후, 원래 의 다른 모든 불 균형 서브 트 리 는 조정 할 필요 가 없 으 며, 전체 이 진 트 리 는 또 하나의 균형 이 진 트 리 가 된다.
1. 조정 방법
(1) 삽입 점 위 치 는 반드시 이 진 트 리 의 성질 을 만족 시 켜 야 한다. 즉, 모든 나무의 왼쪽 결점 은 뿌리 결점 보다 작고 오른쪽 결점 은 뿌리 결점 보다 크다.
(2) 결점 을 삽입 한 후 불 균형 한 최소 이 진 트 리 를 찾 아 조정 하고 전체 트 리 가 불 균형 하면 전체 트 리 를 조정 한다.
2. 방식 조정
(1) LL 형
LL 형: 왼쪽 트 리 의 왼쪽 노드 를 삽입 하여 오른쪽으로 회전 합 니 다.
A 의 왼쪽 아이 B 의 왼쪽 트 리 에 결점 F 를 삽입 하기 때문에 A 의 균형 인 자 는 1 에서 2 로 변 하여 불 균형 한 최소 이 진 트 리 뿌리 결점 이 된다.이때 A 결점 은 시계 방향 으로 오른쪽으로 회전 하고 회전 과정 에서 '회전 우선' 의 규칙 에 따라 A 결점 은 D 결점 을 바 꾸 어 B 결점 의 오른쪽 자나무 가 되 고 D 결점 은 A 결점 의 왼쪽 아이 가 된다.
(2) RR 형
RR 형: 오른쪽 하위 트 리 의 오른쪽 아 이 를 삽입 하여 왼쪽으로 회전 합 니 다.
A 의 오른쪽 트 리 C 의 오른쪽 트 리 에 결점 F 를 삽 입 했 기 때문에 A 의 균형 인 자 는 - 1 에서 - 2 로 변 하여 불 균형 한 최소 이 진 트 리 뿌리 결점 이 되 었 다.이때 A 결점 은 시계 반대 방향 으로 왼쪽으로 회전 하 며 '회전 우선' 의 규칙 에 따라 A 결점 은 D 결점 을 C 의 왼쪽 자수 로 교체 하고 D 결점 은 A 의 오른쪽 자수 가 된다.
(3) LR 형
LR 형: 왼쪽 트 리 에 위치 한 오른쪽 아 이 를 삽입 할 때 두 번 회전 을 하고 왼쪽 회전 을 한 다음 에 오른쪽 회전 을 합 니 다.첫 번 째 최소 불 균형 서브 트 리 의 뿌리 노드 는 움 직 이지 않 고 노드 가 있 는 서브 트 리 를 조정 하고 두 번 째 는 최소 불 균형 서브 트 리 를 조정 합 니 다.
  
 A 의 왼쪽 트 리 B 의 오른쪽 트 리 에 결점 F 를 삽 입 했 기 때문에 A 의 평형 인 자 는 1 에서 2 로 변 하여 불 균형 한 최소 이 진 트 리 뿌리 결점 이 되 었 다.첫 번 째 회전 A 결점 이 움 직 이지 않 으 면 먼저 B 의 오른쪽 서브 트 리 의 뿌리 결점 D 를 왼쪽으로 회전 시 켜 B 결점 의 위치 로 올 린 다음 에 이 D 결점 을 오른쪽으로 회전 시 켜 A 결점 의 위치 로 올 린 다.
(4) RL 형
RL 형: 오른쪽 트 리 의 왼쪽 아 이 를 삽입 하여 두 번 조정 하고 오른쪽 회전 을 한 다음 에 왼쪽 회전 을 합 니 다.처리 상황 은 LR 과 유사 하 다.