JavaScript中的分类树(也称为树形结构或树数据结构)是一种非线性数据结构,它模拟了一种层次关系,就像一棵倒置的树,有一个根节点,每个节点可以有零个或多个子节点。
以下是一个简单的JavaScript实现二叉树的例子:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
inOrderTraverse(node = this.root, callback) {
if (node !== null) {
this.inOrderTraverse(node.left, callback);
callback(node.value);
this.inOrderTraverse(node.right, callback);
}
}
}
// 使用示例
const tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);
tree.inOrderTraverse((value) => console.log(value)); // 输出: 3 5 7 10 15
问题:树不平衡导致搜索效率低下。
原因:在二叉搜索树中,如果插入的数据是有序的,树会退化成一个链表,导致搜索、插入和删除操作的时间复杂度退化到O(n)。
解决方法:
示例代码(AVL树旋转):
class AVLNode extends TreeNode {
constructor(value) {
super(value);
this.height = 1;
}
}
class AVLTree extends BinaryTree {
// ...其他方法
getBalanceFactor(node) {
return node === null ? 0 : this.getHeight(node.left) - this.getHeight(node.right);
}
getHeight(node) {
return node === null ? 0 : node.height;
}
updateHeight(node) {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
rotateRight(y) {
let x = y.left;
let T2 = x.right;
x.right = y;
y.left = T2;
this.updateHeight(y);
this.updateHeight(x);
return x;
}
rotateLeft(x) {
let y = x.right;
let T2 = y.left;
y.left = x;
x.right = T2;
this.updateHeight(x);
this.updateHeight(y);
return y;
}
insertNode(node, newNode) {
// ...之前的插入逻辑
let balanceFactor = this.getBalanceFactor(node);
// Left Left Case
if (balanceFactor > 1 && newNode.value < node.left.value) {
return this.rotateRight(node);
}
// Right Right Case
if (balanceFactor < -1 && newNode.value > node.right.value) {
return this.rotateLeft(node);
}
// Left Right Case
if (balanceFactor > 1 && newNode.value > node.left.value) {
node.left = this.rotateLeft(node.left);
return this.rotateRight(node);
}
// Right Left Case
if (balanceFactor < -1 && newNode.value < node.right.value) {
node.right = this.rotateRight(node.right);
return this.rotateLeft(node);
}
return node;
}
}
以上代码展示了如何在JavaScript中实现一个基本的二叉搜索树,并通过AVL树的旋转操作来解决不平衡问题。
领取专属 10元无门槛券
手把手带您无忧上云