이번에는 JS로 레드-블랙 트리를 구현하는 단계에 대해 자세히 설명하겠습니다. JS로 레드-블랙 트리를 구현할 때 주의사항은 무엇인가요?
레드-블랙 트리의 속성
다음 속성을 만족하는 이진 검색 트리는 레드-블랙 트리입니다
각 노드는 블랙 또는 레드입니다.
루트 노드는 검은색입니다.
각 리프 노드(NIL)는 검정색입니다.
노드가 빨간색이면 해당 하위 노드는 모두 검은색입니다.
각 노드에 대해 해당 노드에서 모든 하위 리프 노드까지의 단순 경로에는 동일한 수의 검정색 노드가 포함됩니다.
속성 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 중국어 웹사이트 기사에 나와 있습니다!
추천 자료:
에서 bass.scss를 전 세계적으로 도입하는 단계에 대한 자세한 설명위 내용은 JS에서 레드-블랙 트리를 구현하는 단계에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

去掉重复并排序的方法:1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句,去掉数组中的重复元素,返回去重后的新数组;2、利用sort()对去重数组进行排序,语法“去重数组.sort()”。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题,包括了Symbol类型的描述、Symbol不会隐式转字符串等问题,下面一起来看一下,希望对大家有帮助。

怎么制作文字轮播与图片轮播?大家第一想到的是不是利用js,其实利用纯CSS也能实现文字轮播与图片轮播,下面来看看实现方法,希望对大家有所帮助!

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于对象的构造函数和new操作符,构造函数是所有对象的成员方法中,最早被调用的那个,下面一起来看一下吧,希望对大家有帮助。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于面向对象的相关问题,包括了属性描述符、数据描述符、存取描述符等等内容,下面一起来看一下,希望对大家有帮助。

方法:1、利用“点击元素对象.unbind("click");”方法,该方法可以移除被选元素的事件处理程序;2、利用“点击元素对象.off("click");”方法,该方法可以移除通过on()方法添加的事件处理程序。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于BOM操作的相关问题,包括了window对象的常见事件、JavaScript执行机制等等相关内容,下面一起来看一下,希望对大家有帮助。

foreach不是es6的方法。foreach是es3中一个遍历数组的方法,可以调用数组的每个元素,并将元素传给回调函数进行处理,语法“array.forEach(function(当前元素,索引,数组){...})”;该方法不处理空数组。


핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

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

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

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

MinGW - Windows용 미니멀리스트 GNU
이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

ZendStudio 13.5.1 맥
강력한 PHP 통합 개발 환경
