js数据结构与算法

数据结构

1、数组 Array

对应JavaScript的数组。

2、栈 Stack

栈：先进后出的数据结构

1. push(value) 入栈
2. pop() 出栈
3. peek() 查看栈顶元素
4. isEmpty() 判断栈是否为空
5. size() 获取栈的长度
6. clear() 清空栈
7. print() 将栈中元素以字符串形式返回

3、队列 Queue

1、双端队列 Deque

两端都可以入队和出队的队列

class Deque {
  #items = {};
  #lowCounter = 0;
  #highCounter = 0;

  // .....
  *[Symbol.iterator]() {
    for (let key of this.#items) {
      yield this.#items[key];
    }
  }
}

1. enqueueBack(value) 在队尾入队

   enqueueBack(element) {
     this.#items[this.#highCounter] = element;
     this.#highCounter++;
   }
   

2. enqueueFront(value) 在队头入队

   enqueueFront(element) {
     this.#lowCounter--;
     this.#items[this.#lowCounter] = element;
   }
   

3. dequeueBack() 在队尾出队

   dequeueBack() {
     if (this.isEmpty()) return undefined;
     this.#highCounter--;
     let res = this.#items[this.#highCounter];
     delete this.#items[this.#highCounter];
     return res;
   }
   

4. dequeueFront() 在队头出队

   dequeueFront() {
     if (this.isEmpty()) return undefined;
     let res = this.#items[this.#lowCounter];
     delete this.#items[this.#lowCounter];
     this.#lowCounter++;
     return res;
   }
   

5. back() 获取队尾元素

   back() {
     return this.#items[this.#highCounter - 1];
   }
   

6. front() 获取队头元素

   front() {
     return this.#items[this.#lowCounter];
   }
   

7. isEmpty() 判断队列是否为空

   isEmpty() {
     return this.#highCounter === this.#lowCounter;
   }
   

8. size() 获取队列的长度

   size() {
     return this.#highCounter - this.#lowCounter;
   }
   

9. clear() 清空队列

   clear() {
     this.#items = {};
     this.#lowCounter = 0;
     this.#highCounter = 0;
   }
   

