AVL 트리 삭제 및 재구성

Question

노드를 AVL 트리에서 삭제할 때 한 번만 삽입하는 것과 달리 반복 횟수를 여러 번 재구성해야 할 수도 있습니다. 누구든지 저에게 삭제 사례를 보여줄 수 있습니까? 또한 AVL 트리를 구현했으며 delete() 함수가 제대로 작동하는지 확인하려고합니다. 그래서 삽입 (delete)이 정확하고 모든 것을 처리 하는지를 알아내는 데 도움이되는 삽입과 삭제의 순서를 줄 수 있습니까?

각 노드에 이름 (문자열)이 저장되어 있고 insertAVL (요소) 및 deleteAVL (요소) 함수가있는 AVL 트리가 있다고 가정합니다.

Answer 1

글쎄, 나무 위로 올라와야하기 때문에 삽입과 삭제 모두 여러 번 회전 할 수 있습니다.

예를 들어 {5,2,4,3,7,8,10,9}의 데이터 세트를 추가 한 다음 {5}을 제거하고 {9}를 추가하고 마지막으로 {2}을 제거합니다. 당신은 다음을 얻습니다.

addValue. id=5 
└── (1) 5 

addValue. id=2 
└── (2) 5 
    └── (1) 2 

addValue. id=4 
└── (3) 5 *unbalanced left 2 - right 0* 
    └── (2) 2 
     └── (1) 4 
After left rotation: 
└── (3) 5 *unbalanced left 2 - right 0* 
    └── (2) 4 
     └── (1) 2 
After right rotation: 
└── (2) 4 
    ├── (1) 2 
    └── (1) 5 

addValue. id=3 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (1) 5 

addValue. id=7 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (2) 5 
     └── (1) 7 

addValue. id=8 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 5 *unbalanced right 2 - left 0* 
     └── (2) 7 
      └── (1) 8 
After left rotation: 
└── (3) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (2) 7 
     ├── (1) 5 
     └── (1) 8 

addValue. id=10 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (2) 8 
      └── (1) 10 

addValue. id=9 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (3) 8 *unbalanced left 0 - right 2* 
      └── (2) 10 
       └── (1) 9 
After right rotation: 
└── (5) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (4) 7 
     ├── (1) 5 
     └── (3) 8 *unbalanced right 2 - left 0* 
      └── (2) 9 
       └── (1) 10 
After left rotation: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 
     ├── (1) 5 
     └── (2) 9 
      ├── (1) 8 
      └── (1) 10 

removeValue. value=5 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 7 *unbalanced right 2 - left 0* 
     └── (2) 9 
      ├── (1) 8 
      └── (1) 10 
After left rotation: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 9 
     ├── (2) 7 
     │ └── (1) 8 
     └── (1) 10 

addValue. id=9 
└── (5) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (4) 9 
     ├── (3) 7 *unbalanced right 2 - left 0* 
     │ └── (2) 8 
     │  └── (1) 9 
     └── (1) 10 
After left: 
└── (4) 4 
    ├── (2) 2 
    │ └── (1) 3 
    └── (3) 9 
     ├── (2) 8 
     │ ├── (1) 7 
     │ └── (1) 9 
     └── (1) 10 

removeValue. value=2 
└── (4) 4 *unbalanced right 3 - left 1* 
    ├── (1) 3 
    └── (3) 9 
     ├── (2) 8 
     │ ├── (1) 7 
     │ └── (1) 9 
     └── (1) 10 
After right rotation: 
└── (4) 4 *unbalanced right 3 - left 1* 
    ├── (1) 3 
    └── (3) 8 
     ├── (1) 7 
     └── (2) 9 
      ├── (1) 9 
      └── (1) 10 
After left rotation: 
└── (3) 8 
    ├── (2) 4 
    │ ├── (1) 3 
    │ └── (1) 7 
    └── (2) 9 
     ├── (1) 9 
     └── (1) 10 

자세히 알아 보려면 AVL 트리 here이 있습니다.