솔

레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com 또한, 레드블랙 트리는 실제로 키값을 2개 가지진 않지만 2-3트리의 성질도 가지고 있습니다.https://sol248.tistory.com/63 2-3Tree (2-3트리)다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알..

https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com이전에 AVL트리의 특징과 구현하는 방법에 대해 알아보았습니다. 이번에는 AVL트리를 활용하여 간단한 영어사전을 만들어보겠습니다. AVL트리는 알아서 균형을 맞춰주는 트리 형태이기에  삽입, 삭제, 탐색의 시간 복잡도가 최악의 경우에도 O(log N) 이라는 장점이 있었죠. 마침 영어사전은 빠른 삽입, 빠른 삭제, 빠른 탐색이 요구되므로 한번 구..

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다바로 아래의 그림처럼 말이죠.  이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다. 이것을 가능하게 한 것이 바로 AVL 트리 입니다. 먼저 이진탐색트리의 코드부터 보겠습니다. 이진탐색트리 클래스)연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니..