10. print() 将队列中元素以字符串形式返回

    print() {
      console.log(Object.values(this.#items).toString());
    }
    

2、队列 Queue

先进先出的数据结构

// 队列结构的实现
class Queue extends Deque {
  enqueue = super.enqueueBack;
  dequeue = super.dequeueFront;

  enqueueBack = null;
  enqueueFront = null;
  dequeueBack = null;
  dequeueFront = null;
  back = null;

  *[Symbol.iterator]() {
    yield* super[Symbol.iterator]();
  }
}

1. enqueue(value) 入队
2. dequeue() 出队
3. front() 获取队列头部元素
4. isEmpty() 判断队列是否为空
5. size() 获取队列的长度
6. clear() 清空队列
7. print() 将队列中元素以字符串形式返回

4、链表 LinkedList

4-1、单链表

LinkedList: 每个节点包含一个值和一个指向下一个节点的指针，最后一个节点指向 null。

// 链表节点
class LinkedListNode {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

// 单链表的实现
class LinkedList {
  #count = 0;
  #head = null;
  #foot = null;

  _getHead() {
    return this.#head;
  }

  _setHead(head) {
    this.#head = head;
  }

  _getFoot() {
    return this.#foot;
  }

  _setFoot(foot) {
    this.#foot = foot;
  }

  _getCount() {
    return this.#count;
  }

  _setCount(count) {
    this.#count = count;
  }

  // ......
  *[Symbol.iterator]() {
    let current = this.#head;
    while (current) {
      yield current.element;
      current = current.next;
    }
  }
}

1. append(element): 在链表末尾添加一个元素。

   append(element) {
     const newNode = new LinkedListNode(element);
     if (this.#head === null) {
       this.#head = newNode;
       this.#foot = newNode;
     } else {
       this.#foot.next = newNode;
       this.#foot = newNode;
     }
     this.#count++;
   }
   

2. insert(position, element): 在链表指定位置插入一个元素。

   insert(position, element) {
     if (position >= 0 && position <= this.#count) {
       const newNode = new LinkedListNode(element);
       let current;
   
       if (position === 0) {
         newNode.next = this.#head;
         this.#head = newNode;
       } else {
         current = this.#head;
         for (let i = 1; i < position; i++) {
           current = current.next;
         }
         newNode.next = current.next;
         current.next = newNode;
       }
       this.#count++;
       return true;
     }
     return false;
   }
   

3. get(position): 获取链表中指定位置的元素。

   get(position) {
     if (position > -1 && position < this.#count) {
       let current = this.#head;
       for (let i = 0; i < position && current !== null; i++) {
         current = current.next;
       }
       return current ? current.element : undefined;
     }
     return undefined;
   }
   

4. indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回-1。

   indexOf(element) {
     let current = this.#head;
     for (let i = 0; i < this.#count && current !== null; i++) {
       if (current.element === element) return i;
       // 这里并不严谨
       // if (DataType.isEqual(current.element, element)) return i;
       
       current = current.next;
     }
     return -1;
   }
   

5. update(position, element): 修改链表中指定位置的元素。

   update(position, element) {
     if (position > -1 && position < this.#count) {
       let current = this.#head;
       for (let i = 0; i < position && current !== null; i++) {
         current = current.next;
       }
       current.element = element;
       return true;
     }
     return false;
   }
   

6. removeAt(position): 从链表中移除指定位置的元素。

   removeAt(position) {
     if (position > -1 && position < this.#count) {
       let current = this.#head;
       if (position === 0) {
         this.#head = current.next;
       } else {
         let previous;
         for (let i = 0; i < position; i++) {
           previous = current;
           current = current.next;
         }
         previous.next = current.next;
       }
       this.#count--;
       return current.element;
     }
     return undefined;
   }
   

7. remove(element): 从链表中移除指定元素。

   remove(element) {
     const index = this.indexOf(element);
     return this.removeAt(index);
   }
   

8. isEmpty(): 判断链表是否为空。

   isEmpty() {
     return this.#count === 0;
   }
   

9. size(): 返回链表的长度。

   size() {
     return this.#count;
   }
   

10. toString(): 返回链表的字符串表示。

    toString() {
      let current = this.#head;
      let str = "";
      while (current) {
        str += current.element + (current.next ? ", " : "");
        current = current.next;
      }
      return str;
    }
    

4-2、双向链表

DoublyLinkedList: 每个节点包含一个值、一个指向前一个节点的指针和一个指向下一个节点的指针。

// 双向链表节点
class DoublyLinkedListNode extends LinkedListNode {
  constructor(element) {
    super(element);
    this.prev = null;
  }
}

// 双向链表的实现
class DoublyLinkedList extends LinkedList {
  
	// ......
  *[Symbol.iterator]() {
    yield* super[Symbol.iterator]();
  }
}

1. append(element): 在链表末尾添加一个元素。

   append(element) {
     const newNode = new DoublyLinkedListNode(element);
     if (this._getHead() === null) {
       this._setHead(newNode);
       this._setFoot(newNode);
     } else {
       this._getFoot().next = newNode;
       newNode.prev = this._getFoot();
       this._setFoot(newNode);
     }
     this._setCount(this._getCount() + 1);
   }
   

2. insert(position, element): 在链表指定位置插入一个元素。

   insert(position, element) {
     if (position >= 0 && position <= this._getCount()) {
       const newNode = new DoublyLinkedListNode(element);
       let current;
   
       if (position === 0) {
         if (this._getCount() === 0) {
           this._setHead(newNode);
           this._setFoot(newNode);
         } else {
           newNode.next = this._getHead();
           this._getHead().prev = newNode;
           this._setHead(newNode);
         }
       } else if (position === this._getCount()) {
         this._getFoot().next = newNode;
         newNode.prev = this._getFoot();
         this._setFoot(newNode);
       } else {
         current = this._getHead();
         for (let i = 1; i < position; i++) {
           current = current.next;
         }
         newNode.next = current.next;
         newNode.prev = current;
         current.next = newNode;
       }
       this._setCount(this._getCount() + 1);
       return true;
     }
     return false;
   }
   

3. get(position): 获取链表中指定位置的元素。

4. indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回-1。

5. update(position, element): 修改链表中指定位置的元素。

6. removeAt(position): 从链表中移除指定位置的元素。

   removeAt(position) {
     if (position > -1 && position < this._getCount()) {
       let current = this._getHead();
       if (position === 0) {
         this._setHead(current.next);
         if (this._getCount() === 1) {
           this._setFoot(null);
         } else {
           this._getHead().prev = null;
         }
       } else if (position === this._getCount() - 1) {
         current = this._getFoot();
         this._getFoot().prev.next = null;
         this._setFoot(current.prev);
       } else {
         for (let i = 0; i < position; i++) {
           current = current.next;
         }
         current.prev.next = current.next;
         current.next.prev = current.prev;
       }
       this._setCount(this._getCount() - 1);
       return current.element;
     }
     return undefined;
   }
   

7. remove(element): 从链表中移除指定元素。

   remove(element) {
     const index = this.indexOf(element);
     return this.removeAt(index);
   }
   

8. isEmpty(): 判断链表是否为空。

9. size(): 返回链表的长度。

10. toString(): 返回链表的字符串表示。

    toString() {
      let current = this._getHead();
      let str = "";
      while (current) {
        str += current.element + (current.next ? ", " : "");
        current = current.next;
      }
      return str;
    }
    

4-3、循环链表

CircularLinkedList: 最后一个节点指向第一个节点的链表, 形成一个环。

// 循环链表的实现
class CircularLinkedList extends LinkedList {
	// ......
 	*[Symbol.iterator]() {
    yield* super[Symbol.iterator]();
  }
}

1. append(element): 在链表末尾添加一个元素。

   append(element) {
     super.append(element);
     this._getFoot().next = this._getHead();
   }
   

2. insert(position, element): 在链表指定位置插入一个元素。

   insert(position, element) {
     super.insert(position, element);
     this._getFoot().next = this._getHead();
   }
   

3. get(position): 获取链表中指定位置的元素。

4. indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回-1。

5. update(position, element): 修改链表中指定位置的元素。

6. removeAt(position): 从链表中移除指定位置的元素。

   removeAt(position) {
     const result = super.removeAt(position);
     this._getFoot().next = this._getHead();
     return result;
   }
   

7. remove(element): 从链表中移除指定元素。

   remove(element) {
     const result = super.remove(element);
     this._getFoot().next = this._getHead();
     return result;
   }
   

8. isEmpty(): 判断链表是否为空。

9. size(): 返回链表的长度。

10. toString(): 返回链表的字符串表示。

    toString() {
      return super.toString() + ", " + this._getHead().element;
    }
    

5、Set和Map

6、散列表HashTable

使用散列函数生成index，然后添加到arr里面。

class HashTable {
  #table = [];
  
  // ......
  *[Symbol.iterator]() {
    for (let bucket of this.#table) {
      if (bucket) {
        for (let pair of bucket) {
          yield pair;
        }
      }
    }
  }
}

1. 离散函数：loseloseCode、DJB2、FNV

2. set(key, value)：新增修改

   set(key, value) {
     const index = HashFunction.loseloseHash(key);
     if (!this.#table[index]) {
       this.#table[index] = [];
     }
     // 简单的冲突处理：在同一个index使用数组存储键值对
     for (let pair of this.#table[index]) {
       if (DataType.isEqual(pair[0], key)) {
         pair[1] = value; // 更新已存在的键
         return;
       }
     }
     this.#table[index].push([key, value]); // 添加新的键值对
   }
   

3. delete(key)：删除

   delete(key) {
     const index = HashFunction.loseloseHash(key);
     if (this.#table[index]) {
       this.#table[index] = this.#table[index].filter(
         (pair) => !DataType.isEqual(pair[0], key)
       );
     }
   }
   

4. clear()：清空

   clear() {
     this.#table = [];
   }
   

5. get(key)：获取

   get(key) {
     const index = HashFunction.loseloseHash(key);
     if (this.#table[index]) {
       for (let pair of this.#table[index]) {
         if (DataType.isEqual(pair[0], key)) {
           return pair[1];
         }
       }
     }
     return undefined;
   }
   

6. size()：长度

   size() {
     return this.#table.reduce(
       (count, bucket) => count + (bucket ? bucket.length : 0),
       0
     );
   }
   

7、树 Tree

7-1、二叉搜索树

BinarySearchTree：简称BST

1. 节点结构

   class TreeNode {
     constructor(key) {
       this.key = key;
       this.left = null;
       this.right = null;
     }
   }
   

2. 构造函数

   class BST {
     constructor() {
       this.root = null;
     }
     // ......
   }
   

3. insert(key)：插入

   insert(key) {
     this.root = this._insertNode(this.root, key);
   }
   
   _insertNode(node, key) {
     if (node === null) {
       return new TreeNode(key);
     } else if (key < node.key) {
       node.left = this._insertNode(node.left, key);
     } else if (key > node.key) {
       node.right = this._insertNode(node.right, key);
     }
     
     return node;
   }
   

4. inOrderMap(callback)：中序遍历

   1. 使用遍历不断执行callback，返回查询结果
   2. 先查节点左边，然后中间，最后右边。每个节点都是如此递归重复操作。
   3. 最后就会输出 小到大 的顺序

   inOrderMap(callback) {
     this._inOrderMapNode(this.root, callback);
   }
   
   _inOrderMapNode(node, callback) {
     if (node !== null) {
       this._inOrderMapNode(node.left, callback);
       callback(node.key);
       this._inOrderMapNode(node.right, callback);
     }
   }
   

5. preOrderMap(callBack)：前序遍历

   preOrderMap(callback) {
     this._preOrderMapNode(this.root, callback);
   }
   
   _preOrderMapNode(node, callback) {
     if (node !== null) {
       callback(node.key);
       this._preOrderMapNode(node.left, callback);
       this._preOrderMapNode(node.right, callback);
     }
   }
   

6. postOrderMap(callBack)：后序遍历

   postOrderMap(callback) {
     this._postOrderMapNode(this.root, callback);
   }
   
   _postOrderMapNode(node, callback) {
     if (node !== null) {
       this._postOrderMapNode(node.left, callback);
       this._postOrderMapNode(node.right, callback);
       callback(node.key);
     }
   }
   

7. search(key)：查找，存在返回node，否则返回null

   search(key) {
     return this._searchNode(this.root, key);
   }
   
   _searchNode(node, key) {
     if (node === null) {
       return false;
     } else if (key < node.key) {
       return this._searchNode(node.left, key);
     } else if (key > node.key) {
       return this._searchNode(node.right, key);
     } else {
       return node;
     }
   }
   

8. min()：最小值

   min() {
     return this._minNode(this.root);
   }
   
   _minNode(node) {
     while (node.left !== null) {
       node = node.left;
     }
     return node;
   }
   

9. max()：最大值

   max() {
     return this._maxNode(this.root);
   }
   
   _maxNode(node) {
     while (node.right !== null) {
       node = node.right;
     }
     return node;
   }
   

10. remove(key)：删除

    1. 情况A：删除节点没有子节点，直接删除

11. 情况B：删除节点有单个子节点，子节点替换删除节点
    3. 情况C：删除节点有双节点
    - 找到删除节点下最大的子节点，替换删除节点的值
    - 同样的逻辑，删除最大的子节点。
    

    delete(key) {
      this.root = this._deleteNode(this.root, key);
    }
    
    _deleteNode(node, key) {
      if (node === null) {
        return null;
      } else if (key < node.key) {
        node.left = this._deleteNode(node.left, key);
      } else if (key > node.key) {
        node.right = this._deleteNode(node.right, key);
      } else {
        if (node.left === null && node.right === null) {
          node = null;
        } else if (node.left === null) {
          node = node.right;
        } else if (node.right === null) {
          node = node.left;
        } else {
          let _minNode = this._minNode(node.right);
          node.key = _minNode.key;
          node.right = this._deleteNode(node.right, node.key);
        }
      }
      return node;
    }
    

7-2、平衡二叉树

Adelson-Velskii-Landi ：简称AVL。

1. 平衡二叉树也是二叉树，所以可以直接继承二叉树

   class AVL extends BST {
     constructor() {
       super();
     }
     // ...
   }
   

2. 树的高度

   树的高度 = Math.max(左边子节点层级，右边子节点层级）。

   _getNodeHeight(node) {
     if (node === null) return -1;
     return (
       Math.max(
         this._getNodeHeight(node.left),
         this._getNodeHeight(node.right)
       ) + 1
     );
   }
   

3. 平衡因子

   平衡因子 = 左子节点层级 - 右子节点层级

   _getBalanceFactor(node) {
     if (node === null) return 0;
     return this._getNodeHeight(node.left) - this._getNodeHeight(node.right);
   }
   

4. 失衡判断：左右两边的层级数相差不能大于2，平衡因子不能大于1

5. 左旋

   

   _leftRotate(node) {
     let newRoot = node.right;
     node.right = newRoot.left;
     newRoot.left = node;
     return newRoot;
   }
   

6. 右旋

_rightRotate(node) {
  let newRoot = node.left;
  node.left = newRoot.right;
  newRoot.right = node;
  return newRoot;
}

7. 平衡节点

   1. LL型：如右旋图所示

   2. LR型：如下图所示
      

   3. RR型：如左旋图所示

   4. RL型：如下图所示

5. 所以的节点平衡都是由这四个基本类型组成

_balanceNode(node) {
  let balanceFactor = this._getBalanceFactor(node);
  if (balanceFactor > 1) {
    if (this._getBalanceFactor(node.left) < 0) {
      node.left = this._leftRotate(node.left); // LR型，先左旋
    }
    // LL型，右旋。并且被LR型复用一次
    node = this._rightRotate(node);
  } else if (balanceFactor < -1) {
    if (this._getBalanceFactor(node.right) > 0) {
      node.right = this._rightRotate(node.right);
    }
    node = this._leftRotate(node);
  }
  return node;
}

8. 插入

   insert(key) {
     this.root = this._insertNode(this.root, key);
   }
   
   _insertNode(node, key) {
     if (node === null) {
       return new TreeNode(key);
     } else if (key < node.key) {
       node.left = this._insertNode(node.left, key);
     } else if (key > node.key) {
       node.right = this._insertNode(node.right, key);
     }
   
     // 重新平衡树，从新节点开始向上调整树的结构，直到根节点为止。
     return this._balanceNode(node);
   }
   

9. 删除

   delete(key) {
     this.root = this._deleteNode(this.root, key);
   }
   
   _deleteNode(node, key) {
     if (node === null) {
       return null;
     } else if (key < node.key) {
       node.left = this._deleteNode(node.left, key);
     } else if (key > node.key) {
       node.right = this._deleteNode(node.right, key);
     } else {
       if (node.left === null && node.right === null) {
         node = null;
       } else if (node.left === null) {
         node = node.right;
       } else if (node.right === null) {
         node = node.left;
       } else {
         let _minNode = this._minNode(node.right);
         node.key = _minNode.key;
         node.right = this._deleteNode(node.right, node.key);
       }
     }
   
     // 重新平衡树，从删除节点开始向上调整树的结构，直到根节点为止。
     return this._balanceNode(node);
   }
   

7-3、红黑树

红黑树的定义：左根右、根叶黑、不红红、黑路同

1. 必须是二叉搜索树

2. 根和叶子(null)都是黑色

3. 不存在连续的两个红色节点

4. 任一节点到其叶子的所有路径上，黑节点数量相同
   

5. 节点结构

   const RED = Symbol("RED");
   const BLANK = Symbol("Black");
   
   class RBTreeNode {
     constructor(key) {
       this.key = key;
       this.color = RED; // 默认为红色
       this.left = null;
       this.right = null;
       this.parent = null;
     }
   }
   

6. 红黑树也是二叉树，所以继承二叉树

   class RBTree extends BST {
     constructor() {
       super();
     }
     
     // .....
   }
   

7. 左旋

   _leftRotate(node) {
     let newNode = node.right;
   
     node.right = newNode.left;
     if (node.right !== null) {
       node.right.parent = node;
     }
   
     newNode.parent = node.parent;
     if (node.parent === null) {
       this.root = newNode;
     } else if (node === node.parent.left) {
       node.parent.left = newNode;
     } else {
       node.parent.right = newNode;
     }
   
     newNode.left = node;
     node.parent = newNode;
   }
   

8. 右旋

   _rightRotate(node) {
     let newNode = node.left;
   
     node.left = newNode.right;
     if (node.left !== null) {
       node.left.parent = node;
     }
   
     newNode.parent = node.parent;
     if (node.parent === null) {
       this.root = newNode;
     } else if (node === node.parent.left) {
       node.parent.left = newNode;
     } else {
       node.parent.right = newNode;
     }
   
     newNode.right = node;
     node.parent = newNode;
   }
   

9. 树调节

   /* 
     插入修正
     1、新插入的节点颜色为红色
     2、如果父节点为黑色，则不需要修正
     3、如果父节点为红色，则需要修正
       1、叔叔节点为红色
         1、叔叔和父亲节点都变为黑色，祖父节点变为红色
         2、对祖父节点进行修正
       2、叔叔节点为黑色
         1、父节点为祖父节点的左子节点
           1、新节点为父节点的右子节点 - 左旋父亲节点,再右旋祖父节点
           2、新节点为父节点的左子节点 - 右旋祖父节点
           3、旋转完成后，父变黑，祖父变红，对父修正
         2、父节点为祖父节点的右子节点
           1、新节点为父节点的左子节点 - 右旋父亲节点,再左旋祖父节点
           2、新节点为父节点的右子节点 - 左旋祖父节点
           3、旋转完成后，父变黑，祖父变红，对父修正
     4、将根节点设置为黑色
   */
   _fixInsert(node) {
     while (
       node &&
       node.color === RED &&
       node.parent &&
       node.parent.color === RED
     ) {
       let parent = node.parent;
       let grandParent = parent.parent;
   
       if (grandParent && grandParent.left === parent) {
         let uncle = grandParent.right;
         if (uncle && uncle.color === RED) {
           grandParent.color = RED;
           parent.color = BLANK;
           uncle.color = BLANK;
           node = grandParent;
         } else {
           if (node === parent.right) {
             this._leftRotate(parent);
             node = parent;
             parent = node.parent;
           }
           this._rightRotate(grandParent);
           parent.color = BLANK;
           grandParent.color = RED;
           node = parent;
         }
       } else if (grandParent && grandParent.right === parent) {
         let uncle = grandParent.left;
         if (uncle && uncle.color === RED) {
           grandParent.color = RED;
           parent.color = BLANK;
           uncle.color = BLANK;
           node = grandParent;
         } else {
           if (node === parent.left) {
             this._rightRotate(parent);
             node = parent;
             parent = node.parent;
           }
           this._leftRotate(grandParent);
           parent.color = BLANK;
           grandParent.color = RED;
           node = parent;
         }
       }
     }
   
     this.root.color = BLANK;
   }
   

10. 插入

    insert(key) {
      let newNode = new RBTreeNode(key);
      this.root = this._insertNode(this.root, newNode);
      this._fixInsert(newNode);
    }
    
    _insertNode(node, newNode) {
      if (node === null) {
        return newNode;
      } else if (newNode.key < node.key) {
        node.left = this._insertNode(node.left, newNode);
        node.left.parent = node;
      } else if (newNode.key > node.key) {
        node.right = this._insertNode(node.right, newNode);
        node.right.parent = node;
      }
    
      return node;
    }
    

11. 删除

    /* 
      删除修正
      1、如果删除的是红色节点，执行正常的删除操作，不需要修正
      2、左右都有子节点：最后都会转变为只有一个子节点或者没有子节点的情况
      3、只有一个子节点，此时子节点必然是红色。直接将子节点的值替换到父节点，然后删除子节点
      4、没有子节点
        1、父节点为红色，执行删除操作，不需要修正
        2、父节点为黑色: 兄弟节点必然存在
          1、兄弟节点为黑色
            1、兄弟节点至少有一个红色节点：(LL、RR、LR、RL)变色 + 旋转
              1、兄在左，兄左有红子树。兄子变黑，兄变父色，父变黑，父右旋, LL
              2、兄在右，兄右有红子树。兄子变黑，兄变父色，父变黑，父左旋, RR
              3、兄在左，兄左用黑子树。子变父色，兄左旋，父右旋, LR
              4、兄在右，兄右用黑子树。子变父色，兄右旋，父左旋, RL
            2、兄弟节点全部是黑色节点：
              1、兄弟节点变红
              2、如果父节点为红色，父变黑
              3、如果父节点为黑色，对父修正
          2、兄弟节点为红色
            1、兄变黑，父变红
            2、父像删除节点方向选择
            3、获取新的兄弟节点，继续修正
    */
    _fixDelete(node) {
      while (node && node.color === BLACK && node.parent !== null) {
        let sibling = null;
        let parent = node.parent;
        let isLeftChild = parent.left === node;
        sibling = isLeftChild ? parent.right : parent.left;
    
        if (!sibling) break;
    
        // 情况1：兄红
        if (sibling.color === RED) {
          parent.color = RED;
          sibling.color = BLACK;
    
          if (isLeftChild) {
            this._leftRotate(parent);
          } else {
            this._rightRotate(parent);
          }
    
          sibling = isLeftChild ? parent.right : parent.left;
        }
    
        if (!sibling) break;
    
        // 情况2：兄黑兄子全黑
        if (
          (sibling.left === null || sibling.left.color === BLACK) &&
          (sibling.right === null || sibling.right.color === BLACK)
        ) {
          sibling.color = RED;
          if (parent.color === RED) {
            parent.color = BLACK;
          } else {
            node = parent;
            continue; // 递归修正
          }
        } else {
          // 情况3：兄黑，至少有一个子节点是红色
          // 情况3-1：兄弟的红子树在删除节点的方向上。此时是LR或RL。
          // 逻辑就可以先完成兄旋转，然后转换为LL或RR的情况。
          if (
            (isLeftChild && sibling.right.color === BLACK) ||
            (!isLeftChild && sibling.left.color === BLACK)
          ) {
            sibling.color = RED;
            if (isLeftChild && sibling.left) {
              sibling.left.color = BLACK;
            } else if (!isLeftChild && sibling.right) {
              sibling.right.color = BLACK;
            }
    
            if (isLeftChild) {
              this._rightRotate(sibling);
            } else {
              this._leftRotate(sibling);
            }
    
            sibling = isLeftChild ? parent.right : parent.left;
          }
    
          if (!sibling) break;
    
          // 情况3-2：兄弟的红子树在删除节点的反方向上。此时是LL或RR
          sibling.color = parent.color;
          parent.color = BLACK;
          if (isLeftChild) {
            sibling.right.color = BLACK;
            this._leftRotate(parent);
          } else {
            sibling.left.color = BLACK;
            this._rightRotate(parent);
          }
          break;
        }
      }
    }
    
    // 删除节点
    delete(key) {
      let res = {};
      this.root = this._deleteNode(this.root, key, res);
      this._fixDelete(res.node);
    }
    
    _deleteNode(node, key, res) {
      if (node === null) {
        return null;
      } else if (key < node.key) {
        node.left = this._deleteNode(node.left, key, res);
        node.left.parent = node;
      } else if (key > node.key) {
        node.right = this._deleteNode(node.right, key, res);
        node.right.parent = node;
      } else {
        if (node.left === null && node.right === null) {
          res.node = node;
          node = null;
        } else if (node.left === null) {
          node.key = node.right.key;
          node.right = null;
        } else if (node.right === null) {
          node.key = node.left.key;
          node.left = null;
        } else {
          let _minNode = this._minNode(node.right);
          node.key = _minNode.key;
          node.right = this._deleteNode(node.right, node.key, res);
        }
      }
    
      return node;
    }
    

8、二叉堆

• 它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点）， 并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性
• 二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速 导出树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子 节点。这叫作堆特性

8-1、最小堆

// 最小堆的实现
class MinHeap {
  constructor() {
    this.heap = [];
  }

  getLeftIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  getParentIndex(childIndex) {
    if (childIndex === 0) return null;
    return Math.floor((childIndex - 1) / 2);
  }

  swap(indexOne, indexTwo) {
    [this.heap[indexOne], this.heap[indexTwo]] = [
      this.heap[indexTwo],
      this.heap[indexOne],
    ];
  }

  // 上浮操作
  siftUp(index) {
    let parent = this.getParentIndex(index);
    while (parent !== null && this.heap[index] < this.heap[parent]) {
      this.swap(parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }

  insert(value) {
    if (value !== null) {
      this.heap.push(value);
      this.siftUp(this.heap.length - 1);
      return true;
    }
    return false;
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  findMinimum() {
    return this.isEmpty() ? null : this.heap[0];
  }

  // 弹出最小值或最大值
  extract() {
    if (this.isEmpty()) return null;
    if (this.size() === 1) return this.heap.pop();
    const removedValue = this.heap.shift();
    this.siftDown(0);
    return removedValue;
  }

  // 下沉操作
  siftDown(index) {
    let element = index;
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();

    if (left < size && this.heap[element] > this.heap[left]) {
      element = left;
    }

    if (right < size && this.heap[element] > this.heap[right]) {
      element = right;
    }

    if (index !== element) {
      this.swap(index, element);
      this.siftDown(element);
    }
  }
}

8-2、最大堆

// 最大堆的实现
class MaxHeap extends MinHeap {
  constructor() {
    super();
  }
  
  findMinimum = null;

  findMaximum() {
    return this.isEmpty() ? null : this.heap[0];
  }

  // 重写上浮方法，使之成为最大堆
  siftUp(index) {
    let parent = this.getParentIndex(index);
    while (parent !== null && this.heap[index] > this.heap[parent]) {
      this.swap(parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }

  // 重写下沉操作，使之成为最大堆
  siftDown(index) {
    let element = index;
    const left = this.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();

    if (left < size && this.heap[element] < this.heap[left]) {
      element = left;
    }

    if (right < size && this.heap[element] < this.heap[right]) {
      element = right;
    }

    if (index !== element) {
      this.swap(index, element);
      this.siftDown(element);
    }
  }
}

9、图 Graph

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected;
    this.vertices = new Set(); // 顶点集合
    this.adjList = new Map(); // 邻接表，key为顶点，value为与该顶点相连的顶点的集合
  }

  // 添加顶点
  addVertex(vertices) {
    if (this.vertices.has(vertices)) return false;
    this.vertices.add(vertices);
    this.adjList.set(vertices, new Set()); // 初始化邻接表为空集合
    return true;
  }

  // 添加边
  addEdge(from, to) {
    // 如果不存在该顶点，则先添加顶点
    if (!this.adjList.get(from)) {
      this.addVertex(from);
    }
    if (!this.adjList.get(to)) {
      this.addVertex(to);
    }

    // 添加边 from -> to
    this.adjList.get(from).add(to);

    // 无向图两边都要添加
    if (!this.isDirected) {
      this.adjList.get(to).add(from);
    }
  }

  // 获取顶点集合
  getVertices() {
    return this.vertices;
  }

  // 获取邻接表
  getAdjList() {
    return this.adjList;
  }

  // 打印图 A -> B C D
  toString() {
    let s = "";
    this.adjList.forEach((value, key) => {
      s += `${key} -> `;
      value.forEach((v) => (s += v + " "));
      s += "\n";
    });
    return s;
  }
}

算法

1、散列函数

class HashFunction {
  // loselose散列函数
  static loseloseHash(str) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash += str.charCodeAt(i);
    }
    return hash % 37;
  }

  // DJB2散列函数
  static DJB2(str) {
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
      hash += (hash << 5) + str.charCodeAt(i);
    }
    return hash % 37;
  }

  // FNV散列函数
  static FNV(str) {
    let hash = 1315423911;
    for (let i = 0; i < str.length; i++) {
      hash ^= str.charCodeAt(i);
      hash +=
        (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24);
    }
    return hash % 37;
  }
}

2、排序算法 Sort

交换函数

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

2-1、冒泡排序

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

2-2、选择排序

function selectionSort(arr) {
  let minIndex;
  for (let i = 0; i < arr.length - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
  return arr;
}

2-3、插入排序

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

2-4、归并排序

/* 
  归并排序：递归拆分，合并排序。(分而治之)
  将大数组拆分成小数组，直到每个小数组只有一个元素
  然后遍历小数组，将它们合并成一个大数组，直到只剩下一个大数组
*/
function mergeSort(arr) {
  if (arr.length < 2) return arr;
  // 拆分数组，直到每个子数组只有一个元素
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;

  // 循环合并两个数组，直到其中一个数组为空
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // 将剩余的元素添加到结果数组中
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

2-5、快速排序

/* 
  快速排序
  选择一个基准值，将数组分成两部分，一部分小于等于基准值，一部分大于等于基准值
  递归地对这两部分进行快速排序，直到数组只剩下一个元素, 最后合并成一个有序数组
*/
function quickSort(arr) {
  if (arr.length < 2) return arr;
  // 基准值选择第一个元素
  const pivot = arr[0];
  const left = [];
  const right = [];

  // 将数组分成两部分，一部分小于等于基准值，一部分大于等于基准值
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 递归地对这两部分进行快速排序，直到数组只剩下一个元素
  return [...quickSort(left), pivot, ...quickSort(right)];
}

function quickSort2(arr, left = 0, right = arr.length - 1) {
	if (left >= right) return;

  // 选择基准值，这里选择最右边的元素
  const pivot = arr[right];

  // 初始化最小索引位置
  let i = left;

  // 将数组分成两部分
  for (let j = left; j < right; j++) {
    // 如果当前元素小于基准值，将其与最小索引位置的元素交换位置，并移动最小索引位置
    if (arr[j] < pivot) {
      this.swap(arr, i, j);
      i++;
    }
  }

  // 将基准值放到正确位置
  this.swap(arr, i, right);
  // 此时基准元素在i位置，i左边都是小于基准值的，i右边都是大于等于基准值的

  // 递归地对这两部分进行快速排序
  quickSort2(arr, left, i - 1); // 递归排序左半部分
  quickSort2(arr, i + 1, right); // 递归排序右半部分
}

2-6、计数排序

function countingSort(arr) {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  let range = max - min + 1;
  let countArr = new Array(range).fill(0);
  for (let i = 0; i < arr.length; i++) {
    countArr[arr[i] - min]++;
  }
  let index = 0;
  for (let j = 0; j < countArr.length; j++) {
    while (countArr[j] > 0) {
      arr[index++] = j + min;
      countArr[j]--;
    }
  }
  return arr;
}

2-7、桶排序

function bucketSort(arr) {
  let min = Math.min(...arr);
  let max = Math.max(...arr);
  let range = max - min + 1;
  let buckets = new Array(range).fill().map(() => []);
  for (let i = 0; i < arr.length; i++) {
    buckets[arr[i] - min].push(arr[i]);
  }
  let index = 0;
  for (let j = 0; j < buckets.length; j++) {
    if (buckets[j].length > 0) {
      insertSort(buckets[j]);
      while (buckets[j].length > 0) {
        arr[index++] = buckets[j].shift();
      }
    }
  }
  return arr;
}

2-8、基数排序

function radixSort(arr) {
  let max = Math.max(...arr);
  let digitCount = (max + "").length;
  for (let i = 0; i < digitCount; i++) {
    const buckets = new Array(10).fill().map(() => []);
    for (let j = 0; j < arr.length; j++) {
      buckets[Math.floor((arr[j] / Math.pow(10, i)) % 10)].push(arr[j]);
    }
    let index = 0;
    for (let k = 0; k < buckets.length; k++) {
      while (buckets[k].length > 0) {
        arr[index++] = buckets[k].shift();
      }
    }
  }
  return arr;
}

3、查找算法 Search

3-1、顺序查找

function sequentialSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

3-2、二分查找

// 二分查找 (有序数组查找)
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

3-3、插值查找

// 插值查找 (有序数组查找)
function interpolationSearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high && target >= arr[low] && target <= arr[high]) {
    const mid = Math.floor((target - arr[low]) * (high - low) / (arr[high] - arr[low]) + low);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

4、随机算法

// 洗牌算法
function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const randomIndex = Math.floor(Math.random() * (i + 1));
    swap(array, i, randomIndex);
  }
  return array;
}

5、算法设计

5-1、分而治之

分而治之 是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将解决方式合并以解决原来的问题

分而治之算法可以分成三个部分：

1. 分解原问题为多个子问题（原问题的多个小实例）
2. 解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题
3. 组合这些子问题的解决方式，得到原问题的解。

经典问题：归并排序、快速排序、二分查找

5-2、动态规划-DP

动态规划（dynamic programming, DP）是一种将复杂问题分解成更小的子问题来解决的优化技术

用动态规划解决问题时，要遵循三个重要步骤：

1. 定义子问题
2. 实现要反复执行来解决子问题的部分
3. 识别并求解出基本条件
4. 子问题是层层嵌套反馈的依赖关系

经典问题：

最少找零

/* 
动态规划 - 最少硬币找零问题
美国有四种硬币，面额分别为1、5、10、25美分。给定一个总金额n，求最少需要多少个硬币？
*/
let amount = 31;
let coins = [1, 5, 10, 25];

function minCoinsChange(coins, amount) {
  let y = 0;

  while (coins.length > 0) {
    y += Math.floor(amount / Math.max(...coins));
    amount %= Math.max(...coins);
    let index = coins.indexOf(Math.max(...coins));
    coins.splice(index, 1);
  }

  return y;
}

function minCoinsChange2(coins, amount) {
  let dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (const coin of coins) {
    for (let money = coin; money <= amount; money++) {
      dp[money] = Math.min(dp[money], dp[money - coin] + 1);
    }
  }

  return dp[amount];
}

01背包

/* 
背包问题
背包容量为8，有四个物品，每个物品有两个属性：[体积, 价值]，求最大价值。
*/
let maxBag = 10;
let weights = [3, 4, 5, 7];
let values = [3, 5, 6, 7];

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // 初始化二维 DP 数组（n+1 行，capacity+1 列）
  const dp = Array(n + 1)
    .fill(0)
    .map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1];
    const value = values[i - 1];
    for (let w = 1; w <= capacity; w++) {
      // 如果当前容量不足以装下第 i 个物品，继承上一行的结果
      if (w < weight) {
        dp[i][w] = dp[i - 1][w];
      } else {
        // 选择不装或装入，取最大值
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value);
      }
    }
  }
  return dp[n][capacity];
}

