이 글에서는 자바스크립트 학습을 위한 확실한 참고자료와 가치가 있는 javascript 알고리즘의 이진 검색 트리 샘플 코드를 주로 소개합니다. 자바스크립트에 관심 있는 친구들은 이 글을 참고해보세요.
이진 트리란 무엇인가요?
이진 트리는 트리의 각 노드가 최대 2개의 자식 노드만 가질 수 있다는 것을 의미합니다.
이진 검색 트리란 무엇입니까
이진 트리를 기반으로 추가 조건이 있습니다. 즉, 이진 트리가 값을 삽입합니다. 삽입된 값이 현재 노드보다 작으면 왼쪽 노드에 삽입하고, 그렇지 않으면 삽입 프로세스 중에 왼쪽 노드 또는 오른쪽 노드가 이미 존재하는 경우 오른쪽 노드에 삽입한 다음 다음에 따라 계속 비교합니다. 새 노드를 만날 때까지 위의 규칙을 따릅니다.
이진 검색 트리의 특성
독특한 데이터 구조로 인해 이진 검색 트리의 시간 복잡도는 추가, 삭제 또는 검색 여부에 관계없이 O(h)입니다. h는 이진 트리의 높이입니다. 따라서 이진 트리는 최대한 짧아야 합니다. 즉, 왼쪽 노드와 오른쪽 노드의 균형이 최대한 맞아야 합니다.
이진 검색 트리 구축
이진 검색 트리를 구축하려면 먼저 이진 트리의 노드 클래스를 구축해야 합니다. 이진 트리의 특성을 보면 각 노드 클래스에는 왼쪽 노드, 오른쪽 노드와 값 자체가 있으므로 노드 클래스는 다음과 같습니다.
class Node { constructor(key) { this.key = key; this.left = null; this.right = null; } }
그런 다음 이진 검색 트리를 구성합니다
class Tree{ constructor(param = null) { if (param) { this.root = new Node(param); } else { this.root = null; } } }
여기서. 루트는 현재 object의 트리입니다.
이진 검색 트리의 왼쪽 하위 트리가 노드보다 작고 오른쪽 하위 트리의 다른 노드가 더 큰 특성으로 인해 새로운 알고리즘을 작성하기 쉽습니다. 이진 검색 트리의 경우 다음과 같습니다.insert(key) { if (this.root === null) { this.root = new Node(key); } else { this._insertNode(this.root, key); } } _insertNode(node, key) { if (key < node.key) { if (node.left === null) { node.left = new Node(key);{1} } else { this._insertNode(node.left, key);{2} } } else if (key > node.key) { if (node.right === null) { node.right = new Node(key);{3} } else { this._insertNode(node.right, key);{4} } } }위 코드는 먼저 새 키와 현재 노드의 키 크기를 결정합니다. 크기가 작으면 null 왼쪽 하위 노드를 찾을 때까지 왼쪽 하위 노드를 재귀적으로 탐색합니다. 현재 노드보다 크면 동일한 원칙이 적용됩니다. 위의 코드 {1}{2}{3}{4}가 this.root의 값을 변경할 수 있는 이유는 자바스크립트 함수가 값으로 전달되고, 매개변수가 기본이 아닌 유형(예: 여기서 객체의 값은 메모리이므로 this.root의 내용은 매번 직접 변경됩니다.
이진 검색 트리 순회
이진 검색 트리는 사전 주문, 중간 주문, 사후 주문의 세 가지 순회 방법으로 나뉩니다.inOrderTraverse(callback) { this._inOrderTraverse(this.root, callback); } _inOrderTraverse(node, callback) { if (node) { this._inOrderTraverse(node.left, callback); callback(node.key); this._inOrderTraverse(node.right, callback); } }위는 순서대로 순회하는 것입니다.
검색은 매우 간단합니다. 왼쪽 자식 노드가 노드보다 작고 오른쪽 자식 노드가 노드보다 크다는 원리를 기반으로 루프 판단을 하면 됩니다. search(value) {
if (this.root) {
if (value === this.root.key) {
return true;
} else {
return this._searchNode(value, this.root);
}
}
throw new Error('this.root 不存在');
}
_searchNode(value, node) {
if (!node) {
return false;
}
if (value === node.key) {
return true;
}
if (value > node.key) {
return this._searchNode(value, node.right);
} else if (value < node.key) {
return this._searchNode(value, node.left);
}
}
삭제는 더 복잡하며 상황에 따라 판단해야 합니다.
먼저 노드에 왼쪽 하위 트리가 있는지 확인하고 왼쪽 하위 트리가 없으면 루트를 직접 제거합니다. 오른쪽 하위 트리 노드는 삭제된 노드를 대체합니다.remove(key) { this._removeNode(this.root, key); } _removeNode(node, value) { if (!node) { return null; } if (value > node.key) { node.right = this._removeNode(node.right, value); } else if (value < node.key) { node.left = this._removeNode(node.left, value); } else { // 如果没有左子树,那么将右子树根节点作为替换节点 if (!node.left) { return node.right; // 如果存在左子树,那么取右子树最小节点作为替换节点 } else if (node.left) { return this._minNode(node.right); } } }
일반적으로 이 간단한 이진 검색 트리 학습을 통해, 재귀에 대한 나의 이전 이해는 단순한 이론적 개념에 불과했습니다. 이 심층적인 연습을 통해 재귀에 대한 이해가 많이 깊어졌습니다.
수학 공부가 생각나네요. 수학의 이론적 공식은 기억하기 쉽고 마스터하기 쉽습니다. 지식 포인트를 마스터하는 데 필요한 전체 점수가 10점이라면 실제로 연습하기 전까지는 마스터하는 정도만 보면 됩니다. 공식은 단지 몇 개의 문장과 몇 가지 원리로 매우 간단하기 때문에 2점이 될 수 있지만, 직면하는 문제는 이론을 진정으로 실천하고 다양한 실천을 거쳐야만 진정으로 변화할 수 있습니다. 그 신비를 이해하십시오.세 가지 JavaScript 시뮬레이션 구현 캡슐화 방법과 해당 작성 방법의 차이점 공유
JavaScript 자체 실행 함수 및 jQuery 확장 메서드에 대한 자세한 설명
JavaScript의 Require call js 예제 설명
위 내용은 자바스크립트 알고리즘 이진 검색 트리의 샘플 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!