찾다
웹 프론트엔드JS 튜토리얼JS에서 레드-블랙 트리를 구현하는 단계에 대한 자세한 설명

이번에는 JS로 레드-블랙 트리를 구현하는 단계에 대해 자세히 설명하겠습니다. JS로 레드-블랙 트리를 구현할 때 주의사항은 무엇인가요?

레드-블랙 트리의 속성

다음 속성을 만족하는 이진 검색 트리는 레드-블랙 트리입니다

  1. 각 노드는 블랙 또는 레드입니다.

  2. 루트 노드는 검은색입니다.

  3. 각 리프 노드(NIL)는 검정색입니다.

  4. 노드가 빨간색이면 해당 하위 노드는 모두 검은색입니다.

  5. 각 노드에 대해 해당 노드에서 모든 하위 리프 노드까지의 단순 경로에는 동일한 수의 검정색 노드가 포함됩니다.

속성 1과 2는 너무 많이 설명할 필요가 없습니다.

속성 3, 각 리프 노드(NIL)는 검정색입니다. 여기서 리프 노드는 위 그림의 노드 1, 5, 8, 15를 의미하는 것이 아니라 아래 그림의 null 값을 갖는 노드를 의미하며 색상은 검정색이며 부모 노드의 자식 노드입니다. .

속성 4, 노드가 빨간색인 경우(그림에서는 빨간색 대신 흰색이 사용됨) 노드 2,5,8,15와 같이 두 하위 노드는 검은색입니다. 그러나 노드의 두 하위 노드가 모두 검은색인 경우 노드 1과 같이 해당 노드는 빨간색이 아닐 수 있습니다.

속성 5, 각 노드에 대해 해당 노드에서 모든 하위 리프 노드까지의 단순 경로에는 동일한 수의 검정색 노드가 포함됩니다. 예를 들어, 노드 2에서 모든 하위 리프 노드까지의 단순 경로에서 검정 노드 수는 2이고, 루트 노드 11에서 모든 하위 리프 노드까지의 단순 경로에서 검정 노드 수는 2입니다. .

그런 나무의 특징은 무엇인가요?

루트에서 리프 노드까지의 단순 경로에서 각 노드의 색상을 제한함으로써 레드-블랙 트리는 대략적으로 균형을 이루기 때문에 어떤 경로도 다른 경로보다 두 배 더 길지 않도록 보장합니다. ——"알고리즘 소개"

속성 4로 인해 레드-블랙 트리에서는 두 개의 레드 노드가 인접하지 않습니다. 트리에서 가능한 가장 짧은 경로는 모두 검은색 노드가 있는 경로이고, 트리에서 가능한 가장 긴 경로는 빨간색 노드와 검은색 노드가 교대로 있는 경로입니다. 속성 5와 결합하면 각 경로에는 동일한 수의 검정색 노드가 포함되므로 레드-블랙 트리는 경로가 다른 경로보다 두 배 길지 않도록 보장합니다.

레드-블랙 트리 삽입

먼저 이진 검색 트리에 노드를 삽입하고 빨간색으로 색칠합니다. 검정색이면 속성 5를 위반하므로 조정이 불편하고, 빨간색이면 속성 2나 속성 4를 위반할 수 있습니다. 비교적 간단한 작업을 통해 레드-블랙 트리의 속성으로 복원할 수 있습니다.

이진 검색 트리에 노드가 삽입된 후 다음과 같은 상황이 발생할 수 있습니다.

사례 1

노드가 삽입된 후 상위 노드가 없고 해당 노드가 삽입되어 루트 노드가 되며, 속성 2를 위반하면 노드를 검정색으로 조정하고 삽입을 완료합니다.

사례 2

노드를 삽입한 후 해당 상위 노드는 검정색이고 속성을 위반하지 않았으며 조정이 필요하지 않으며 삽입이 완료되었습니다. 예를 들어 아래 그림에 노드 13을 삽입합니다.

사례 3

노드를 삽입한 후 상위 노드는 빨간색으로 속성 4를 위반하고 일련의 조정이 필요합니다. 예를 들어 아래 그림에 노드 4를 삽입합니다.

그렇다면 일련의 조정은 무엇일까요?