function knapSack2(weights, values, maxBag) {
  let dp = new Array(maxBag + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    const weight = weights[i];
    const value = values[i];
    for (let j = maxBag; j >= weight; j--) {
      dp[j] = Math.max(dp[j], dp[j - weight] + value);
    }
  }

  return dp[maxBag];
}

最小公共子序

// 最长公共子序列
let str1 = "acbaed";
let str2 = "abcadf";

function lcs(str1, str2) {
  let m = str1.length;
  let n = str2.length;

  // 初始化二维 DP 数组（m+1 行，n+1 列）
  const dp = Array(m + 1)
    .fill(0)
    .map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1; // 当前字符匹配，继承左上角的值并加一
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 当前字符不匹配，取左边或上边的最大值
      }
    }
  }

  return dp[m][n];
}

function lcs2(str1, str2) {
  let m = str1.length;
  let n = str2.length;
 
  // 初始化一维 DP 数组（长度为 n+1）
  const dp = Array(n + 1).fill(0);
 
  for (let i = 1; i <= m; i++) {
    // 创建一个临时数组来保存当前行的值
    const temp = Array(n + 1).fill(0);
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        temp[j] = dp[j - 1] + 1; // 当前字符匹配，继承之前的值并加一
      } else {
        temp[j] = Math.max(dp[j], dp[j - 1]); // 当前字符不匹配，取左边或上边的最大值
      }
    }
    // 将临时数组的值复制回 dp 数组，为下一轮迭代做准备
    dp = temp;
  }
 
  return dp[n];
}

