Appearance
二叉查找树
再看一种特殊的二叉树,二叉查找数。最大的特点是支持动态数据集合的快速插入、删除、查找操作。散列表也支持这些操作,而且散列表的这些操作更加高效,时间复杂度是 O(1)。既然有了高效的散列表,是不是可以用散列表替换来替换二叉树呢?有哪些地方散列表做不了,必须要用二叉树来做?
什么是二叉查找数
二叉查找树是二叉树中常见的一种类型,也叫二叉搜索树,是为了快速查找而产生的。
二叉查找树就是:在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都要大于这个节点的值。
二叉查找数的查找、插入和删除
二叉树支持快速的查找、插入和删除,看这 3 个操作时如何实现的。
查找
在二叉查找树中查找一个节点,先取根节点,如果等于要查找节点的值,那就返回;如果要查找节点的值小于根节点的值,那就在左子树中递归查找,如果要查找节点的值大于根节点的值,那就在右子树中递归。
插入
插入类似于查找,新插入的节点一般在叶子节点上。
在二叉树中插入节点,所以也是从根节点开始,依次比较要插入节点和节点的大小关系。如果要插入节点的值比节点的值大,并且节点的右子树为空,那就将节点要插入节点直接插入到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入的位置。同理,如果要插入节点的值比节点的值小,并且节点的左子树为空,就将节点要插入节点插入到左子节点的位置;如果不为空,那就再遍历左子树,查找插入位置。
删除
二叉树查找和插入都比较简单,但是它的删除复杂一些。针对删除节点的子节点个数不同,需要分 3 中情况来处理:
- 要删除的节点没有子节点:只需要将父节点中,指向要删除结点的指针值为 null。
- 要删除的节点只有一个子节点(只有左子节点或者右子节点):只需要更新父节点中指向要删除节点的指针,让它指向要删除节点的子节点就可以了。
- 要删除的节点有两个子节点:要找到这个节点的右子树中最小的节点,把它替换到要删除的节点上,然后删除掉这个最小节点。因为最小节点肯定没有左子节点(如果有左子节点,那就不是最小节点了),所以可以使用前面的两条规则来删除这个最小节点。
为什么要找右子树中最小的节点呢?
这个右子树中最小节点和要删除节点有着相同的特点,用它替换,才可以满足二叉查找数的定义。
其他操作
除了插入、删除、查找操作之外,二叉查找树还支持快速查找最大节点和最小节点、前驱节点和后继节点。还有一个重要的特性,中序遍历二叉查找树可以输出有序的数据序列,时间复杂度是 O(n),非常高效。因此,二叉查找树也叫二叉排序树。
支持重复数据的二叉查找树
前面的操作中,都是假设树中的节点存储的是数字。但是实际开发中,在二叉查找树中存储的是一个包含很多字段的对象,利用其中的某个字段作为键值(key)来构建二叉查找树。其它字段叫作卫星数据。
那如果存储的数据中,有两个对象的键值相同,那怎么处理?
这里有两种处理办法:
1. 把值相同的数据都存储在同一个节点上
每个节点不仅会存储一个数据,因此可以通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。
2. 存储在不同节点
插入的时候,如果碰到一个节点的值与要插入的数据值相同,就将这个要插入的数据放到这个节点的右子树中,也就是把新插入的数据当作大于这个节点的值来处理。
查找的时候,遇到值相同的节点,并不停止查找,而是继续在右子树中查找,直到遇到叶子节点才停止。这样就可以把键值等于要查找值的所有节点都找出来。
删除的时候,也需要先找到每个要删除的节点,然后再按照前面讲的删除操作的方法,依次删除。
js
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class binarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
let node = new Node(val);
if (this.root === null) {
this.root = node;
return;
}
let currentNode = this.root;
let parent;
while (true) {
parent = currentNode;
if (val < currentNode.value) {
currentNode = currentNode.left;
// 并且左子树为空
if (currentNode === null) {
parent.left = node;
break;
}
} else {
currentNode = currentNode.right;
// 并且右子树为空
if (currentNode === null) {
parent.right = node;
break;
}
}
}
}
find(val) {
let currentNode = this.root;
while (currentNode !== null) {
const { value } = currentNode;
if (value === val) {
return currentNode;
} else if (val < value) {
currentNode = currentNode.left
} else {
currentNode = currentNode.right;
}
}
return null;
}
delete(val) {
var p = this.root; // 指向要删除的节点,初始化指向根节点
var pp = null; // 记录 p 的父节点
while (p !== null && p.value !== val) {
pp = p;
if (val > p.value) p = p.right;
else p = p.left;
}
if (p === null) return; // 没有找到
// 要删除的节点有两个子节点
if (p.left !== null && p.right !== null) {
// 查找右子树中最小节点
var minP = p.right;
var minPP = p;
while (minP.left !== null) {
minPP = minP;
minP = minP.left;
}
// 将minP的数据替换到p中
p.value = minPP.value;
// 下面就变成了删除minP了
p = minP;
pp = minPP
}
// 删除的节点是叶子节点或者仅有一个子节点
var child; // p 的子节点
if (p.left !== null) child = p.left;
else if (p.right !== null) child = p.right;
else child = null;
if (pp === null) this.root = child; // 删除的是根节点,且根节点没有有两个子节点
else if (pp.left === p) pp.left = child;
else pp.right = child;
}
findMin() {
if (this.root === null) return null;
var currentNode = this.root;
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
return currentNode;
}
findMax() {
if (this.root === null) return null;
var currentNode = this.root;
while (currentNode.right !== null) {
currentNode = currentNode.right;
}
return currentNode;
}
preOder() {
function print(node) {
if (node !== null) {
console.log(node.value);
print(node.left);
print(node.right);
}
}
print(this.root);
}
inOrder() {
function print(node) {
if (node !== null) {
print(node.left);
console.log(node.value);
print(node.right);
}
}
print(this.root);
}
postOrder() {
function print(node) {
if (node !== null) {
print(node.left);
print(node.right);
console.log(node.value);
}
}
print(this.root);
}
// 非递归前序遍历
preOder1() {
if (this.root === null) return
var res = [];
var stack = [];
stack.push(this.root);
while (stack.length) {
let node = stack.pop();
res.push(node.value);
// 这里先放右边再放左边是因为取出来的顺序相反
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
return res;
}
// 非递归中序遍历
inOrder1() {
if (this.root === null) return;
var stack = [];
var res = [];
var node = this.root; // !!!
while (true) {
// 先把左边的全部放进栈中
while (node !== null) {
stack.push(node);
node = node.left;
}
if (stack.length === 0) break;
var temp = stack.pop();
res.push(temp.value);
// 处理右边
node = temp.right;
}
return res;
}
// 非递归后序遍历
postOrder1() {
if (this.root === null) return;
var res = [];
var stack = [];
stack.push(this.root);
while (stack.length) {
var node = stack.pop();
res.push(node.value);
if (node.left !== null) stack.push(node.left)
if (node.right !== null) stack.push(node.right)
}
return res.reverse();
}
// 按层遍历
levelOrder() {
if (this.root === null) return;
var res = [];
var arr = [];
arr.push(this.root);
while (arr.length) {
let node = arr.shift();
res.push(node.value);
if (node.left) arr.push(node.left);
if (node.right) arr.push(node.right);
}
return res;
}
}
function test() {
let searchTree = new binarySearchTree();
console.log('add: 4 1 2 5 ')
searchTree.insert(4)
searchTree.insert(1)
searchTree.insert(2)
searchTree.insert(5)
searchTree.preOder()
console.log(searchTree.preOder1())
searchTree.inOrder()
console.log(searchTree.inOrder1())
searchTree.postOrder()
console.log(searchTree.postOrder1())
console.log(searchTree.levelOrder())
}
test();
二叉树的时间复杂度分析
不同结构的二叉查找树,它们的查找、插入、删除操作的执行效率都是不一样的。
如图第一种,最糟糕的情况下二叉查找树已经退化为链表,此时查找的复杂度为 O(n);那么最好的情况复杂度又是呢?比如二叉查找树正好是完全二叉树(或者满二叉树)。
通过代码、图来看,插入、删除和查找,时间复杂度其实都是跟树的高度成正比,也就是 O(height)。所以问题就变成怎么求一棵包含 n 个节点的完全二叉树的高度?
树的高度等于树的层数减 1,为了方便计算,用层来求解:
对于完全二叉树,第一层有 1 个节点,第二层有 2 个节点,...,第 k 层有 2^(k-1) 个节点。
不过,完全二叉树的最后一层就不满足上面的规律了,那么它包含的节点个数在 1~2^(L-1) 之间(假设最大层数是 L)。
所有节点相加起来,得到总节点个数 n,它满足这一关系:
1 + 2 + 4 + ... + 2^(L-2) + 1 <= n <= 1 + 2 + 4 + ... + 2^(L-2) + 2^(L-1)
根据等比数列求和,得到:
2^(L-1) <= n <= 2^L-1
所以 L 的范围是:
log2(n + 1) <= L <= log2n + 1
即完全二叉树的层数小于等于 log2n + 1,高度小于等于 log2n。
显然,极度不平衡的二叉查找树,查找性能是不能满足要求的。需要构建一种不管怎么插入、删除数据都能保持任意节点的左右子树都比较平衡的二叉查找树——平衡二叉查找数,它的高度接近 logn,所以插入、删除和查找的时间复杂度都比较稳定,为 O(logn)。
总结
现在再看看开头的问题,有了散列表,为什么还要使用二叉查找树?
主要有这几方面的原因:
- 散列表的数据是无序的,要想输出有序的数据,需要先进行排列。而对于二叉查找树来说,通过中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列。
- 散列表扩容耗时比较多,而且遇到散列冲突时,性能不稳定。尽管二叉查找树的性能也不稳定,但是工程中,最常用的平衡二叉查找树性能非常稳定,时间复杂度稳定在 O(logn)。
- 笼统的说,尽管散列表的查找等操作都是常量级的,但是因为哈希冲突,这个常量不一定比 logn 小。所以实际的查找速度可能不一定比 O(logn) 快,加上哈希函数的耗时,也不一定比平衡二叉查找树效率高。
- 散列表的构造比二叉查找树要复杂,考虑的东西很多。比如散列函数设计、冲突解决、扩容、缩容等。而平衡二叉树查找树只考虑平衡性这一个问题,而且这个问题的方案比较成熟、固定。
- 散列表为了避免过多的散列冲突,散列表转载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间。
综合比较来说,平衡二叉查找数在某些方面的性能优于散列表。所以,这两者的存在并不冲突,实际开发,要根据需求来选择使用哪种。
树,二叉树、满二叉树、完全二叉树都是树的结构概念。
二叉查找树是一种特殊的二叉树,它对节点之间值的大小关系有要求。它要求任意一个节点,其左子树中的每个节点的值都小于这个节点的值,而右子树中每个节点的值都大于这个节点的值。支持快速的查找、插入、删除操作。
它的这些操作的时间复杂度和树的高度成正比。最坏情况下二叉树退化成链表,时间复杂度是 O(n);最坏情况下,二叉树为完全二叉树,时间复杂度为 O(logn)。
为了避免时间复杂度的退化,针对二叉查找数,需要设计一种更加复杂的树——平衡二叉查找数,时间复杂度可以稳定为 O(logn)。