좌편향적홍흑나무

Left-leaning red–black tree
좌편향적홍흑나무
유형나무
발명된2008
발명된 사람로버트 세지윅
큰 O 표기법에서의 시간 복잡성
알고리즘. 평균 최악의 경우
공간 O(n) O(n)
검색 O(log n) O(log n)
삽입하다 O(log n) O(log n)
삭제 O(log n) O(log n)

왼쪽 편향 적색-흑색(LLRB) 트리는 자기 균형 이진 검색 트리의 일종이다.적색-흑색 나무의 변종이며 동일한 무증상 복잡성을 운영에도 보장하지만, 구현이 용이하도록 설계되었다.

왼쪽 편향 적색 흑색 나무의 특성

제안된 모든 적색-흑색 트리 알고리즘은 N 키의 트리에서 로그 N의 작은 상수 배수로 경계된 최악의 경우 검색 시간으로 특징지어지며, 실제로 관찰된 동작은 일반적으로 pe에서 관찰될 수 있는 최적의 로그 N 노드에 가까운 최악의 경우보다 더 빠른 동일한 배수로 되어 있다.바싹 균형 잡힌 나무

특히, N 무작위 키로 만들어진 왼쪽 편 빨간색-검은색 2–3 나무의 경우:

  • 랜덤하게 성공한 검색은 로그2 N - 0.5 노드를 검사한다.
  • 평균 트리 높이는 약 2 로그2 N이다.
  • 왼쪽 하위 트리의 평균 크기는 로그 스케일링 동작을 나타낸다.

외부 링크

페이퍼스

구현

작가 날짜 언어 변종 메모들 링크
로버트 세지윅 2008 자바 이 Sedgewick 논문에서
데이비드 앤슨 2009년 6월 2일 C# 균형 유지:의 다용도 적갈색 트리 구현.네트
카즈-스파이브 2011 하스켈 llrbtree(데이터).세트.LLRBTree)
리 스탠자 2010 C++ 토론 포함 균형 잡힌 나무, 제4부: 왼쪽 기울어진 붉은색-검은색 나무
제이슨 에번스 2010 C 2-3 rb.h
니콜라 보르티뇽 2010년 12월 8일 액션스크립트 3 AS3 구현 및 토론
윌리엄 애런 2011 C 부모 포인터가 있는 반복을 사용하는 2-3 변종 llrb.h: 좌편향 적-검은 나무
마키에 피쵸카 2009 발라 Gee.TreeMap
페타르 메이문코프 2010 가다 2-3 고엘RB
세바스티앙 차푸스 2015 C C - 좌편향 rbtree 구현


김승영 2015 C 2-3-4 변종 C 구현
로빈 헤그겔룬트 한센 2018 엘름 엘름 구현
R 프라탑 차크라바시 2019 녹 녹 이행
막스 고렌 2022 C++ 2-3 전체 재귀 구현 C++ 구현
발레리아노 델라 롱가 2021 스위프트 2-3 firstIndex, endIndex, first, last, min 및 max에 대한 O(1) 복잡성을 가진 양방향 수집 프로토콜 준수. 신속한 구현
필자와 아흐메드 2021 파이톤 https://www.youtube.com/channel/UCm68_MratG7meGtzTbkS_3g/featured

기타


Stub icon

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.