5-3、贪心算法

贪心算法遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的 解），从而达到全局的最优（全局最优解）

// 分数背包问题
maxBag = 10;
weights = [3, 4, 5, 7];
values = [3, 5, 6, 7];

function fractionalKnapsack(weights, values, maxBag) {
  const n = weights.length;
  // 根据价值密度对物品进行排序，价值密度高的排在前面
  const items = Array.from({ length: n }, (_, i) => [
    values[i] / weights[i],
    weights[i],
    values[i]
  ]);
  items.sort((a, b) => b[0] - a[0]);

  let totalValue = 0;
  for (const item of items) {
    if (maxBag >= item[1]) {
      // 如果背包容量足够，装入整个物品
      totalValue += item[2];
      maxBag -= item[1];
    } else if (maxBag > 0) {
      // 如果背包容量不足，装入部分物品
      totalValue += item[0] * maxBag;
      break;
    }
  }

  return totalValue;
}

5-4、回溯算法

回溯是一种渐进式寻找并构建问题解决方式的策略。我们从一个可能的动作开始并试着用这个动作解决问题。如果不能解决，就回溯并选择另一个动作直到将问题解决。根据这种行为，回 溯算法会尝试所有可能的动作（如果更快找到了解决办法就尝试较少的次数）来解决问题