삽입된 노드의 상위 노드 아버지가 빨간색이면 노드 아버지는 검은색 부모 노드 할아버지를 가져야 합니다. 왜냐하면 노드 아버지가 상위 노드가 없으면 루트 노드이고 루트 노드이기 때문입니다. 검정색이에요. 그런 다음 노드 할아버지의 다른 자식 노드를 노드 아버지의 형제 노드인 노드 삼촌이라고 부를 수 있습니다. 노드 삼촌은 검은색이거나 빨간색일 수 있습니다.

복잡한 상황도 단순한 상황으로 바뀔 수 있기 때문에 가장 단순한 상황부터 분석해 보겠습니다. 단순한 상황은 노드 아저씨가 흑인인 상황입니다.

시나리오 3.1

위의 (a)와 같이 상황은 이렇습니다. 노드는 빨간색, 아버지는 빨간색, 할아버지와 삼촌은 검은색, α, β, θ, Ω, eta는 모두 해당됩니다. 노드 하위 트리. 전체 이진 검색 트리에서 속성 4 위반으로 인해 노드와 아버지만이 정상적인 레드-블랙 트리가 될 수 없다고 가정합니다. 이때 그림 (a)를 그림 (b)로 조정하면 정상적인 레드-블랙 트리로 복원할 수 있습니다. 검은 나무. 전체 조정 프로세스는 실제로 회전과 색상 변경의 두 단계로 나뉩니다.

회전이란 무엇인가요?

위 그림 (c)에 표시된 것처럼 이진 검색 트리의 일부입니다. 여기서 x, y는 노드이고 α, β, θ는 해당 노드의 하위 트리입니다. α

노드는 빨간색, 아버지는 빨간색, 할아버지와 삼촌은 검은색입니다. 특정 상황 1

그림 (a)에서 노드는 아버지의 왼쪽 자식 노드이고, 아버지는 그랜드의 왼쪽 자식 노드입니다.

색상 변경

그래서 그림(a)을 회전시킨 후 그랜드는 빨간색으로, 아버지는 검은색으로 바뀌고 그림(b)가 되어 삽입이 완료됩니다.

노드는 빨간색, 아버지는 빨간색, 할아버지와 삼촌은 검은색입니다. 구체적인 사례 2.

노드는 아버지의 오른쪽 자식 노드이고, 아래 그림(e)에 표시된 대로 아버지는 오른쪽 자식 노드입니다. , 이는 특정 사례입니다.

즉, 삼촌

노드가 빨간색, 아버지가 빨간색, 할아버지와 삼촌이 검은색인 구체적인 사례 3입니다.

노드는 아버지의 오른쪽 자식 노드이고 아버지는 그랜드의 왼쪽 자식 노드입니다. 아래에.

그림(m)에서 노드와 아버지를 회전하면 그림(n)이 됩니다. 아버지를 새로운 노드로 취급하여 특정 상황이 됩니다. 1. 다시 회전하고 색상을 변경하여 삽입을 완료합니다.

노드는 빨간색, 아버지는 빨간색, 할아버지와 삼촌은 검은색, 특정 사례 4.

노드는 아래 그림 (i)에 표시된 대로 아버지의 오른쪽 자식 노드이고 아버지는 그랜드의 왼쪽 자식 노드입니다. 구체적인 경우입니다. 3. 뒤집기.

그림(i)에서 노드와 아버지를 회전시키면 그림(j)가 됩니다. 아버지를 새로운 노드로 취급하여 특정 상황이 됩니다. 2. 다시 회전하고 색을 변경하여 삽입을 완료합니다.

사례 3.2

노드, 아버지와 삼촌은 빨간색, 할아버지는 검은색입니다.

위 그림(k)처럼 회전하는 대신 그랜드는 빨간색으로, 아버지와 삼촌은 검은색으로, 그랜드는 상황을 판단하는 새로운 노드로 활용됩니다. grand를 새로운 노드로 사용하면 Case 2가 되고, Case 3.1이 되면 삽입이 완료되고, 조정 후에도 여전히 Case 3.2이면 삽입이 완료되고, grand, father의 색상을 계속 변경한다. 및 삼촌, 노드 노드가 위로 이동합니다. 새 노드에 상위 노드가 없으면 케이스 1이 됩니다. 루트 노드는 검은색으로 표시되고 삽입이 완료됩니다.

