特点
- 左子树的节点 < 根节点 < 右子树节点
- 没有重复节点
查找
search(key, node = this.roots) {
if (node) {
if (key < node.key) {
return this.search(node.left, key);
} else if (key > node.key) {
return this.search(node.right, key);
} else {
return true;
}
} else {
return false;
}
}
插入和删除
插入很简单，就是在树的最底层寻找一个合适的位置。
insert(key) {
let newNode = {
key: key,
left: null,
right: null
};
if (!this.roots) {
this.roots = newNode;
} else {
this.insertNode(this.roots, newNode); // 从根节点开始
}
return this; // 链式操作
};
insertNode(node, newNode) {
if (newNode.key < node.key) {
if (!node.left) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else if(newNode.key > node.key){
if (!node.right) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}else{
return false; //不能有键值相等的节点
}
}
删除比较复杂，要根据子节点情况分三类进行操作： 1.如果没有子节点直接删除 2.如果有一个子节点那么将孩子提升到被删除元素的位置 3.如果有两个子节点则需要用被删除节点的右子树中最小节点替换，如下图所示：
remove(key, node = this.roots) {
if (node === null) {
return false;
}
if (key < node.key) {
node.left = this.remove(key, node.left);
return node;
} else if (key > node.key) {
node.right = this.remove(key, node.right);
return node;
} else {
//如果没有子节点直接删除
//如果有一个子节点那么将孩子提升到被删除元素的位置
if (node.left === null && node.right === null) {
node = null;
return node;
} else if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
} else {
//如果有两个子节点
console.log(node)
let aux = this.findMinNode(node.right); //在右子树中向左到尽头找到最小节点
node.key = aux.key;
node.right = this.remove(aux.key, node.right);
return node;
}
}
}
findMinNode(node) {
while (node && node.left) {
node = node.left;
}
return node;
}
复杂度
搜索、插入、删除的复杂度等于树高。
同样一棵二叉搜索树，全部由插入生成的和经过插入和删除的两棵树就不一样。树高的期望为 {O(log n)}，最坏 {O(n)}。
正因为这种随机性，特别是当插入有序的节点时，树就会退化成线性表，所以我们还会对二叉搜索树进行优化，让其拥有最好的最坏复杂度。你听说过的红黑树、AVL树就是解决这一问题而出现的，下篇文章我们会介绍。