// 迷宫老鼠问题类似
let board = [
  ["A", "B", "C", "E"],
  ["S", "F", "C", "S"],
  ["A", "D", "E", "E"],
];
let word = "ABCCED";

function ratInAMaze(board, word) {
  const row = board.length;
  const col = board[0].length;

  // 遍历每一个点作为起点, 如果规定起点，就不需要双循环遍历起点了
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      let res = find(i, j, 0);
      if (res) return res;
    }
  }

  // 如果找不到，返回false
  return false;

  // 递归函数，从起点开始找，找到就走下去，找不到就回溯
  function find(r, c, cur) {
    // 边界条件判断，越界了就返回false
    if (r >= row || r < 0) return false;
    if (c >= col || c < 0) return false;

    // 不是当前字母就走下去，找到了就走下去，找不到就回溯
    if (board[r][c] !== word[cur]) return false;

    // 找到了最后一个字母，返回true
    if (cur === word.length - 1) return true;

    // 标记当前点走过，防止走回头路
    let temp = board[r][c];
    board[r][c] = null;

    // 四个方向递归找，找到了就走下去，找不到就回溯
    let ret =
      find(r + 1, c, cur + 1) || // 向下走
      find(r - 1, c, cur + 1) || // 向上走
      find(r, c + 1, cur + 1) || // 向右走
      find(r, c - 1, cur + 1);   // 向左走

    // 回溯，恢复现场
    board[r][c] = temp;
    return ret;
  }
}