요약하자면

노드 상황 작업
케이스 1 노드는 빨간색이고, father는 없습니다. 노드 색상 변경
케이스 2 노드는 빨간색이고 아버지는 빨간색입니다. black
Case 3.1 노드,아버지는 빨간색,할아버지,삼촌은 흑인 한두 번 회전하고 다시 색칠하세요
Case 3.2 노드,아버지,삼촌은 빨간색, 그랜드는 검정색 아버지, 삼촌, 할아버지, 할아버지를 다시 칠하는 것이 새로운 노드입니다

Code

// 结点
function Node(value) {
 this.value = value
 this.color = 'red' // 结点的颜色默认为红色
 this.parent = null
 this.left = null
 this.right = null
}
function RedBlackTree() {
 this.root = null
}
RedBlackTree.prototype.insert = function (node) {
 // 以二叉搜索树的方式插入结点
 // 如果根结点不存在,则结点作为根结点
 // 如果结点的值小于node,且结点的右子结点不存在,跳出循环
 // 如果结点的值大于等于node,且结点的左子结点不存在,跳出循环
 if (!this.root) {
 this.root = node
 } else {
 let current = this.root
 while (current[node.value  tree.insert(new Node(i)))
debugger

이 기사의 사례를 읽으신 후 방법을 마스터하셨다고 생각합니다. 더 흥미로운 정보를 보려면 다른 관련 주제에 주목하세요. PHP 중국어 웹사이트 기사에 나와 있습니다!

추천 자료:

js 중복 제거 및 숫자 배열 최적화

Vue

에서 bass.scss를 전 세계적으로 도입하는 단계에 대한 자세한 설명

위 내용은 JS에서 레드-블랙 트리를 구현하는 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
JavaScript의 역할 : 웹 대화식 및 역동적 인 웹JavaScript의 역할 : 웹 대화식 및 역동적 인 웹Apr 24, 2025 am 12:12 AM

JavaScript는 웹 페이지의 상호 작용과 역학을 향상시키기 때문에 현대 웹 사이트의 핵심입니다. 1) 페이지를 새로 고치지 않고 콘텐츠를 변경할 수 있습니다. 2) Domapi를 통해 웹 페이지 조작, 3) 애니메이션 및 드래그 앤 드롭과 같은 복잡한 대화식 효과를 지원합니다. 4) 성능 및 모범 사례를 최적화하여 사용자 경험을 향상시킵니다.

C 및 JavaScript : 연결이 설명되었습니다C 및 JavaScript : 연결이 설명되었습니다Apr 23, 2025 am 12:07 AM

C 및 JavaScript는 WebAssembly를 통한 상호 운용성을 달성합니다. 1) C 코드는 WebAssembly 모듈로 컴파일되어 컴퓨팅 전력을 향상시키기 위해 JavaScript 환경에 도입됩니다. 2) 게임 개발에서 C는 물리 엔진 및 그래픽 렌더링을 처리하며 JavaScript는 게임 로직 및 사용자 인터페이스를 담당합니다.

웹 사이트에서 앱으로 : 다양한 JavaScript 애플리케이션웹 사이트에서 앱으로 : 다양한 JavaScript 애플리케이션Apr 22, 2025 am 12:02 AM

JavaScript는 웹 사이트, 모바일 응용 프로그램, 데스크탑 응용 프로그램 및 서버 측 프로그래밍에서 널리 사용됩니다. 1) 웹 사이트 개발에서 JavaScript는 HTML 및 CSS와 함께 DOM을 운영하여 동적 효과를 달성하고 jQuery 및 React와 같은 프레임 워크를 지원합니다. 2) 반응 및 이온 성을 통해 JavaScript는 크로스 플랫폼 모바일 애플리케이션을 개발하는 데 사용됩니다. 3) 전자 프레임 워크를 사용하면 JavaScript가 데스크탑 애플리케이션을 구축 할 수 있습니다. 4) node.js는 JavaScript가 서버 측에서 실행되도록하고 동시 요청이 높은 높은 요청을 지원합니다.

