前言
集合是高层的数据结构，高层的数据结构还有栈和队列，这种数据结构更像是定义好了这种数据结构的相应的使用接口。
有了这些使用的接口包括这些数据结构本身所维持的一些性质，就可以非常容易的把它们放入一些具体的应用中，但是底层实现可以是多种多样的。
比如栈和队列的底层实现即可以是动态数组也可以是链表，集合 Set 也是类似这样的数据结构。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
集合的应用
典型的应用：用于客户的统计。
如你做一个网站，对访问的 ip 进行一个统计，不仅要关注总访问量，还要关注有多少不同的 ip 访问，或者今天跟昨天相比又有多少个新的 ip 来访问，在这种时候就应该使用集合这种数据结构来做统计。
典型的应用：词汇量的统计。
在进行英文阅读的时候你会去参考，这本书的词汇量究竟有多少，对于一本书的词汇量来说，相同的单词是只记一次的，在这种时候就应该使用集合这种数据结构来做统计。
接下来就基于之前实现的二分搜索树以及链表来进行集合的实现。
基于二分搜索树的实现集合
集合就是承载元素的一个容器，在集合中有一个非常重要的特点，也就是每个元素只能存在一次。在具体应用的时候需要这样的数据结构，它能够帮助你非常快速的进行去重这个工作，去重指的是去除所有重复的元素，让所有的元素只保留一份。例如你想统计一个饭馆有多少位会员，这时候你就需要进行一个去重的操作，会员不能够重复，无论是新客户还是老客户都只能手持一张会员卡。
在二分搜索树的添加操作的时候，最开始实现的时候是不能盛放重复元素的，所以这个二分搜索树本身就是一个非常好的实现“集合”的底层数据结构。
集合接口
MySet
void add (e) : 不能添加重复元素 void remove (e) boolean conatains (e) int getSize () boolean isEmpty ()
使用 MyBSTSet 来实现这个集合的接口
代码示例
(class: MyBinarySearchTree, class: MyBSTSet, class: Main)
MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 找到二分搜索树中的最大值的元素 +
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// 找到二分搜索树中的最大值的元素的节点 递归算法 -
recursiveMaximum(node) {
// 解决最基本的问题 向右走再也走不动了，说明当前节点就是最大值节点。
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMax(node) {
if (node.right === null) {
// 先存 当前这个节点的左子树，
// 因为可能当前这个节点仅仅没有右子树，只有左子树，
// 那么左子树可以替代当前这个节点。
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// 找到二分搜索树中的最小值 +
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// 找到二分搜索树中的最小值的元素的节点 递归算法 -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMin(node) {
// 解决最简单的问题
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 将复杂的问题拆分为性质相同的小问题，
// 然后求出这些小问题的解后构建出原问题的答案
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// 删除二分搜索树上的任意节点
remove(element) {
this.root = this.recursiveRemove(this.root, element);
}
// 删除二分搜索树上的任意节点 递归算法
// 返回删除对应元素节点后新的二分搜索树的根
recursiveRemove(node, element) {
if (node === null) return null;
// 当前节点的元素值比待删除的元素小 那么就向当前节点的右子树中去找
if (this.compare(node.element, element) < 0) {
node.right = this.recursiveRemove(node.right, element);
return node;
} else if (this.compare(node.element, element) > 0) {
// 向当前节点的左子树中去找
node.left = this.recursiveRemove(node.left, element);
return node;
} else {
// 如果找到了相同值的节点了，开始进行相应的处理
// 如果这个节点左子树为空，那么就让这个节点的右子树覆盖当前节点
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 如果当前节点的右子树为空，那么就让这个节点的左子树覆盖当前节点
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// 如果当前节点的左右子树都不为空，那么就开始特殊操作
// 1. 先找到当前节点右子树上最小的那个节点，保存起来
// 2. 然后删除掉当前节点右子树上最小的那个节点，
// 3. 让保存起来的那个节点覆盖掉当前节点
// 1. 也就是保存起来的那个节点的right = 删除掉当前节点右子树上最小的节点后返回的那个节点
// 2. 再让保存起来的那个节点的left = 当前节点的left
// 4. 解除当前节点及其left和right，全都赋值为null，这样就相当于把当前节点从二分搜索树中剔除了
// 5. 返回保存的这个节点
let successtor = this.recursiveMinimum(node.right);
successtor.right = this.recursiveRemoveMin(node.right);
// 恢复removeMin 操作的this.size -- 带来的影响
this.size++;
successtor.left = node.left;
// 开始正式的删除当前节点的操作
node = node.left = node.right = null;
this.size--;
// 返回当前保存的节点
return successtor;
}
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 层序遍历
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while (!queue.isEmpty()) {
node = queue.dequeue();
operator(node.element);
console.log(node.element);
// 队列 是先进先出的，所以从左往右入队
// 栈 是后进先出的， 所以从右往左入栈
if (node.left !== null) queue.enqueue(node.left);
if (node.right !== null) queue.enqueue(node.right);
}
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}MyBSTSet
// 自定义二分搜索树集合Set
class MyBinarySearchTreeSet {
constructor() {
// 借用二分搜索树来实现这个接口
this.myBinarySearchTree = new MyBinarySearchTree();
}
// 添加元素
add(element) {
this.myBinarySearchTree.add(element);
}
// 移除元素
remove(element) {
this.myBinarySearchTree.remove(element);
}
// 是否包含这个元素
contains(element) {
return this.myBinarySearchTree.contains(element);
}
// 遍历操作
// 第一个参数 是回掉函数，
// 第二个参数 是遍历的方式 深度优先遍历(前pre、中in、后post)，广度优先遍历(层序level)
each(operator, method) {
// 遍历方式默认是非递归的前序遍历，
// 其它的遍历方式就是递归的前、中、后、层序遍历。
switch (method) {
case 'pre':
this.myBinarySearchTree.preOrder(operator);
break;
case 'in':
this.myBinarySearchTree.inOrder(operator);
break;
case 'post':
this.myBinarySearchTree.postOrder(operator);
break;
case 'level':
this.myBinarySearchTree.levelOrder(operator);
break;
default:
this.myBinarySearchTree.nonRecursivePreOrder(operator);
break;
}
}
// 获取集合中实际的元素个数
getSize() {
return this.myBinarySearchTree.getSize();
}
// 返回集合是否为空的bool值
isEmpty() {
return this.myBinarySearchTree.isEmpty();
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTreeSet Area');
{
let n = 5;
let set = new MyBinarySearchTreeSet();
let random = Math.random;
let temp = null;
for (var i = 0; i < n; i++) {
temp = random();
set.add(n * n * n * temp);
set.add(n * n * n * temp);
set.add(n * n * n * temp);
set.add(n * n * n * temp);
set.add(n * n * n * temp);
set.add(n * n * n * temp);
set.add(n * n * n * temp);
}
console.log(set.getSize());
this.show(set.getSize());
let array = new MyArray(n);
set.each(element => {
console.log(element);
this.show(element);
array.add(element);
});
for (var i = 0; i < array.getSize(); i++) {
set.remove(array.get(i));
}
console.log(set.getSize());
this.show(set.getSize());
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};集合-基于链表的实现
集合设计的是一个接口，所以可以采用不同的底层数据结构来进行实现它，和栈和队列一样，可以使用底层的数据结构动态数组和链表来实现它，那么也可以通过链表来实现集合。
二分搜索树和链表都属于动态数据结构，对于二分搜索树来说数据都是存储在一个一个 node 中，链表也是把数据存储到一个一个的 node 中。不过这两个 node 的定义是不同的，对于二分搜索树来说有左右两个指针来指向左子树和右子树，而对于链表来说每一个 node 都指向了下一个 node。
由于它们同样是动态数据结构，所以可以基于这两种数据结构为底层实现这个集合，还可以相应的进行比较这两种数据结构实现后的性能，通过它们的性能比较可以看出二分搜索树这种数据结构的优势所在。
// 二分搜索树的Node
class Node {
e; // Element
left; // Node
right; // Node
}
// 链表的Node
class Node {
e; // Element
next; // Node
}集合接口
MySet
void add (e) : 不能添加重复元素 void remove (e) boolean conatains (e) int getSize () boolean isEmpty ()
使用 MyLinkedListSet 来实现这个集合的接口
代码示例
( class: MyLinkedList, class: MyLinkedListSet)
MyLinkedList
// 自定义链表节点
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// 将一个数组对象 转换为一个链表 并且追加到当前节点上
appendToLinkedListNode(array) {
let head = null;
if (this.element === null) {
// 头部添加
head = this;
head.element = array[0];
head.next = null;
} else {
// 插入式
head = new MyLinkedListNode(array[0], null);
head.next = this.next;
this.next = head;
}
// 添加节点的方式 头部添加、尾部添加、中间插入
// 尾部添加节点的方式
for (var i = 1; i < array.length; i++) {
head.next = new MyLinkedListNode(array[i], null);
head = head.next;
}
}
//@override
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
// 自定义链表
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 删除指定索引位置的节点
remove(index) {
// 验证索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待删除的节点
let delNode = node.next;
// 给待删除那个节点的前一个的节点的next引用替换为
// 但删除的这个节点的next
node.next = delNode.next;
// 或者这样也行
// node.next = node.next.next;
// 临时存储待删除的那个节点里的元素
let element = delNode.element;
// 清空 待删除的节点
delNode = null;
this.size--;
return element;
}
// 扩展：移除链表头的元素
removeFirst() {
return this.remove(0);
}
// 扩展：移除链表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListSet
// 自定义链表集合Set
class MyLinkedListSet {
//
constructor() {
this.myLinkedList = new MyLinkedList();
}
add(element) {
if (!this.myLinkedList.contains(element))
this.myLinkedList.addFirst(element);
}
remove(element) {
this.myLinkedList.removeElement(element);
}
contains(element) {
return this.myLinkedList.contains(element);
}
each(operator) {
let size = this.myLinkedList.getSize();
for (var i = 0; i < size; i++) {
operator(this.myLinkedList.get(i));
}
}
getSize() {
return this.myLinkedList.getSize();
}
isEmpty() {
return this.myLinkedList.isEmpty();
}
}集合类的复杂度分析
实现了两个基于动态数据结构的集合类，分别是基于二分搜索树的集合类 MyBSTSet和基于链表的集合类 MyLinkedListSet，基于链表的集合类性能要差一些。
对集合的时间复杂度分析，分别是增加 add、查询 contains、删除 remove
MyLinkedListSet 与 MyBSTSet 时间复杂度对比
MyLinkedListSet 的时间复杂度为O(n)，MyBSTSet 的时间复杂度为O(h) or O(log n)，h = log2 (n+1) = O(log2 n)，h 和 n 之间成一个 log 关系，log 以 2 为底的(n+1)。
通常称它们之间的关系为O(log2 n)也就是大 O log 以 2 为底 n 这样的一个关系，在大 O 这样的一个定义下，这个底的大小可以忽略不计，因为认为常数不重要，以 2 为底、以 10 为底、以 100 为底，它都是一个 log 级别的函数。
就像看线性关系，前面的系数也是不关注的，它是1*n、2*n、100*n、10000*n，它们都是线性的一个关系，所以这个关系可以写成O(log n)。
二分搜索树的局限性
虽然二分搜索树实现的集合时间复杂度为O(log n)，但是计算出这个时间复杂度是在满二叉树的情况下，所以这个O(log n)其实是一个最优的情况，如果二叉树稍微有一些倾斜，也能达到O(log n)这个级别。但是自己实现的二分搜索树有一个致命的问题，它有最坏的情况，对于同样的数据，可以创建出不同的二分搜索树。
例如每一个节点的左孩子都为空只有右孩子，在这种情况下二分搜索树和一个链表是一样的，也就是说这棵二分搜索树的高度等于节点数，这就是二分搜索树最坏的情况，例如按照顺序添加[1,2,3,4,5,6]，就可以创建出一颗退化成链表的二分搜索树。
在大多数实际情况下 MyBSTSet 不会那么奇怪的按照顺序添加数据，因为那样会让二分搜索树退化成链表，但是也有可能你的二分搜索树就会遇到最差的情况或者接近最差的情况，那么此时你二分搜索树的性能近乎接近链表的性能，这样的性能其实也是O(n)这样的性能，这也是你之前实现的二分搜索树的局限性。
但是平均来讲，大多数情况下它都能达到O(log n)的时间复杂度，但是依然会有特殊情况，最差的情况他会退化成和链表一样的O(n)，所以就需要解决这个问题，解决这个问题的方式就是创建所谓的平衡二叉树。
所以非常准确的说二分搜索树的时间复杂度为O(h)，在大多数情况下这个 h 等于log n，如果非常的不巧，那么这个 h 等于 n。
log n 和 n 的差距
当n=16的时候，logn 让它取 2 为底，相应的log2 n的值为 4，n 的值就是 16。也就是说它们相差四倍，随着 n 的增大，它们之间的差距就会越来越大。
比如说n=1024的时候，logn 还是让它取 2 为底，因为 2 的十次方为 1024，那么相应的log2 n的值为 10，n 的值就是 1024，在这种情况下，二者之间相差一百倍。如果n=100万这个级别的数据的话，logn 还是让它取 2 为底，因为 2 的 20 次方大概就是 100 万，那么相应的log2 n的值为 20，n 的值就是 100 万，在这种情况下，二者之间相差 5 万倍。
它们之间的差距非常非常大。 比如你使用O(log n)这个算法和O(n)这个算法，输入的数据为 100 万个，如果你O(log n)这个算法花一秒时间就跑完的话，那么O(n)这个算法就需要花 5 万秒，大概 14 个小时。
再比如你O(log n)这个算法要花一天的时间跑完这个程序，那么O(n)这个算法就需要花 5 万天，大概 137 年的事件才能跑出结果。这概念就像你睡一觉 24 小时后O(log n)算法的程序就跑出结果了，而O(n)算法的程序你这一辈子都跑不出结果来。
log n 这个复杂度是非常快非常快的一个时间复杂度，很多高级的排序算法最终它是 nlogn 这个时间复杂度，这个时间复杂度比 n 方的时间复杂度快了非常多倍，快的倍数与O(log n)和O(n)差不多，虽然它们之间还有常数的差异，但是在复杂度分析的时不去管这个常数的差异。
MyLinkedListSet
增加 add O(n)： 为了防止元素重复，所以必须先查询一遍，然后再决定添加不添加，虽然添加的复杂度为O(1)，但是查询的操作是遍历整个链表，所以整体时间复杂度为O(n)。
查询 contains O(n)：查询的操作是遍历整个链表，所以时间复杂度为O(n)
删除 remove O(n)：删操作也需要遍历整个链表，所以时间复杂度为O(n)
MyBSTSet
增加 add O(h) or O(log n)：添加一个元素，待添加的这个元素和根节点的这个元素进行比较，如果小于的话直接去左子树，如果大于的话直接去右子树，每一次近乎都能把一半儿的元素给扔掉。
添加这个元素这个过程其实就像是在走一个链表，一层一层的从这个树的根节点向叶子节点出发，最终一共经历的节点个数就是这棵树的高度，也就是整棵树最大的深度。
查询元素也是如此，删除元素还是如此，所以对于二分搜索树来说，这三个时间复杂度都是O(h)这个级别的，这个 h 就是二分搜索树的高度。
查询 contains O(h) or O(log n)
删除 remove O(h) or O(log n)
二分搜索树
满的二叉树每一层有多少个节点
第 0 层：1 个节点
第 1 层：2 个节点
第 2 层：4 个节点
第 3 层：8 个节点
第 4 层：16 个节点
第 h-1 层：2^(h-1)个节点
满的二叉树一共有多少个节点？
可以通过等比数列来进行计算，2^(1-1) + 2^(2-1) + ... + 2^(h-1)`= 1 x (1-2^(h)) / (1-2) = 2^(h) - 1 = n`。
满的二叉树的高度与节点个数之间的关系
h = log2 (n+1) = O(log2 n)，h 和 n 之间成一个 log 关系，log 以 2 为底的(n+1)，通常称它们之间的关系为O(log2 n)，也就是大 O log 以 2 为底 n 这样的一个关系，在大 O 这样的一个定义下，这个底的大小可以忽略不计。
因为认为常数不重要，以 2 为底、以 10 为底、以 100 为底，它都是一个 log 级别的函数，就像看线性关系，前面的系数也是不关注的，它是1*n、2*n、100*n、10000*n，它们都是线性的一个关系，所以这个关系可以写成O(log n)。
二分搜索树这种底层的数据结构实现的集合，它性能是大大的快于链表实现的集合。
代码示例
(class: MyLinkedList, class: MyBinarySearchTree, class: PerformanceTest, class: MyLinkedListSet, class:MyBSTSet , class: Main)
MyLinkedList
// 自定义链表节点
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// 将一个数组对象 转换为一个链表 并且追加到当前节点上
appendToLinkedListNode(array) {
let head = null;
if (this.element === null) {
// 头部添加
head = this;
head.element = array[0];
head.next = null;
} else {
// 插入式
head = new MyLinkedListNode(array[0], null);
head.next = this.next;
this.next = head;
}
// 添加节点的方式 头部添加、尾部添加、中间插入
// 尾部添加节点的方式
for (var i = 1; i < array.length; i++) {
head.next = new MyLinkedListNode(array[i], null);
head = head.next;
}
}
//@override
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
// 自定义链表
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 获取链表中实际的节点个数
getSize() {
return this.size;
}
// 判断链表是否为空
isEmpty() {
return this.size === 0;
}
// 在链表头添加节点
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虚拟头节点
this.insert(0, element);
}
// 在链表指定索引处插入节点
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一个prev就是dummyHead
let prev = this.dummyHead;
// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，
// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点
// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），
// 小于index是因为要找到指定索引位置的前一个节点
// 循环是因为 要继续找到指定索引处的节点的前一个节点
for (var i = 0; i < index; i++) {
// 不停的切换引用，直到找到对应索引处节点的下一个节点
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 扩展：在链表最后一个节点的位置添加节点
addLast(element) {
this.insert(this.size, element);
}
// 获取指定索引位置的元素
get(index) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引节点的前一个节点 就使用dummyHead
// 如果你要找到指定索引节点 就使用dummyHead.next
// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，
// dummyHead.next才是真正被记录的第一个节点。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 获取头节点的元素
getFirst() {
return this.get(0);
}
// 获取尾节点的元素
getLast() {
return this.get(this.size - 1);
}
// 设置指定索引位置的元素值
set(index, element) {
// 判断索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 从第一个真正被记录的节点开始，从0开始
let node = this.dummyHead.next;
// 索引为 0 时，实际上切换到的节点 它的索引为 1
// i < index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index
for (let i = 0; i < index; i++) {
// 每一次切换 都只是改变引用
// 不的在链表中找下一个节点
node = node.next;
}
node.element = element;
}
// 所有节点中是否有包含该元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切换
node = node.next;
}
return false;
}
// 删除指定索引位置的节点
remove(index) {
// 验证索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待删除的节点
let delNode = node.next;
// 给待删除那个节点的前一个的节点的next引用替换为
// 但删除的这个节点的next
node.next = delNode.next;
// 或者这样也行
// node.next = node.next.next;
// 临时存储待删除的那个节点里的元素
let element = delNode.element;
// 清空 待删除的节点
delNode = null;
this.size--;
return element;
}
// 扩展：移除链表头的元素
removeFirst() {
return this.remove(0);
}
// 扩展：移除链表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 新增：根据元素来删除链表中的元素 2018-11-05
removeElement(element) {
let prev = this.dummyHead;
while (prev.next !== null) {
if (prev.next.element === element) break;
prev = prev.next;
}
if (prev.next !== null) {
let delNode = prev.next;
prev.next = delNode.next;
delNode = null;
this.size--;
}
}
// 输出链表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 找到二分搜索树中的最大值的元素 +
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// 找到二分搜索树中的最大值的元素的节点 递归算法 -
recursiveMaximum(node) {
// 解决最基本的问题 向右走再也走不动了，说明当前节点就是最大值节点。
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMax(node) {
if (node.right === null) {
// 先存 当前这个节点的左子树，
// 因为可能当前这个节点仅仅没有右子树，只有左子树，
// 那么左子树可以替代当前这个节点。
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// 找到二分搜索树中的最小值 +
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// 找到二分搜索树中的最小值的元素的节点 递归算法 -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMin(node) {
// 解决最简单的问题
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 将复杂的问题拆分为性质相同的小问题，
// 然后求出这些小问题的解后构建出原问题的答案
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// 删除二分搜索树上的任意节点
remove(element) {
this.root = this.recursiveRemove(this.root, element);
}
// 删除二分搜索树上的任意节点 递归算法
// 返回删除对应元素节点后新的二分搜索树的根
recursiveRemove(node, element) {
if (node === null) return null;
// 当前节点的元素值比待删除的元素小 那么就向当前节点的右子树中去找
if (this.compare(node.element, element) < 0) {
node.right = this.recursiveRemove(node.right, element);
return node;
} else if (this.compare(node.element, element) > 0) {
// 向当前节点的左子树中去找
node.left = this.recursiveRemove(node.left, element);
return node;
} else {
// 如果找到了相同值的节点了，开始进行相应的处理
// 如果这个节点左子树为空，那么就让这个节点的右子树覆盖当前节点
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 如果当前节点的右子树为空，那么就让这个节点的左子树覆盖当前节点
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// 如果当前节点的左右子树都不为空，那么就开始特殊操作
// 1. 先找到当前节点右子树上最小的那个节点，保存起来
// 2. 然后删除掉当前节点右子树上最小的那个节点，
// 3. 让保存起来的那个节点覆盖掉当前节点
// 1. 也就是保存起来的那个节点的right = 删除掉当前节点右子树上最小的节点后返回的那个节点
// 2. 再让保存起来的那个节点的left = 当前节点的left
// 4. 解除当前节点及其left和right，全都赋值为null，这样就相当于把当前节点从二分搜索树中剔除了
// 5. 返回保存的这个节点
let successtor = this.recursiveMinimum(node.right);
successtor.right = this.recursiveRemoveMin(node.right);
// 恢复removeMin 操作的this.size -- 带来的影响
this.size++;
successtor.left = node.left;
// 开始正式的删除当前节点的操作
node = node.left = node.right = null;
this.size--;
// 返回当前保存的节点
return successtor;
}
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 层序遍历
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while (!queue.isEmpty()) {
node = queue.dequeue();
operator(node.element);
console.log(node.element);
// 队列 是先进先出的，所以从左往右入队
// 栈 是后进先出的， 所以从右往左入栈
if (node.left !== null) queue.enqueue(node.left);
if (node.right !== null) queue.enqueue(node.right);
}
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}PerformanceTest
// 性能测试
class PerformanceTest {
constructor() {}
// 对比都列
testQueue(queue, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
queue.enqueue(random() * openCount);
}
while (!queue.isEmpty()) {
queue.dequeue();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比栈
testStack(stack, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
stack.push(random() * openCount);
}
while (!stack.isEmpty()) {
stack.pop();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 对比集合
testSet(set, openCount) {
let startTime = Date.now();
let random = Math.random;
let arr = [];
let temp = null;
// 第一遍测试
for (var i = 0; i < openCount; i++) {
temp = random();
// 添加重复元素，从而测试集合去重的能力
set.add(temp * openCount);
set.add(temp * openCount);
arr.push(temp * openCount);
}
for (var i = 0; i < openCount; i++) {
set.remove(arr[i]);
}
// 第二遍测试
for (var i = 0; i < openCount; i++) {
set.add(arr[i]);
set.add(arr[i]);
}
while (!set.isEmpty()) {
set.remove(arr[set.getSize() - 1]);
}
let endTime = Date.now();
// 求出两次测试的平均时间
let avgTime = Math.ceil((endTime - startTime) / 2);
return this.calcTime(avgTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime(result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor((result / (60 * 60 * 1000)) % 24);
//获取距离的分钟数
var minutes = Math.floor((result / (60 * 1000)) % 60);
//获取距离的秒数
var seconds = Math.floor((result / 1000) % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? '0' + day : day;
hours = hours < 10 ? '0' + hours : hours;
minutes = minutes < 10 ? '0' + minutes : minutes;
seconds = seconds < 10 ? '0' + seconds : seconds;
milliSeconds =
milliSeconds < 100
? milliSeconds < 10
? '00' + milliSeconds
: '0' + milliSeconds
: milliSeconds;
// 输出耗时字符串
result =
day +
'天' +
hours +
'小时' +
minutes +
'分' +
seconds +
'秒' +
milliSeconds +
'毫秒' +
' <<<<============>>>> 总毫秒数：' +
result;
return result;
}
}MyLinkedListSet
// 自定义链表集合Set
class MyLinkedListSet {
//
constructor() {
this.myLinkedList = new MyLinkedList();
}
add(element) {
if (!this.myLinkedList.contains(element))
this.myLinkedList.addFirst(element);
}
remove(element) {
this.myLinkedList.removeElement(element);
}
contains(element) {
return this.myLinkedList.contains(element);
}
each(operator) {
let size = this.myLinkedList.getSize();
for (var i = 0; i < size; i++) {
operator(this.myLinkedList.get(i));
}
}
getSize() {
return this.myLinkedList.getSize();
}
isEmpty() {
return this.myLinkedList.isEmpty();
}
}MyBSTSet
// 自定义二分搜索树集合Set
class MyBinarySearchTreeSet {
constructor() {
// 借用二分搜索树来实现这个接口
this.myBinarySearchTree = new MyBinarySearchTree();
}
// 添加元素
add(element) {
this.myBinarySearchTree.add(element);
}
// 移除元素
remove(element) {
this.myBinarySearchTree.remove(element);
}
// 是否包含这个元素
contains(element) {
return this.myBinarySearchTree.contains(element);
}
// 遍历操作
// 第一个参数 是回掉函数，
// 第二个参数 是遍历的方式 深度优先遍历(前pre、中in、后post)，广度优先遍历(层序level)
each(operator, method) {
// 遍历方式默认是非递归的前序遍历，
// 其它的遍历方式就是递归的前、中、后、层序遍历。
switch (method) {
case 'pre':
this.myBinarySearchTree.preOrder(operator);
break;
case 'in':
this.myBinarySearchTree.inOrder(operator);
break;
case 'post':
this.myBinarySearchTree.postOrder(operator);
break;
case 'level':
this.myBinarySearchTree.levelOrder(operator);
break;
default:
this.myBinarySearchTree.nonRecursivePreOrder(operator);
break;
}
}
// 获取集合中实际的元素个数
getSize() {
return this.myBinarySearchTree.getSize();
}
// 返回集合是否为空的bool值
isEmpty() {
return this.myBinarySearchTree.isEmpty();
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('Set Comparison Area');
let myLinkedListSet = new MyLinkedListSet();
let myBinarySearchTreeSet = new MyBinarySearchTreeSet();
let performanceTest = new PerformanceTest();
let myLinkedListSetInfo = performanceTest.testSet(
myLinkedListSet,
5000
);
let myBinarySearchTreeSetInfo = performanceTest.testSet(
myBinarySearchTreeSet,
5000
);
this.alterLine('MyLinkedListSet Area');
console.log(myLinkedListSetInfo);
this.show(myLinkedListSetInfo);
this.alterLine('MyBinarySearchTreeSet Area');
console.log(myBinarySearchTreeSetInfo);
this.show(myBinarySearchTreeSetInfo);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};总结
在计算机的世界中，集合是一种非常有用的一种数据结构，集合在生活中可以做客户统计、词汇量统计。在很多算法面试题来说，集合也是有很大的作用的。
虽然我们实现了自己专属集合，仅供学习数据结构中的算法思想。生产端还是要使用 内置的集合，内置的 Set 比自己实现的 MyBSTSet 要强大很多。因为 底层实现 Set 的树结构是一个平衡二叉树，更准确的说是基于红黑树来进行实现的，所以这个 Set 不会出现最差的时间复杂度O(n)的情况，在最差的情况下在 Set 中进行增删查也是O(logn)这种级别。并且这个 Set 还定义了更多的操作，这些操作都是和二分搜索树具有顺序性相关的操作。
拓展
leetcode 804.唯一摩尔斯密码词
网址：https://leetcode-cn.com/problems/unique-morse-code-words/
解答
// 答题
class Solution {
// leetcode 804. 唯一摩尔斯密码词
uniqueMorseRepresentations(words) {
/**
* @param {string[]} words
* @return {number}
* 使用自己的二分搜索树来实现
*/
var uniqueMorseRepresentations = function(words) {
// 摩斯码
const codes = [
'.-',
'-...',
'-.-.',
'-..',
'.',
'..-.',
'--.',
'....',
'..',
'.---',
'-.-',
'.-..',
'--',
'-.',
'---',
'.--.',
'--.-',
'.-.',
'...',
'-',
'..-',
'...-',
'.--',
'-..-',
'-.--',
'--..'
];
const myBinarySearchTreeSet = new MyBinarySearchTreeSet();
let content = '';
// 获取起始字符的aceii码，
// 从而可以求出某个单词的每一个字符在字母表中占的位置索引，
// 根据这些位置索引就可以在摩斯表中找到相应的摩斯码，
// 一个单词就是一组摩斯码，然后使用set添加，就可以直接实现去重的操作了
const start = 'a'.charCodeAt(0);
for (const word of words) {
for (const w of word) content += codes[w.charCodeAt(0) - start];
myBinarySearchTreeSet.add(content);
content = '';
}
return myBinarySearchTreeSet.getSize();
};
/**
* @param {string[]} words
* @return {number}
* 使用系统内置的Set集合类
*/
var uniqueMorseRepresentations = function(words) {
// 摩斯码
const codes = [
'.-',
'-...',
'-.-.',
'-..',
'.',
'..-.',
'--.',
'....',
'..',
'.---',
'-.-',
'.-..',
'--',
'-.',
'---',
'.--.',
'--.-',
'.-.',
'...',
'-',
'..-',
'...-',
'.--',
'-..-',
'-.--',
'--..'
];
const set = new Set();
let content = '';
// 获取起始字符的aceii码，
// 从而可以求出某个单词的每一个字符在字母表中占的位置索引，
// 根据这些位置索引就可以在摩斯表中找到相应的摩斯码，
// 一个单词就是一组摩斯码，然后使用set添加，就可以直接实现去重的操作了
const start = 'a'.charCodeAt(0);
for (const word of words) {
for (const w of word) content += codes[w.charCodeAt(0) - start];
set.add(content);
content = '';
}
return set.size;
};
return uniqueMorseRepresentations(words);
}
}
// main 函数
class Main {
constructor() {
this.alterLine('leetcode 804.唯一摩尔斯密码词');
let s = new Solution();
let words = ['gin', 'zen', 'gig', 'msg'];
this.show(s.uniqueMorseRepresentations(words));
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};有序集合和无序集合
之前实现的集合是基于二分搜索树实现的集合，还有 系统内置的基于红黑树实现的集合，它们本质都是有序的集合。
有序的集合是指元素在集合中是具有顺序性的。例如在二分搜索树中存储的元素，可以很轻易地从小到大遍历出来或者去看这个元素的是上或下一个元素是谁等等，这个准确的来说就是有序集合(OrderSet)。
无序的集合是指元素在集合中是没有顺序的。例如在链表中存储的元素，只是根据元素插入的顺序来决定这些元素在集合中的顺序，不能够轻易地从小到大来遍历在这个集合中所有的元素，也无法非常容易的去找到这个集合中最小最大的元素是谁、上或下一个元素谁等等这些操作。
通常有序的集合都是通过搜索树来实现的，无论是二分搜索树还是平衡二叉树它们都是搜索树，因为搜索树就有这样的优势，它可以实现有序的集合，对于有些问题集合的有序性是非常重要的。
在另一些问题中完全没有必要使用有序集合，比如仅仅是处理放重复元素的问题上，根本利用不到集合的有序性，完全可以使用无序的集合来解决这个问题。
对于无序的集合其实还是有更好的解决方案的，那就是基于哈希表的实现，对于哈希表来说，相应的增删查这样的操作其实比搜索树还要快。
其实对于搜索树的实现来说如果它保持了有序性，那么它的能力其实也会更大，这个能力就表现在很轻易的查询到最大最小元素，或者某一个元素的前一个元素和后一个元素等等。
当然轻易完成这些操作是有代价的，这个代价其实就在时间复杂性上，它是稍微差于哈希表的。
多重集合
对于集合来说在大多数情况下是不希望有重复元素的，但是在有些情况下也希望有集合可以容纳重复的元素，在这种情况下就称之为多重集合(MultipleSet)。
多重集合具体的实现也非常简单，只需要在允许重复的二分搜索树上进行包装一下一下即可。要清楚你所解决的问题是否需要使用多重集合，多重集合是根据业务场景所决定的，通常使用集合的大多数情况下还是选择不包含重复元素的集合。