6、算法复杂度

大 O 表示法将算法按照消耗的时间进行分类，依据随输入增大所需要的空间/内存。

1. O(1)

   function inc(n) {
     return ++n;
   }
   

2. O(n)

   function search(arr, value) {
     for (let i = 0; i < arr.length; i++) {
       if (arr[i] === value) return i
     }
     return -1;
   }
   

3. O(n2)

   function bubbleSort(arr) {
     for (let i = 0; i < arr.length - 1; i++) {
       for (let j = 0; j < arr.length - 1 - i; j++) {
         if (arr[j] > arr[j + 1]) {
           [arr[i], arr[j]] = [arr[j], arr[i]];
         }
       }
     }
     return arr;
   }
   

7、参考资料

1. 书籍《学习JavaScript数据结构与算法》第3版
2. b站视频：《千锋教育新版数据结构与算法视频教程》
3. b站视频：《红黑树 - 定义，插入，构建》- 作者：蓝不过海呀
4. b站视频：《红黑树 - 删除》- 作者：蓝不过海呀
5. b站视频：《[纯手推！！！]动态规划背包问题汇总 01背包。。。》 - 作者：T_zhao
6. b站视频：《动态规划中的01背包问题你清楚吗？…》 - 作者：渡一教育
7. b站视频：代码随想录 的合集视频