Python vs. JavaScript : 사용 사례 및 응용 프로그램 비교Python vs. JavaScript : 사용 사례 및 응용 프로그램 비교Apr 21, 2025 am 12:01 AM

Python은 데이터 과학 및 자동화에 더 적합한 반면 JavaScript는 프론트 엔드 및 풀 스택 개발에 더 적합합니다. 1. Python은 데이터 처리 및 모델링을 위해 Numpy 및 Pandas와 같은 라이브러리를 사용하여 데이터 과학 및 기계 학습에서 잘 수행됩니다. 2. 파이썬은 간결하고 자동화 및 스크립팅이 효율적입니다. 3. JavaScript는 프론트 엔드 개발에 없어서는 안될 것이며 동적 웹 페이지 및 단일 페이지 응용 프로그램을 구축하는 데 사용됩니다. 4. JavaScript는 Node.js를 통해 백엔드 개발에 역할을하며 전체 스택 개발을 지원합니다.

JavaScript 통역사 및 컴파일러에서 C/C의 역할JavaScript 통역사 및 컴파일러에서 C/C의 역할Apr 20, 2025 am 12:01 AM

C와 C는 주로 통역사와 JIT 컴파일러를 구현하는 데 사용되는 JavaScript 엔진에서 중요한 역할을합니다. 1) C는 JavaScript 소스 코드를 구문 분석하고 추상 구문 트리를 생성하는 데 사용됩니다. 2) C는 바이트 코드 생성 및 실행을 담당합니다. 3) C는 JIT 컴파일러를 구현하고 런타임에 핫스팟 코드를 최적화하고 컴파일하며 JavaScript의 실행 효율을 크게 향상시킵니다.

자바 스크립트 행동 : 실제 예제 및 프로젝트자바 스크립트 행동 : 실제 예제 및 프로젝트Apr 19, 2025 am 12:13 AM

실제 세계에서 JavaScript의 응용 프로그램에는 프론트 엔드 및 백엔드 개발이 포함됩니다. 1) DOM 운영 및 이벤트 처리와 관련된 TODO 목록 응용 프로그램을 구축하여 프론트 엔드 애플리케이션을 표시합니다. 2) Node.js를 통해 RESTFULAPI를 구축하고 Express를 통해 백엔드 응용 프로그램을 시연하십시오.

JavaScript 및 웹 : 핵심 기능 및 사용 사례JavaScript 및 웹 : 핵심 기능 및 사용 사례Apr 18, 2025 am 12:19 AM

웹 개발에서 JavaScript의 주요 용도에는 클라이언트 상호 작용, 양식 검증 및 비동기 통신이 포함됩니다. 1) DOM 운영을 통한 동적 컨텐츠 업데이트 및 사용자 상호 작용; 2) 사용자가 사용자 경험을 향상시키기 위해 데이터를 제출하기 전에 클라이언트 확인이 수행됩니다. 3) 서버와의 진실한 통신은 Ajax 기술을 통해 달성됩니다.

JavaScript 엔진 이해 : 구현 세부 사항JavaScript 엔진 이해 : 구현 세부 사항Apr 17, 2025 am 12:05 AM

보다 효율적인 코드를 작성하고 성능 병목 현상 및 최적화 전략을 이해하는 데 도움이되기 때문에 JavaScript 엔진이 내부적으로 작동하는 방식을 이해하는 것은 개발자에게 중요합니다. 1) 엔진의 워크 플로에는 구문 분석, 컴파일 및 실행; 2) 실행 프로세스 중에 엔진은 인라인 캐시 및 숨겨진 클래스와 같은 동적 최적화를 수행합니다. 3) 모범 사례에는 글로벌 변수를 피하고 루프 최적화, Const 및 Lets 사용 및 과도한 폐쇄 사용을 피하는 것이 포함됩니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SecList

SecList

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.

PhpStorm 맥 버전

PhpStorm 맥 버전

최신(2018.2.1) 전문 PHP 통합 개발 도구

WebStorm Mac 버전

WebStorm Mac 버전

유용한 JavaScript 개발 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는