关于Javascript数据结构（一）
前几天收拾我的桌面的时候，发现了我上次从图书馆借的JS数据结构，在学校的网办大厅一看，好家伙还有两个星期就要过期了，我要是不看那不是很亏？
以下是一些学习笔记和心得。
一、什么是数据结构
概括起来就是：是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素的集合。
一个好的数据结构可以为计算机进行数据处理的时候提高不少的性能和节省更多的空间。
一般常见的数据结构有像栈、队列、链表、集合等等。
二、栈
1. 什么是栈
栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端。称为栈顶，另一端叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。
这就有点像我们平时超市购物时买东西的货架那样，先进去的在最里面，后进去的在最外面，当别人从货架上那商品的时候，最先拿到的总是最后一个放上去的。
2. 创建栈
会实现以下的功能：
push(elements): 添加一个（或几个）新元素到栈顶pop(): 移除并返回栈顶的元素peek(): 返回栈顶的元素isEmpty(): 判断栈是否为空，是为true，否为falseclear(): 清除栈里所有元素size(): 返回栈的元素数量
(1) 基于数组的栈
我们将创建一个基于【数组】的栈。创建一个 stack-array.js
class Stack {
constructor(){
this.items = [ ]; // 存储栈元素的数组
}
push(...elems){
this.items.push(...elems); // 往数组中添加一个元素
return true;
}
pop(){
return this.items.pop(); // 从数组末尾删除一个元素并返回
}
peek(){
return this.items[ this.items.length-1 ]; // 返回数组最后一个元素
}
isEmpty(){
return this.items.length == 0; // 判断数组长度是否为零来判断栈是否为空
}
clear(){
this.items = []; // 将数组清空来达到清空栈的目的
return true;
}
size(){
return this.items.length; // 数组元素数量即栈的元素数量
}
}
复制代码(2) 基于对象的栈
数组查询元素是需要一个个按顺序来查找的，所以当数组的长度越来越长时，查找所需要的时间就会越来越长。另外，数组是元素的有序集合，为了保证元素的排列有序，他会占用更多的内存空间。
所以我们可以使用【对象】来进行存储元素同时保证他的有序性。
class Stack{
constructor(){
this.count = 0; // 存储栈的长度
this.items = {}; // 存储栈的元素的对象
}
push(...elems){
for(let elem of elems){
this.items[this.count] = elem; // 以当前栈的长度作为 key，保证以对象为底层的同时保证有序性
this.count ++;
}
return true;
}
pop(){
if(this.isEmpty()) return undefined; // 不同于数组，对象删除不存在的指针的元素时会返回 true，从而无法判断该元素是否存在过。
this.count--;
let result = this.items[ this.count ];
delete this.items[ this.count ]; // 删除元素
return result;
}
peek(){
return this.items[ this.count - 1 ]; // 返回最后一个插入对象的元素
}
isEmpty(){
return this.count == 0;
}
claer(){
this.items = {}; // 重置对象
this.count = 0;
}
size(){
return this.count;
}
}
复制代码二、队列与双端队列
队列是遵循 先进先出（FIFO，也称为先来先服务） 原则的一组 有序 的项。队列在尾部添加新元素，在顶部移除元素，新添加的元素必须是在队列末尾。
这就十分像我们日常生活中的排队了，每个人都是队列中的元素，排在最前面的处理好业务后可以最先离开。
1. 创建队列
enqueue(elements): 向队列尾部添加一个或多个新的元素dequeue(): 移除队列的第一项peek()返回队列中第一个元素isEmpty(): 判断队列是否为空，是返回true，否返回falsesize(): 返回队列包含的元素个数
class Queue{
constructor(){
this.count = 0; // 存储队列的长度
this.lowestCount = 0; // 存储队列的第一个元素的指针
this.items = {}; // 存储队列元素的对象
}
enqueue(...elems){ // 使用 扩展运算符
for(let elem of elems){
this.items[ this.count ] = elem;
this.count ++;
}
return true;
}
dequeue(){
if(this.isEmpty()) return undefined;
const result = this.items[ this.lowestCount ];
delete this.items[this.lowestCount];
this.lowestCount ++; // 删除第一个元素后将下标指向下一个
return result;
}
peek(){
if(this.isEmpty()) return undefined;
return this.items[ this.lowestCount ];
}
isEmpty(){
return this.size() === 0;
}
size(){
return this.count - this.lowestCount;
}
clear(){
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
}
复制代码2. 创建双端队列
双端队列是一种特殊的队列，允许我们同时从前端和后端添加和移除元素。
这就有点类似那羽毛球桶了，羽毛球就是元素，球桶的两边都可以放入和取出羽毛球
将要实现的方法：
addFront(elem): 在前端添加新元素addBack(elem): 在后端添加新元素removeFront(): 移除前端第一个元素并返回removeBack(): 移除后端一个元素并返回peekFront(): 返回前端第一个元素peekBack(): 返回后端第一个元素isEmpty(): 判断双端队列是否为空，是返回true，否返回falsesize(): 返回双端队列的元素数量clear(): 清除双端队列所有元素
class Deque{
constructor(){
this.items = {}; // 存储双端队列的元素
this.count = 0; // 存储队列元素的数量（队列末尾的元素下标 + 1）
this.lowestCount = 0; // 存储队列开头的元素下标
}
addBack(elem){
this.items[ this.count ] = elem;
this.count ++;
return true;
}
addFront(elem){
if(this.isEmpty()){ // 当队列为空时，从前和从后添加都是一样的
this.addBack(elem);
}else{ // 当存在元素时，前端下标 - 1 然后添加元素
this.lowestCount --;
this.items[ this.lowestCount ] = elem;
}
return true
}
removeFront(){
if(this.isEmpty()) return undefined;
const result = this.items[ this.lowestCount ];
delete this.items[this.lowestCount]
this.lowestCount ++;
return result;
}
removeBack(){
if(this.isEmpty()) return undefined;
this.count --;
const result = this.items[ this.count ];
delete this.items[ this.count ];
return result;
}
peekFront(){
if(this.isEmpty()) return undefined;
return this.items[ this.lowestCount ];
}
peekBack(){
if(this.isEmpty()) return undefined;
return this.items[ this.count - 1 ];
}
isEmpty(){
return this.size() === 0;
}
size(){
return this.count - this.lowestCount; // 通过数量 - 前端下标 获取队列数量
}
clear(){
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
}
复制代码三、链表
要存储多个元素，数组（或列表）可能是最常用的数据结构，每种语言都实现了数组结构，同时还提供了 [] 这种便利写法，但是这种数据结构还有缺点：大多数语言中数组的是大小是固定的，从数组的起点或中间插入或移除元素的成本很高。
链表 存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素有一个存储元素本身和一个指向下一个元素的引用（指针或链接）组成。好处在于添加或移除元素的时候不需要移动其他元素，然而当我们想访问链表中间的某个元素时，则需要从头开始遍历。
可以把 链表 想想成一辆火车，每节车厢就是一个元素，每个车厢末尾都标记这本车厢的下一个车厢的车牌号。
1. 创建链表
让我们开始创建链表。
// util.js ------ 默认用来比较元素是否相等的 比较函数
export default function defaultEquals(a, b){
return a === b;
}
复制代码// node.js ------ 用来存储每个元素的容器
export default class Node{
constructor(elem){
this.elem = elem; // 元素内容
this.next = undefined; // 元素指针，指向该元素的下一个元素
}
}
复制代码将会实现以下方法：
push(elem): 向尾部添加一个元素insert(elem, position): 向特定位置添加一个元素getElementAt( index ): 返回指定位置的元素remove(elem): 移除一个元素indexOf(elem): 返回该元素的索引，不存在该元素则返回 -1removeAt(position): 移除指定位置的一个元素isEmpty(): 判断链表是否为空，是返回true，否返回falsesize(): 返回链表包含的元素数量toString(): 返回表示整个链表的字符串
// linkedList.js
import defaultEquals from "./defaultEquals";
import Node from "./Node";
export default class LinkedList {
constructor(equals = defaultEquals){
this.count = 0; // 链表长度
this.head = undefined; // 链表头（根元素）
this.equalsFn = equals; // 元素比较方法（因为存的元素可能不是基础类型的，可以自定义比较方法）
}
getElementAt(index){
if(index >= this.size() || index < 0) return undefined;
let i = index > Math.floor(this.size() / 2) ? Math.floor(this.size()) / 2 : 0
let current = this.head;
while( current.next !== undefined && i < index ){
current = current.next;
i++;
}
return current;
}
push(elem){
let node = new Node(elem);
if(this.isEmpty()){ // 当链表中不存在元素时，则作为链表头（第一个元素）
this.head = node;
}else{
let current = this.head;
while(current.next !== undefined){ // 循环查找下一个元素，直到某个元素的下一个元素为 undefined
current = current.next;
}
current.next = node;
}
this.count ++;
return true;
}
insert(elem, position){
let newNode = new Node(elem);
if(position === 0){
newNode.next = this.head;
this.head = newNode;
this.count ++;
return true;
}else if(position < 0 || position > this.size()){
return false;
}else{
if(position === this.size()){
this.push(elem);
}else{
let current = this.getElementAt(position - 1);
let nextCurrent = current.next;
newNode.next = nextCurrent;
current.next = newNode;
}
this.count ++;
return true;
}
}
remove(elem){
if(this.isEmpty()) return undefined;
let current = this.head;
let i = 0;
while(current !== undefined){
if(this.equalsFn(current.elem, elem)){
let lastCurrent = this.getElementAt(i - 1);
lastCurrent.next = current.next;
this.count --;
return current
}
current = current.next;
i++;
}
return undefined;
}
removeAt(index){
if(this.isEmpty() || index < 0 || index > this.count){
return false;
}else{
if(index === 0){
let current = this.head;
this.head = this.head.next;
this.count --;
return current;
}
let current = this.getElementAt( index - 1 );
let nextCurrent = current.next;
current.next = nextCurrent.next;
this.count --;
return nextCurrent;
}
}
indexOf(elem){
if(this.isEmpty()) return -1;
let current = this.head;
let i = 0;
while(current !== undefined){
if(this.equalsFn(current.elem, elem)){
return i;
}
current = current.next;
i++;
}
return -1;
}
isEmpty(){
return this.head === undefined;
}
size(){
return this.count;
}
toString(){
if(this.isEmpty()) return "";
let str = `${this.head.elem}`;
let current = this.head.next;
while(current !== undefined){
str += ` ---> ${current.elem}`;
current = current.next;
}
return str;
}
}
复制代码实际运用：
const link1 = new LinkedList();
console.log(link1.isEmpty()); // true
link1.push("白金之星");
link1.push("世界");
link1.insert("黄金体验", 1);
link1.push("紫色隐者");
console.log(link1.getElementAt(2)); // Node("世界")
console.log(link1.indexOf("白金之星")); // 0
console.log(link1.size()); // 4
console.log(link1.remove("银色战车")); // undefined;
console.log(link1.remove("紫色隐者")); // Node("紫色隐者")
console.log(link1.removeAt(2)); // Node("世界");
link1.insert("银色战车", 0);
console.log(link1.size()); // 2
console.log(link1.isEmpty()); // false
console.log(link1.toString()); // 银色战车 ---> 白金之星 ---> 黄金体验
复制代码2. 双向链表
双向链表是一种特殊的链表，普通链表只有一个指针指向他的下一个元素，而 双向链表则有两个指针，分别指向他的上一个元素和下一个元素。
还是火车举例子，普通火车的每个车厢只标注了下一节车厢的车牌号，而双向链表就像高铁一样，两头都可以行驶，每节车厢都标注了上一节和下一节车厢的车牌号。
我们使用前面已经写好了的链表稍加改进，创建一个双向链表。
// DoubleNode.js
export default class DoubleNode extends Node{ // 创建用于双向链表的Node类
constructor(elem, next, prev){
super(elem, next); // 通过继承使 DoubleNode 可以使用 Node 的属性
this.prev = prev; // 添加 prev 属性作为上一个元素的指针
}
}
复制代码import LinkedList from "./LinkedList.js";
import DoubleNode from "./DoubleNode.js";
import defaultEquals from "./defaultEquals.js";
// DoublyLinkedList.js
class DoublyLinkedList extends LinkedList{
constructor(equals = defaultEquals){
super(equals);
this.tail = undefined;
}
push(elem){
const newNode = new DoubleNode(elem);
if(this.isEmpty()){
this.head = this.tail = newNode
}else{
const current = this.tail;
current.next = newNode;
newNode.prev = current;
this.tail = newNode;
}
this.count ++;
return true;
}
insert(elem, position){
const newNode = new DoubleNode(elem);
if(position < 0 || position > this.size()){
return false;
}else if(position === 0){
let current = this.head;
current.prev = newNode;
newNode.next = current;
this.head = newNode;
}else if(position === this.size()){
this.push(elem);
}else{
let current = this.getElementAt(position);
let prevCurrent = current.prev;
prevCurrent.next = newNode;
newNode.prev = prevCurrent;
current.prev = newNode;
newNode.next = current;
}
this.count ++;
return true;
}
remove(elem){
if(this.isEmpty()) return undefined;
let current = this.head;
let i = 0;
while(current !== undefined){
if(this.equalsFn(current.elem, elem)){
const lastCurrent = current.prev;
const nextCurrent = current.next;
if(nextCurrent !== undefined){
nextCurrent.prev = lastCurrent;
}
lastCurrent.next = current.next;
this.count --;
return current
}
current = current.next;
i++;
}
return undefined;
}
removeAt(position){
if(this.isEmpty()) return undefined;
if(position > this.size() || position < 0){
return undefined;
}else{
this.count --;
if(position === 0){
const current = this.head;
const nextCurrent = current.next;
current.prev = undefined;
return current;
}else if(position === this.size()){
const current = this.tail;
const prevCurrent = current.prev;
prevCurrent.next = undefined;
return current;
}else{
const current = this.getElementAt(position);
const prevCurrent = current.prev;
const nextCurrent = current.next;
prevCurrent.next = nextCurrent;
nextCurrent.prev = prevCurrent;
return current;
}
}
}
}
复制代码实际使用效果：
const link2 = new DoublyLinkedList();
console.log(link2.isEmpty()); // true
link2.push("泷泽萝拉哒");
link2.push("木大木大");
link2.insert("口头瓦鲁", 1);
link2.push("银类呀咩撸做");
console.log(link2.getElementAt(2).elem); // 木大木大
console.log(link2.indexOf("白金之星")); // -1
console.log(link2.size()); // 4
console.log(link2.remove("木大木大").elem); // 木大木大
console.log(link2.removeAt(2).elem); // 银类呀咩撸做
link2.insert("欧拉欧拉", 0);
console.log(link2.size()); // 3
console.log(link2.isEmpty()); // false
console.log(link2.toString()); // 欧拉欧拉 ---> 泷泽萝拉哒 ---> 口头瓦鲁
复制代码3. 循环链表
循环链表 也是一种特殊的链表，即最后一项元素的下一个指针不是指向 undefined，而是指向链表的第一个元素。
双相链表也有循环链表，称为 双向循环链表，即第一个元素的上一个指针指向最后一个元素，最后一个元素的指针指向第一个元素。
其实顾名思义，就是循环。绕了个圈又回到起点的那种感觉。
这里只用单向循环链表做演示（绝不是懒得打双向）：
// CircularLinkedList.js
class CircualrLinkedList extends LinkedList{ // 继承于单向链表
constructor(equalsFn = defaultEquals){
super(equalsFn);
}
push(elem){
const newNode = new Node(elem);
if(this.isEmpty()){
newNode.next = newNode;
this.head = newNode;
}else{
let current = this.head;
let index = 0;
while(index < this.size() - 1){
current = current.next;
index ++;
}
newNode.next = this.head;
current.next = newNode;
}
this.count ++;
return true;
}
remove(elem){
if(this.isEmpty()) return undefined;
let current = this.head;
let i = 0;
while(i < this.size() - 1){
if(this.equalsFn(current.elem, elem)){
let lastCurrent = this.getElementAt(i - 1);
lastCurrent.next = current.next;
this.count --;
return current
}
current = current.next;
i++;
}
return undefined;
}
indexOf(elem){
if(this.isEmpty()) return -1;
let current = this.head;
let i = 0;
while(i < this.size() - 1){
if(this.equalsFn(current.elem, elem)){
return i;
}
current = current.next;
i++;
}
return -1;
}
toString(){
if(this.isEmpty()) return "";
let str = `${this.head.elem}`;
let current = this.head.next;
let i = 0;
while(i < this.size() - 1){
str += ` ---> ${current.elem}`;
current = current.next;
i++;
}
return str;
}
}
复制代码其实没有什么需要修改的，只有需要使用到判断当前元素下一项是否为 undefined着个循环逻辑需要修改，因为循环链表的每个元素的下一项，不会为 undefined。
看看效果：
const link3 = new CircualrLinkedList();
console.log(link3.isEmpty()); // true
link3.push("泷泽萝拉哒");
link3.push("木大木大");
link3.insert("口头瓦鲁", 1);
link3.push("银类呀咩撸做");
console.log(link3.getElementAt(2).elem); // 木大木大
console.log(link3.indexOf("白金之星")); // -1
console.log(link3.size()); // 4
console.log(link3.remove("木大木大").elem); // 木大木大
console.log(link3.removeAt(2).elem); // 银类呀咩撸做
link3.insert("欧拉欧拉", 0);
console.log(link3.size()); // 3
console.log(link3.isEmpty()); // false
console.log(link3.toString()); // 欧拉欧拉 ---> 泷泽萝拉哒 ---> 口头瓦鲁
复制代码4. 有序链表
依旧是 顾名思义【手写狗头】，就是在链表中保持元素的有序性。所以我们不能如了用户随便添加的意愿，需要我们来操作当前元素添加到哪个位置。
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
}
function defaultCompare(a, b){ // 自定义排序方法
if(a === b) return 0;;
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList{
constructor(equalsFn = defaultEquals, compareFn = defaultCompare){
super(equalsFn);
this.compareFn = compareFn; // 添加排序方法
}
insert(elem){
if(this.isEmpty()){
return super.insert(elem, 0);
}else{
let index = this.getIndexNextSortedElement(elem);
return super.insert(elem, index);
}
}
getIndexNextSortedElement(elem){ // 用于判断该元素应该处于链表的哪个位置
let current = this.head;
let i = 0;
while(current && i < this.size()){
if(this.compareFn(elem, current.elem) === Compare.LESS_THAN){ // 设置为倒序，也可以通过修改为 Compare.BIGGER_THAN 变成升序
return i;
}
current = current.next;
i ++;
}
return i;
}
}
复制代码实际使用效果：
const link4 = new SortedLinkedList();
console.log(link4.isEmpty()); // true
link4.insert(2);
link4.insert(5);
link4.insert(3);
link4.insert(8);
link4.insert(1);
link4.insert(4);
console.log(link4.toString()); // 1 --- 2 --- 3 --- 4 --- 5 --- 8
复制代码四、集合
学过高中数学的应该都知道集合这个概念。集合就是一组无序且唯一（不重复）的项组成（可以理解成没有重复元素和没有顺序概念的数组），还有一种特殊的集合叫做空集，顾名思义就是空的集合。
在数学中集合用 大括号({}) 表示，例如：N = {0, 1, 2, 3, 4, 5, ...}，集合中有着 并集、交集、差集、子集等基本运算，我们也来一一模拟出来。
1. 创建集合
需要实现的方法有：
add(elem): 向集合添加一个元素delete(elem): 从集合中移除一个元素has(elem): 判断该元素是否在集合中，是则为true，否则为falseclaer(): 清除集合所有元素size(): 返回集合所包含所有元素数量values(): 返回一个包含集合所有元素的数组union(otherSet): 求当前集合与给定集合的并集并返回（不修改当前集合）intersection(otherSet): 求当前集合与给定集合的交集并返回（不修改当前集合）difference(otherSet): 求当前集合与给定集合的差集并返回（不修改当前集合）isSubsetOf(otherSet): 判断当前集合是否为给定集合的子集
// Set.js
class Set{
constructor(){
this.items = {}
}
has(elem){
return Object.prototype.hasOwnProperty.call(this.items, elem); // 使用 Object.prototype.hasOwnProperty 会更加合适，配合 call() 会更加安全
}
add(elem){
if(!this.has(elem)){ // 集合的唯一和无序主要依靠的就是 has() 和 add() 两个方法
this.items[elem] = elem;
return true;
}
return false;
}
delete(elem){
if(!this.has(elem)) return undefined;
let item = this.items[elem];
delete this.items[elem];
return item;
}
clear(){
this.items = {};
return true;
}
size(){
return Object.keys(this.items).length;
}
values(){
return Object.values(this.items);
}
union(otherSet){
if(!(otherSet instanceof Set)) return undefined;
const unionSet = new Set();
this.values().forEach(value => unionSet.add(value)); // 将两个集合的元素都遍历添加到新的集合中
otherSet.values().forEach(value => unionSet.add(value));
return unionSet;
}
intersection(otherSet){
if(!(otherSet instanceof Set)) return undefined;
let intersectionSet = new Set();
let startSet = this.values();
endSet = this.otherSet.values();
if(startSet.length >= endSet.length){ // 用小的集合遍历大的集合，可以节省资源
startSet = otherSet.values();
endSet = this.values();
}
startSet.forEach(value => {
if(endSet.includes(value)){ // 判断该元素是否在两个集合中都包含着
intersectionSet.add(value);
}
})
return intersectionSet;
}
difference(otherSet){
if(!(otherSet instanceof Set)) return undefined;
let differenceSet = new Set();
for(let item of this.items.values()){
if(!otherSet.has(item)){
differenceSet.add(item);
}
}
return differenceSet;
}
isSubsetOf(otherSet){
if(!(otherSet instanceof Set)) return false;
if(this.size() > otherSet.size()) return false;
for(let item of this.items.values()){
if(!otherSet.has(item)){
return false;
}
}
return true;
}
}
复制代码注意：集合之间进行运算时，注意好作用对象，例如：集合A和集合B的差值，求的是在集合A中集合B所不包含的元素
五、字典与散列表
1. 字典
字典与集合有些相同，又有些不同。
字典存储的项是一个个无序的 键值对，一个键（key）对应一个值（value）,键是不允许重复的，但是值可以。你可以联想到 JS中的 Object，包含的也是键值对。（集合可以看作是 [值, 值] 的方式存储，而字典是 [键, 值] 的方式）
字典也被称作 映射表、符号表或关联数组。
要实现的功能如下：
set(key, value): 向字典添加新元素，若key已存在，则进行覆盖操作remove(key): 在字典中移除对应key的数据值并返回hasKey(key): 判断字典中是否包含某个键值，是返回true，否返回falseget(key): 获取字典中指定键的值clear(): 清除字典的所有数据size(): 返回字典所包含的项的数量。isEmpty(): 判断字典是否为空，是返回true，否返回falsekeys(): 返回由该字典的所有key组成的数组values(): 返回由该字典的所有的value组成的数组keyValues(): 返货该字典所有的键值对forEach(callbackFn): 迭代字典中所有的键值对，callback由两个参数，key和value，该方法可以在回调函数返回false时中止。
function defaultToString(item){
if(item === null){
return "NULL";
}else if(item === undefined){
return "UNDEFINED";
}else if(typeof item === "string" || item instanceof String){
return `${item}`;
}
return item.toString();
}
class ValuePair{
constructor(key, value){
this.key = key;
this.value = value;
}
toString(){
return `[#${this.key}: ${this.value}]`;
}
}
class Dictionary{
constructor(toStrFn = defaultToString){
this.toStrFn = toStrFn;
this.table = {};
}
set(key, value){
if(key !== null && value !== null){
let pair = new ValuePair(key, value);
this.table[this.toStrFn(key)] = pair;
return true;
}
return false;
}
hasKey(key){
return Object.prototype.hasOwnProperty.call(this.table, this.toStrFn(key)); // 使用 Object.prototype.hasOwnProperty 会更加合适，配合 call() 会更加安全
}
get(key){
const current = this.table[this.toStrFn(key)]; // 也可以使用 this.has(key) 判断，但是会查询两次 this.table的值，效率没这个好
return current === null ? undefined : current.value;
}
remove(key){
if(this.hasKey(key)){
let current = this.get(key);
delete this.table[this.toStrFn(key)];
return current;
}
return undefined;
}
clear(){
this.table = {};
return true;
}
size(){
return Object.keys(this.table).length;
}
isEmpty(){
return this.size() === 0;
}
keys(){
return this.keyValues.map(item => item.key); // 使用 map 函数操作数组的每个元素
}
values(){
return this.keyValues.map(item => item.value);
}
keyValues(){
return Object.values(this.table);
}
forEach(callBackFn){
const valuePairs = this.keyValues();
for(let i=0;i<valuePairs.length;i++){
let current = valuePairs[i];
if(!callBackFn(current.key, current.value)){
return false;
}
}
return true;
}
toString(){
if(this.isEmpty()) return ``;
const valuePairs = this.keyValues();
let objString = `${valuePairs[0].toString()}`;
for(let i=1;i<valuePairs.length;i++){
objString += ` --- ${valuePairs[i].toString()}`;
}
return objString;
}
}
复制代码实际使用效果：
let key1 = {"空城承太郎": "白金之星"}; // 注意对象转为字符串时为: [object Object]
let key2 = [1, 2, 3]; // 注意该数组转为字符串为: 1,2,3
let key3 = undefined;
let key4 = null;
let key5 = 123;
let key6 = "Hello";
const dic1 = new Dictionary();
console.log(dic1.isEmpty()); // true
dic1.set(key1, "这是对象的key");
dic1.set(key2, "这是数组的key");
dic1.set(key3, "这是undefined的key");
dic1.set(key4, "这是null的key");
dic1.set(key5, "这是number的key");
dic1.set(key6, "这是string的key");
console.log(dic1.hasKey(key4)); // false: 因为判断 key 为 null 后被阻挡掉了
console.log(dic1.get(key5)); // 这是number的key
console.log(dic1.toString());
// [#123: 这是number的key] --- [#[object Object]: 这是对象的key] --- [#1,2,3: 这是数组的key] --- [#undefined: 这是undefined的key] --- [#Hello: 这是string的key]
dic1.forEach((key, value)=>{ // 循环输出每个value
console.log(value);
return true;
})
复制代码2. 散列表(哈希表)
看书的时候，我也没看懂啥是散列表，只看懂了个它也属于字典，后来在baidu的帮助下，我大致搞懂了这是个啥玩意：
首先我们要知道，什么是 散列函数：
散列函数：
顾名思义，它是一个函数。如果把它定义成hash(key)，其中key表示元素的键值，则hash(key)的值表示经过散列函数计算得到的散列值。
说白了就是为了得到一个散列映射，也就是我们要存在散列表中的 key。
得出结论：
- 散列表，又称哈希表（Hash Table、Hash Map），也是属于字典的一种实现方式。
- 通过给定的 键（key） 而再通过一个关于键值的函数，生成一个值作为表中的一个映射，加快了查找速度，其中这个关于键值的函数便是 散列函数， 生成的值叫做 散列值，而通过散列值做映射存放数据的表就叫做 散列表。
- 常用的散列函数有像：
md5、SHA1、SHA256、loselose(学习)等。 - 假定我们的散列函数名为
hash(key)，散列函数有以下特征：- 确定性：如果两个散列值不相同，则两个散列值的原始值也不相同，即如果：
hash(key1) != hash(key2)则key1 != key2 - 不确定性：即使两个散列值相同，但两散列值的原始值可能相同也可能不相同，即如果：
hash(key1) == hash(key2)，但也不一定保证key1 == key2，这被称为 散列碰撞或哈希碰撞（hash collision） - 不可逆性：通过上条得知，即使我们知道了散列的值，也无法得知他的原始值是啥
- 确定性：如果两个散列值不相同，则两个散列值的原始值也不相同，即如果：
- 具体流程：
创建一个散列表trytry：
要实现以下功能：
put(key, value): 向散列表内添加一个新的项（重复的话则更新散列表）remove(key): 删除散列表中指定键的值get(key): 根据键返回特定的值
class HashTable{
constructor(toStrFn = defaultToString){
this.toStrFn = toStrFn;
this.table = {};
}
loseloseHashCode(key){ // 使用传统的 lose lose散列函数进行计算
if(typeof key === "number") return key;
const tableKey = this.toStrFn(key);
let hash = 0;
for(let i=0;i<tableKey.length; i++){
hash += tableKey.charCodeAt(i); // 就是获取字符串的每个字符的 ASCII码相加
}
return hash % 37; // 除以 37 是为了尽量让散列值不相同（聊胜于无）
}
hashCode(key){
return this.loseloseHashCode(key);
}
put(key, value){
if(key !== null && value !== null){
this.table[this.hashCode(key)] = new ValuePair(key, value);
return true;
}
return false;
}
remove(key){
if(key === null) return undefined;
let current = this.table[this.hashCode(key)];
delete this.table[this.hashCode(key)];
return current.value;
}
get(key){
const valuePair = this.table[this.hashCode(key)];
return valuePair === null ? undefined : valuePair.value;
}
}
复制代码看看实际使用效果：
const hash = new HashTable();
hash.put("John", "is a boy");
hash.put("Borry", "is a girl");
hash.put("Pat", "is a gay");
hash.put("Jonathan", "is so fat");
hash.put("Jamie", "is so thin");
console.log(hash.hashCode("John") + " - John"); // 29 - John
console.log(hash.hashCode("Borry") + " - Borry"); // 8 - Borry
console.log(hash.hashCode("Pat") + " - Pat"); // 34 - Pat
console.log(hash.hashCode("Jonathan") + " - Jonathan"); // 5 - Jonathan
console.log(hash.hashCode("Jamie") + " - Jamie"); // 5 - Jamie
console.log(hash.get("Jonathan")); // is so thin
复制代码你会发现，Jonathan 和 Jamie 的散列值是一样的，而这就导致了后面添加 Jamie 的值的时候不是添加新的值，而是在 Jonathan 的位置进行修改。
但我们自然也不能让这些数据丢失，所以我们需要寻找解决办法。
要不就是选择使用更优质的散列函数（但是无论多好的散列函数都总会有重复的，包括 md5 和 SHA1啥的，所以 不可取）。
或者是使用一些其他的技术手段操作。
- 双重散列方法
- 线性探索方法
- 链表法（最常用）
(1) 双重散列方法
这可不是用两个散列表来记录，而是用两个 散列函数来生成散列值。即如果说使用第一个散列函数生成的散列值有重复值的话，则使用第二个散列函数再生成一次散列值，直到不重复为止：
class HashTable{
djb2HashCode(key){ // 设置第二个散列函数
const tableKey = this.toStrFn(key); // 获取键值
let hash = 5381;
for(let i=0;i<tableKey.length;i++){
hash = (hash * 33) + tableKey.charCodeAt(i)；
}
return hash % 1013; // 选点奇葩冷门的数字尽量避免重复
}
put(key, value){
if(key !== null && value !== null){
let hashcode = this.hashCode(key);
if(Object.property.hasOwnProperty.call(this.table, hashcode)){ // 若出现了重复的散列值则使用第二个散列函数
hashcode = this.djb2HashCode(hashcode);
}
this.table[this.hashCode(key)] = new ValuePair(key, value);
return true;
}
return false;
}
}
复制代码不过即使使用了第二个散列函数，也会有可能出现重复的散列值，所以使用情况较少。
(2) 线性探索方法
线性探索的方法就是但表中存在相同散列值且对应的值不为空时，依旧选择插入值，不过是在当前位置上向上或向下查找空位插入。
例如：
class HashTable{
size(){ // 返回散列表的键值对数量
return Object.keys(this.table).length;
}
put(key, value){
if(key !== null && value !== null){
let position = this.hashCode(key);
let pair = this.table[position];
if(pair !== null && pair !== undefined){
let i = position + 1;
while(i < this.size() && this.table[i] !== undefined){
i ++;
}
this.table[i] = new ValuePairLazy(key, value);
}else{
this.table[this.hashCode(key)] = new ValuePair(key, value);
}
return true;
}
return false;
}
// 其他的 get 和 remove 方法请自行修改（手动狗头）
}
复制代码关于线性探索方法，还有很多种用法，比如 软删除、元素移动方向判断、二次探测方法等。篇幅问题我就不写了（绝不是因为懒）。
(3) 链表法（常用）
这个应该是比较常用的方法。是散列表和字典的结合。
散列表的每一个位置都是一个链表，当出现重复的散列值的时候，则在该位置的链表中新添加一个元素即可。
import LinkedList from "./LinkedList.js"; // 导入之前做的链表
class HashTable{
put(key, value){
if(key !== null && value !== null){
const position = this.hashCode(key);
if(this.table[position] == null || this.table[position] == undefined){
this.table[position] = new LinkedList();
}
const valuePair = new ValuePair(key, value);
this.table[position].push(valuePair);
return true;
}
return false;
}
// 其他的 get 和 remove 方法请自行修改（手动狗头）
}
复制代码有点类似抽屉，散列表中的每个值都是一个抽屉，而链表的每个元素则是该抽屉的每一个格子。
六、树
树开始生根发芽了，噩梦也开始降临了。 —— 莎士比亚
树在生活中并不少见，比如我们学习时常用的 思维导图，你的 家族谱，公司 人员结构等。（类似这样）
1. 相关术语
树的结构包含了多个节点，每个节点又有一个父节点和多个（或零个）子节点（如图每个圈都是个节点）
- 根节点: 树的顶部的节点称为 根节点，他没有父节点。
- 内部节点: 在树中至少有一个子节点的节点称为内部节点（如图：7, 15, 5, 9, 13, 20 都是内部节点）
- 外部节点 / 叶节点: 在书中没有子节点的节点称为外部节点或叶节点（如图：3, 6, 8, 10, 12, 14, 18, 23 都是外部节点）
- 子树: 在书中由一个节点和他的所有的后代节点构成一个子树（如图：节点 13和他的所有后代节点 12和14 构成了一个子树）
- 深度: 一个节点的深度取决于他的祖先节点的数量（如图：节点 3共有 5, 7, 11 三个祖先节点，所以他的深度为 3)
- 高度: 树的高度去接与所有节点的深度的最大值（如图最深的深度为 3，所以该树的高度为 3）
2. 树的类型
- 二叉搜索树，二叉排序树，二叉查找树
- AVL树（平衡二叉树）
- 红黑树
- B树（B-、B+）
- 字典树
- 后缀树
- 别看写得多，会用的没几个（狗头保命）
只讲其中几个（绝不是因为懒）
3. 二叉搜索树（BST）
二叉搜索树有几个特点：
- 每个节点最多只能由两个子节点，一个左侧子节点，一个右侧子节点
- 只允许左侧节点存储比父节点小的值，右侧节点存储比父节点大的值。
让我们试着做一下
class Node{
constructor(key){
this.key = key;
this.left = null;
this.right = null;
}
}
复制代码要实现的方法有：
insert(key): 往树中插入一个新的键search(key): 在树中查找一个键，节点存在返回true，若不存在则返回falseinOrderTraverse(): 通过中序遍历方式遍历所有节点preOrderTraverse(): 通过先序遍历方式遍历所有节点postOrderTraverse(): 通过后序遍历方式遍历所有节点min(): 返回树中最小的值/键max(): 返回树中最大的值/键remove(key): 从书中移除某个键
这里讲解一下什么是树的 中序，先序，后序遍历：
(1) 中序遍历
中序遍历是最简单的，你只需要想成从左到右扫描一遍树的每一个节点便是排序，或者最简单粗暴的就是： 从大到小排序。
如图：
(2) 先序遍历
先序遍历是优先于后代节点的顺序范文每个节点的。你可以想成一个小人绕着树的外轮廓跑，以他跑步的路径第一次遇到的节点进行排序就是先序遍历。如图：
(3) 后序遍历
后序遍历是先访问节点的后代节点，再访问节点本身。我们可以把他想象成剪葡萄，不过规定只能一次剪一颗。
就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。如图：
(4) 层序遍历
这个好理解，就是在每层中进行遍历。如图：
懒得画图了，找了些讲解树遍历的文章用了下图片
图片和思路出自 YuXi_0520的CSDN文章，举得例子举得贼好。
侵权通告一声立删
(5) 代码实现
class Node{ // 作为节点元素
constructor(key){
this.key = key;
this.left = null; // 存储左侧子节点
this.right = null; // 存储右侧子节点
}
}
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
}
function defaultCompare(a, b){ // 自定义排序方法
if(a === b) return 0;;
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn; // 用来比较节点值
this.root = null; // node类型的更根节点
}
// insert(key){ // 做法一：使用循环判断
// if(key !== null && key !== undefined){
// const newnode = new Node(key);
// if(this.root == null){
// this.root = newnode;
// }else{
// let current = this.root;
// while(true){
// if(this.compareFn(key, current.key) === Compare.LESS_THAN){
// if(current.left == null){
// current.left = newnode;
// break;
// }
// current = current.left;
// }else if(this.compareFn(key, current.key) === Compare.BIGGER_THAN){ // 对于树种出现重复数据的解决方法有两种，使用链表存储或作为大于处理，这里使用第二种
// if(current.right == null){
// current.right = newnode;
// break;
// }
// current = current.right;
// }
// }
// return true;
// }
// }
// return false;
// }
insert(key){ // 做法二：使用递归方法
if(key != null && key != undefined){
if(this.root == null){
this.root = new Node(key);
}else{
this.insertNode(this.root, key);
}
return true;
}
return false;
}
insertNode(node, key){
if(this.compareFn(key, node.key) === Compare.LESS_THAN){
if(node.left == null){
node.left = new Node(key);
}else{
this.insertNode(node.left, key);
}
}else{ // 对于树种出现重复数据的解决方法有两种，使用链表存储或作为大于处理，这里使用第二种
if(node.right == null){
node.right = new Node(key);
}else{
this.insertNode(node.right, key);
}
}
}
// search(key){ // 做法一：使用循环
// if(key !== null && key !== undefined){
// let current = this.root;
// while(true){
// if(this.compareFn(key, current.key) === 0) return true;
// if(this.compareFn(key, current.key) === Compare.LESS_THAN){
// if(current.left === null) return false;
// current = current.left;
// }else{
// if(current.right === null) return false;
// current = current.right;
// }
// }
// }
// return false;
// }
search(key){ // 做法二：使用递归
if(key !== null && key !== undefined){
return this.searchNode(this.root, key);
}
return false;
}
searchNode(node, key){
if(node === null || node === undefined){
return false;
}
if(this.compareFn(key, node.key) === Compare.LESS_THAN){
return this.searchNode(node.left, key);
}else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN){
return this.searchNode(node.right, key);
}else{
return true;
}
}
inOrderTraverse(){
return this.inOrderGetNode(this.root);
}
inOrderGetNode(node){
let arr = [];
if(node == null) return arr;
if(node.left !== null){
arr.push(...this.inOrderGetNode(node.left));
}
arr.push(node.key);
if(node.right !== null){
arr.push(...this.inOrderGetNode(node.right));
}
return arr;
}
preOrderTraverse(){
return this.preOrderGetNode(this.root);
}
preOrderGetNode(node){
let arr = [];
if(node === null) return arr;
arr.push(node.key);
if(node.left !== null){
arr.push(...this.preOrderGetNode(node.left));
}
if(node.right !== null){
arr.push(...this.preOrderGetNode(node.right));
}
return arr;
}
postOrderTraverse(){
return this.postOrderGetNode(this.root);
}
postOrderGetNode(node){
let arr = [];
if(node === null) return arr;
if(node.left !== null){
arr.push(...this.postOrderGetNode(node.left));
}
if(node.right !== null){
arr.push(...this.postOrderGetNode(node.right));
}
arr.push(node.key);
return arr;
}
min(){
return this.getMinNode(this.root);
}
getMinNode(node){
if(node === null) return undefined;
if(node.left !== null){
return this.getMinNode(node.left);
}else{
return node;
}
}
max(){
return this.getMaxNode(this.root);
}
getMaxNode(node){
if(node === null) return undefined;
if(node.right !== null){
return this.getMaxNode(node.right);
}else{
return node;
}
}
remove(key){
if(key == null || key == undefined) return false;
this.root = this.removeNode(this.root, key);
return true;
}
removeNode(node, key){
if(node === null || node === undefined) return null;
// key 小于当前节点值时
if(this.compareFn(key, node.key) === Compare.LESS_THAN){
node.left = this.removeNode(node.left, key); // 继续向左查找
return node; // 保留该节点之上的内容
}
// key 大于当前节点值时
else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN){
node.right = this.removeNode(node.right, key); // 继续向右查找
return node; // 保留该节点之上的内容
}
// 查找到对应 key的节点时
else{
// 若节点是叶节点/外部节点（没有子节点）
if(node.left === null && node.right === null){
node = null; // 将节点变为 null，并返回给上层递归（父节点）（看上面代码，返回后便是null）
return node;
}
// 若节点有一个子节点
if(node.left === null){ // 判断子节点是否为右侧子节点
node = node.right; // 用右侧子节点代替原来的位置
return node; // 返回节点交给上层递归（父节点）
}else if(node.right === null){ // 判断子节点是否为左侧子节点
node = node.left; // 用左侧子节点代替原来的位置
return node; // 返回节点交给上层递归（父节点）
}
// 若节点有两个及以上子节点
const aux = this.getMinNode(node.right); // 为了保证二叉树的结构性，需要使用右侧最小的值来代替，此处用上面的 getMinNode(node) 来获取自身右侧最小的值
node.key = aux.key; // 替代原本的值
node.right = this.removeNode(node.right, aux.key); // 替代完后需要把右侧最小的值删掉（没有子节点），只需要重复执行这个函数即可
return node; // 删除完成后返回节点交给上层递归（父节点）
}
}
}
复制代码实际使用： 添加的元素变成的树是这样的：
const tree1 = new BinarySearchTree();
tree1.insert(8);
tree1.insert(5);
tree1.insert(7);
tree1.insert(3);
tree1.insert(2);
tree1.insert(9);
tree1.insert(12);
tree1.insert(1);
tree1.insert(4);
tree1.insert(10);
console.log(tree1.search(8)); // true
console.log(tree1.search(6)); // false
console.log(tree1.inOrderTraverse()); // [1, 2, 3, 4, 5, 7, 8, 9, 10, 12]
console.log(tree1.preOrderTraverse()); // [8, 5, 3, 2, 1, 4, 7, 9, 12, 10]
console.log(tree1.postOrderTraverse()); // [1, 2, 4, 3, 7, 5, 10, 12, 9, 8]
console.log(tree1.min()); // 1
console.log(tree1.max()); // 12
console.log(tree1.remove(3));
console.log(tree1.inOrderTraverse()); // [1, 2, 4, 5, 7, 8, 9, 10, 12]
复制代码总结一下代码：
对于插入和查找，还是很简单的，使用递归的话对函数的功能分工会更加好点（拆解函数功能使其分工明确）
对于遍历，首先最先搞得必然是最简单的中序排序。我的思路是，如果说一个树结构只有一个节点和两个子节点，那他们合并其实就是类似于 left + center + right的这种结构，大致如图：
也就是说，如果当前某个节点有子节点，那我完全可以使用递归先让他们压在一块，然后在和父节点组合在一起，然后就完成了中序遍历。
更巧妙的事情发生了，因为他三种遍历的不同，仅仅是因为遍历的顺序的不同，所以经需要修改一下我们把键添加到数组的顺序，就完成了先序比哪里和后序遍历了。
至于删除节点，上面的注释也写了，根据情况来决定。
4. AVL 树（Adelson-Velskii-Landi）
要知道什么是 AVL树，首先需要知道上面是 自平衡树。
在我们使用二叉树的时候，随着数据的增加，很容易出现书的某一条边会非常的深，导致树的的重量倾斜与一边，这样在对这条边的操作上会引起一些性能为问题，所以我们会尽量使树达到平衡。如图：
而 AVL树是一种 自平衡树，操作节点的时候，AVL树hui蚕食保持平衡，任意一个节点的左子树和右子树的高度差最多为 1。
一些术语：
- 节点高度：指的是节点到任意子节点最深节点的最大值，同时分为左子树高度和右子树高度。比如上图未修改前，节点5 的左子树高度为 3，右子树高度为 1.
- 平衡因子：对在每个节点计算右子树高度减去左子树高度，得出来的值应该为 0、1、-1（达到平衡效果），如节点5的高度差值就是2，节点2 的高度差值就是 -1，如果不是的话，则需要平衡 AVL树，这种概念就是 平衡因子
我们要将树实现平衡，可以执行单旋转和双旋转两种平衡操作，分别对应四种场景。
- 左-左(LL)： 左 侧子节点的高度大于右侧子节点的高度，且 左侧子节点也是平衡或 左 侧较重，如图：
我们将树进行一次右旋转操作即可。
- 右-右(RR)： 与左左相反，右 侧子节点的高度大于左侧子节点的高度，且 右侧子节点也是平衡或 右 侧较重，如图：
我们将树进行一次左旋转操作即可。
- 左-右(LR)： 这种情况出现于 左 侧子节点的高度大于右侧子节点的高度的同时，左侧子节点是右侧偏重。如图：
我们将树进行一次左旋转，然后在进行一次右旋转操作即可
- 右-左(RL)： 与左右相反，右 侧子节点的高度大于左侧子节点的高度的同时，右侧子节点是左侧偏重。如图：
我们将树进行一次右旋转，然后在进行一次左旋转操作即可。
PS: 不知道你们看没看出来怎么个旋转法，而且名字也干涩难懂，大致逻辑搞懂了，但我还是没看出来怎么旋转的，欢迎留言告知。
知道以上用于处理树的平衡的方法后，就可以着手编写代码了。因为 AVL树 也是一种 BST树，所以我们经需要继承原本写的代码即可。
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
}
class AVLTree extends BinarySearchTree{
constructor(compareFn = defaultCompare){
super(compareFn);
this.compareFn = compareFn;
this.root = null;
}
getNodeHeight(node){ // 用于获取一个节点的高度
if(node === null){
return -1;
}
return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}
getBalanceFactor(node){
const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right); // 用 左子节点高度 减去 右子节点高度
switch(heightDifference){
case -2: // 若为 -2，代表右子节点高度较大（右子树偏重）
return BalanceFactor.UNBALANCED_RIGHT;
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT; // 若为 -1，代表右子节点高度稍大（右子树稍重）
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT; // 若为 1，代表左子树节点高度稍大（左子树稍重）
case 2:
return BalanceFactor.UNBALANCED_LEFT; // 若为 2，代表左子树节点高度较大（左子树稍重）
default:
return BalanceFactor.BALANCED; // 若为 0，则代表左右子树节点高度平衡（两边子树高度相等），在插入元素的时候会进行判断，所以不会出现 3啊、-3啊这种情况（有的话早给平衡因子干掉了）
}
}
rotationLL(node){ // 向右单旋转一次
const tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
rotationRR(node){ // 向左单旋转一次
const tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}
rotationLR(node){ // 向左单旋转一次然后向右单旋转一次
node.left = this.rotationRR(node.left);
return this.rotationLL(node);
}
rotationRL(node){ // 向右单旋转一次然后向左单旋转一次
node.right = this.rotationLL(node.right);
return this.rotationRR(node);
}
insert(key){
this.root = this.insertNode(this.root, key);
}
insertNode(node, key){
// 添加元素
if(node == null){ // 当前节点为空时返回一个新元素
return new Node(key);
}else if(this.compareFn(key, node.key) === Compare.LESS_THAN){ // 判断是否比当前节点的值要小，则递归到当前节点的左子节点
node.left = this.insertNode(node.left, key);
}else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN){ // 判断是否比当前节点的值要大，则递归到当前节点的右子节点
node.right = this.insertNode(node.right, key);
}else{ // 判断与当前节点的值相等时，则不变
return node;
}
// 处理平衡因子
const balanceFactor = this.getBalanceFactor(node); // 获取当前节点的平衡情况
if(balanceFactor === BalanceFactor.UNBALANCED_LEFT){ // 若当前节点的左子节点高度大于右子节点时
if(this.compareFn(key, node.left.key) === Compare.LESS_THAN){ // 判断当前的值添加进去的位置，若是添加在了左子节点上，则形成了 左-左 情况
node = this.rotationLL(node);
}else{ // 若添加在了右子节点上，则形成了 左-右 情况
return this.rotationLR(node);
}
}
if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT){ // 若当前节点的右子节点高度大于左子节点时
if(this.compareFn(key, node.right.key) === Compare.BIGGER_THAN){ // 判断当前的值添加进去的位置，若是添加在了右子节点上，则形成了 右-右 情况
node = this.rotationRR(node);
}else{ // 若添加在了左子节点上，则形成了 右-左 情况
return this.rotationRL(node);
}
}
return node;
}
removeNode(node, key){
// 执行父类的删除操作
node = super.removeNode(node, key);
if(node == null){ // 如果删除了根元素导致返回的 node为 null，则不需要进行平衡操作
return node;
}
// 处理平衡因子
const balanceFactor = this.getBalanceFactor(node); // 获取当前节点的平衡情况
if(balanceFactor === BalanceFactor.UNBALANCED_LEFT){ // 若当前节点的左子节点高度大于右子节点时
const balanceFactorLeft = this.getBalanceFactor(node.left); // 判断当前节点的左子节点的平衡情况
if(balanceFactorLeft === BalanceFactor.BALANCED || balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT){ // 若当前节点的右子节点处于平衡或侧重于右边，则为 左-左 情况
return this.rotationLL(node);
}
if(balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT){ // 若当前节点的右子节点侧重于左边，则为 左-右 情况
return this.rotationLR(node.left);
}
}
if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT){ // 若当前节点的右子节点高度大于左子节点时
const balanceFactorRight = this.getBalanceFactor(node.right); // 判断当前节点的右子节点的平衡情况
if(balanceFactorRight === BalanceFactor.BALANCED || balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT){ // 若当前节点的右子节点处于平衡或侧重于右边，则为 右-右 情况
return this.rotationRR(node);
}
if(balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT){ // 若当前节点的右子节点侧重于左边，则为 右-左 情况
return this.rotationRL(node.right);
}
}
return node;
}
}
复制代码实际使用效果：
const tree2 = new AVLTree();
tree2.insert(10);
tree2.insert(15);
tree2.insert(12);
tree2.insert(18);
tree2.insert(11);
tree2.insert(14);
console.log(tree2.preOrderTraverse()); // [12, 10, 11, 15, 14, 18]
tree2.insert(20);
console.log(tree2.preOrderTraverse()); // [12, 10, 11, 15, 14, 18, 20]
console.log(tree2.remove(11)); // true
console.log(tree2.preOrderTraverse()); // [15, 12, 10, 14, 18, 20]
复制代码别问，问就是没有红黑树，还没搞懂，后面的内容搞懂了在另外写一章。
七、总结
- 栈： 遵循后进先出（LIFO） 原则的有序集合
- 队列： 遵循先进先出（FIFO） 原则的有序集合
- 双端队列： 一种允许两端进行数据操作的特殊队列
- 链表： 通过每个项的一个指针来记录下一个项来达到有序的元素集合
- 双向链表： 在链表的基础上每个项还有一个指针记录着上一个项的特殊链表
- 循环链表： 在链表的基础上最后一个项的指针指向第一个项的特殊链表
- 有序链表： 在链表的基础上能够进行项的自动排序的特殊链表
- 集合： 由一组无序且唯一的项组成。
- 空集： 不包含任何元素的特殊集合
- 字典： 通过一组映射关系的形式村粗元素的集合。
- 散列表： 通过散列函数得到的散列值组成的特殊字典，也成为哈希表
- 树： 一种分层数据的抽象模型
-
二叉搜索树（BST）： 仅允许有两个子节点，且左子节点比当前值小，右子节点比当前值大的特殊树
-
AVL树： 一种自平衡的特殊二叉树，会保持左子树与右子树的高度差最多为 1
-
红黑树： 也是一种自平衡的二叉树，相比于 AVL树 它对频繁的数据操作性能更好些，而 AVL树 对数据的查找搜索等性能则比红黑树要好
-
如有错误，欢迎指出。
新人上路，还请多多包含。
我是MoonLight，一个初出茅庐的小前端。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
