devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

平衡树：AVL 树、红黑树、B 树、B+ 树

作者：繁依Fanyi0 | 2024-04-26 17:15:03

赞

踩

平衡树：AVL 树、红黑树、B 树、B+ 树

平衡树：

平衡树是一种数据结构，它能够保持在插入或删除操作后，树的高度保持较小的增量，从而保持树的平衡性，提高了查找、插入和删除操作的效率。AVL树、红黑树、B树以及B+树都是常见的平衡树的变种，它们在不同的应用场景中具有不同的优势和特点。

  • AVL 树在需要严格平衡的场景下使用，例如需要快速的插入、删除和查找操作，而对内存消耗要求较高的情况。

  • 红黑树是一种近似平衡的二叉搜索树，它在插入和删除操作上比 AVL 树更加高效，常用于各种编程语言的标准库中，例如 C++ 的 std::map 和 Java 的 TreeMap。

  • B 树和 B+ 树广泛应用于数据库索引和文件系统中，它们能够有效地支持范围查询和顺序访问，并且能够处理大量数据。

​​​​​​​

AVL树（严格平衡的二叉搜索树）

AVL树是一种严格平衡的二叉搜索树，它要求任何节点的左子树和右子树的高度最多相差1。为了维持平衡，AVL树在插入或删除操作后会通过旋转操作来调整树的结构，以保持平衡性。AVL树的查询、插入和删除操作的时间复杂度都是O(log n)。

代码示例：

  1. class AVLNode {
  2.   /**
  3.    * 构造函数，用于创建一棵二叉树节点
  4.    *
  5.    * @param key 节点的键值
  6.    */
  7.   constructor(key) {
  8.     this.key = key;
  9.     this.left = null;
  10.     this.right = null;
  11.     this.height = 1;
  12.   }
  13. }
  14.  
  15. class AVLTree {
  16.   /**
  17.    * 构造函数
  18.    *
  19.    * @returns 无返回值
  20.    */
  21.   constructor() {
  22.     this.root = null;
  23.   }
  24.  
  25.   /**
  26.    * 获取节点高度
  27.    *
  28.    * @param node 节点对象
  29.    * @returns 返回节点高度，如果节点不存在则返回0
  30.    */
  31.   getHeight(node) {
  32.     // 如果节点存在，则返回节点的高度，否则返回0
  33.     return node ? node.height : 0;
  34.   }
  35.  
  36.   /**
  37.    * 获取节点的平衡因子
  38.    *
  39.    * @param node 节点对象
  40.    * @returns 返回节点的平衡因子，若节点为空则返回0
  41.    */
  42.   getBalanceFactor(node) {
  43.     // 如果节点存在，则返回节点的高度，否则返回0
  44.     return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  45.   }
  46.  
  47.   /**
  48.    * 更新节点高度
  49.    *
  50.    * @param node 节点对象
  51.    */
  52.   updateHeight(node) {
  53.     // 更新节点的高度为左子树和右子树中较高的高度加1
  54.     node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
  55.   }
  56.  
  57.   /**
  58.    * 将节点y进行右旋操作
  59.    *
  60.    * @param y 要进行右旋操作的节点
  61.    * @returns 返回旋转后的新根节点
  62.    */
  63.   rotateRight(y) {
  64.     // 将y的左子节点赋值给x
  65.     let x = y.left;
  66.     // 将x的右子节点赋值给T2
  67.     let T2 = x.right;
  68.  
  69.     // 将y赋值给x的右子节点
  70.     x.right = y;
  71.     // 将T2赋值给y的左子节点
  72.     y.left = T2;
  73.  
  74.     // 更新y的高度
  75.     this.updateHeight(y);
  76.     // 更新x的高度
  77.     this.updateHeight(x);
  78.  
  79.     // 返回x
  80.     return x;
  81.   }
  82.  
  83.   /**
  84.    * 左旋操作
  85.    *
  86.    * @param x 待旋转的节点
  87.    * @returns 返回旋转后的新根节点
  88.    */
  89.   rotateLeft(x) {
  90.     // 将节点x的右子节点赋值给y
  91.     let y = x.right;
  92.     // 将节点y的左子节点赋值给T2
  93.     let T2 = y.left;
  94.  
  95.     // 将节点x赋值给节点y的左子节点
  96.     y.left = x;
  97.     // 将T2赋值给节点x的右子节点
  98.     x.right = T2;
  99.  
  100.     // 更新节点x的高度
  101.     this.updateHeight(x);
  102.     // 更新节点y的高度
  103.     this.updateHeight(y);
  104.  
  105.     // 返回旋转后的新根节点y
  106.     return y;
  107.   }
  108.  
  109.   /**
  110.    * 向AVL树中插入节点
  111.    *
  112.    * @param node 当前节点
  113.    * @param key 待插入节点的键值
  114.    * @returns 返回插入后的节点
  115.    */
  116.   insert(node, key) {
  117.     // 如果节点为空，则创建一个新的节点并返回
  118.     if (!node) {
  119.       return new AVLNode(key);
  120.     }
  121.  
  122.     // 如果插入的键小于节点的键，则在左子树中插入
  123.     if (key < node.key) {
  124.       node.left = this.insert(node.left, key);
  125.     }
  126.     // 如果插入的键大于节点的键，则在右子树中插入
  127.     else if (key > node.key) {
  128.       node.right = this.insert(node.right, key);
  129.     }
  130.     // 如果插入的键等于节点的键，则直接返回该节点
  131.     else {
  132.       return node;
  133.     }
  134.  
  135.     // 更新节点的高度
  136.     this.updateHeight(node);
  137.  
  138.     // 获取节点的平衡因子
  139.     let balance = this.getBalanceFactor(node);
  140.  
  141.     // 左左情况：左子树高度大于右子树高度2及以上，且插入的键小于左子树的最小键
  142.     // 右旋
  143.     // 左左情况
  144.     if (balance > 1 && key < node.left.key) {
  145.       return this.rotateRight(node);
  146.     }
  147.  
  148.     // 右右情况：右子树高度大于左子树高度2及以上，且插入的键大于右子树的最大键
  149.     // 左旋
  150.     // 右右情况
  151.     if (balance < -1 && key > node.right.key) {
  152.       return this.rotateLeft(node);
  153.     }
  154.  
  155.     // 左右情况：左子树高度大于右子树高度2及以上，且插入的键大于左子树的最小键
  156.     // 先左旋，再右旋
  157.     // 左右情况
  158.     if (balance > 1 && key > node.left.key) {
  159.       node.left = this.rotateLeft(node.left);
  160.       return this.rotateRight(node);
  161.     }
  162.  
  163.     // 右左情况：右子树高度大于左子树高度2及以上，且插入的键小于右子树的最大键
  164.     // 先右旋，再左旋
  165.     // 右左情况
  166.     if (balance < -1 && key < node.right.key) {
  167.       node.right = this.rotateRight(node.right);
  168.       return this.rotateLeft(node);
  169.     }
  170.  
  171.     // 返回插入后的节点
  172.     return node;
  173.   }
  174. }
  175.  
  176. // 示例
  177. const avlTree = new AVLTree();
  178. avlTree.root = avlTree.insert(avlTree.root, 10);
  179. avlTree.root = avlTree.insert(avlTree.root, 20);
  180. avlTree.root = avlTree.insert(avlTree.root, 30);
  181. console.log(avlTree.root); // AVLNode { key: 20, left: AVLNode { key: 10, ... }, right: AVLNode { key: 30, ... }, ... }

红黑树

红黑树是一种近似平衡的二叉搜索树，它通过一些附加的约束条件来保持树的大致平衡。红黑树的节点可以是红色或黑色，它要求在插入或删除操作后，树的黑色高度相同。红黑树通过颜色变换和旋转操作来调整树的结构，以满足约束条件。红黑树相对于AVL树来说，旋转操作更少，插入和删除操作更快，但是查询操作略慢一些。

代码示例：

  1. const RED = 'red';
  2. const BLACK = 'black';
  3.  
  4. class RedBlackNode {
  5.   /**
  6.    * 构造函数，用于创建一个节点对象
  7.    *
  8.    * @param key 节点的键值
  9.    * @param color 节点的颜色
  10.    */
  11.   constructor(key, color) {
  12.     this.key = key; // 设置当前节点的键值
  13.     this.left = null; // 初始化左子节点为 null
  14.     this.right = null;// 初始化右子节点为 null
  15.     this.parent = null; // 初始化父节点为 null
  16.     this.color = color;// 设置当前节点的颜色
  17.   }
  18. }
  19.  
  20. class RedBlackTree {
  21.   /**
  22.    * 构造函数
  23.    */
  24.   constructor() {
  25.     // 初始化根节点为null
  26.     this.root = null;
  27.   }
  28.  
  29.   /**
  30.     * 将二叉树节点左旋转
  31.     *
  32.     * @param node 需要左旋转的节点
  33.     */
  34.   rotateLeft(node) {
  35.     // 获取当前节点的右子节点
  36.     let rightChild = node.right;
  37.     // 将当前节点的右子节点的左子节点赋值给当前节点的右子节点
  38.     node.right = rightChild.left;
  39.     // 如果当前节点的右子节点的左子节点不为空
  40.     if (rightChild.left !== null) {
  41.       // 将当前节点的右子节点的左子节点的父节点指向当前节点
  42.       rightChild.left.parent = node;
  43.     }
  44.  
  45.     // 将当前节点的右子节点的父节点指向当前节点的父节点
  46.     rightChild.parent = node.parent;
  47.  
  48.     // 如果当前节点的父节点为空
  49.     if (node.parent === null) {
  50.       // 将当前节点的右子节点设置为根节点
  51.       this.root = rightChild;
  52.       // 如果当前节点是其父节点的左子节点
  53.     } else if (node === node.parent.left) {
  54.       // 将当前节点的父节点的左子节点设置为当前节点的右子节点
  55.       node.parent.left = rightChild;
  56.       // 如果当前节点是其父节点的右子节点
  57.     } else {
  58.       // 将当前节点的父节点的右子节点设置为当前节点的右子节点
  59.       node.parent.right = rightChild;
  60.     }
  61.  
  62.     // 将当前节点的右子节点的左子节点设置为当前节点
  63.     rightChild.left = node;
  64.     // 将当前节点的父节点设置为当前节点的右子节点
  65.     node.parent = rightChild;
  66.   }
  67.  
  68.   /**
  69.    * 将节点右旋
  70.    *
  71.    * @param node 要旋转的节点
  72.    */
  73.   rotateRight(node) {
  74.     // 获取当前节点的左子节点
  75.     let leftChild = node.left;
  76.     // 将当前节点的左子节点指向左子节点的右子节点
  77.     node.left = leftChild.right;
  78.     // 如果左子节点的右子节点不为空
  79.     if (leftChild.right !== null) {
  80.       // 将左子节点的右子节点的父节点指向当前节点
  81.       leftChild.right.parent = node;
  82.     }
  83.     // 将左子节点的父节点指向当前节点的父节点
  84.     leftChild.parent = node.parent;
  85.     // 如果当前节点的父节点为空
  86.     if (node.parent === null) {
  87.       // 将根节点指向左子节点
  88.       this.root = leftChild;
  89.       // 如果当前节点是父节点的右子节点
  90.     } else if (node === node.parent.right) {
  91.       // 将父节点的右子节点指向左子节点
  92.       node.parent.right = leftChild;
  93.       // 否则
  94.     } else {
  95.       // 将父节点的左子节点指向左子节点
  96.       node.parent.left = leftChild;
  97.     }
  98.     // 将左子节点的右子节点指向当前节点
  99.     leftChild.right = node;
  100.     // 将当前节点的父节点指向左子节点
  101.     node.parent = leftChild;
  102.   }
  103.  
  104.   /**
  105.    * 插入节点
  106.    *
  107.    * @param key 节点值
  108.    */
  109.   insert(key) {
  110.     // 创建一个新的红黑树节点，颜色为红色
  111.     let newNode = new RedBlackNode(key, RED);
  112.  
  113.     // 将新节点插入到红黑树中，并返回更新后的根节点
  114.     this.root = this.insertNode(this.root, newNode);
  115.  
  116.     // 修复红黑树的性质
  117.     this.fixTreeProperties(newNode);
  118.   }
  119.  
  120.   /**
  121.    * 在二叉搜索树中插入节点
  122.    *
  123.    * @param root 二叉搜索树的根节点
  124.    * @param node 要插入的节点
  125.    * @returns 返回插入节点后的二叉搜索树的根节点
  126.    */
  127.   insertNode(root, node) {
  128.     // 如果根节点为空，直接返回新节点作为根节点
  129.     if (root === null) {
  130.       return node;
  131.     }
  132.     // 如果新节点的键值小于根节点的键值，则递归地将新节点插入到左子树中
  133.     if (node.key < root.key) {
  134.       root.left = this.insertNode(root.left, node);
  135.       // 将新节点的父节点设置为当前根节点
  136.       root.left.parent = root;
  137.       // 如果新节点的键值大于根节点的键值，则递归地将新节点插入到右子树中
  138.     } else if (node.key > root.key) {
  139.       root.right = this.insertNode(root.right, node);
  140.       // 将新节点的父节点设置为当前根节点
  141.       root.right.parent = root;
  142.     }
  143.  
  144.     // 返回根节点
  145.     return root;
  146.   }
  147.  
  148.   /**
  149.    * 修复树属性
  150.    *
  151.    * @param node 当前节点
  152.    */
  153.   fixTreeProperties(node) {
  154.     // 当当前节点不是根节点且其父节点颜色为红色时，执行循环
  155.     while (node !== this.root && node.parent.color === RED) {
  156.       // 获取当前节点的父节点和祖父节点
  157.       let parentNode = node.parent;
  158.       let grandParentNode = node.parent.parent;
  159.  
  160.       // 如果父节点是祖父节点的左子节点
  161.       if (parentNode === grandParentNode.left) {
  162.         // 获取叔叔节点
  163.         let uncleNode = grandParentNode.right;
  164.  
  165.         // 如果叔叔节点不为空且颜色为红色
  166.         if (uncleNode !== null && uncleNode.color === RED) {
  167.           // 将祖父节点颜色设为红色
  168.           grandParentNode.color = RED;
  169.           // 将父节点颜色设为黑色
  170.           parentNode.color = BLACK;
  171.           // 将叔叔节点颜色设为黑色
  172.           uncleNode.color = BLACK;
  173.           // 将当前节点更新为祖父节点，继续下一轮循环
  174.           node = grandParentNode;
  175.         } else {
  176.           // 如果当前节点是父节点的右子节点
  177.           if (node === parentNode.right) {
  178.             // 执行左旋操作
  179.             this.rotateLeft(parentNode);
  180.             // 将当前节点更新为父节点
  181.             node = parentNode;
  182.             // 更新父节点为当前节点的父节点
  183.             parentNode = node.parent;
  184.           }
  185.           // 执行右旋操作
  186.           this.rotateRight(grandParentNode);
  187.           // 交换父节点和祖父节点的颜色
  188.           [parentNode.color, grandParentNode.color] = [grandParentNode.color, parentNode.color];
  189.           // 将当前节点更新为父节点，继续下一轮循环
  190.           node = parentNode;
  191.         }
  192.       } else {
  193.         // 如果父节点是祖父节点的右子节点
  194.         // 获取叔叔节点
  195.         let uncleNode = grandParentNode.left;
  196.  
  197.         // 如果叔叔节点不为空且颜色为红色
  198.         if (uncleNode !== null && uncleNode.color === RED) {
  199.           // 将祖父节点颜色设为红色
  200.           grandParentNode.color = RED;
  201.           // 将父节点颜色设为黑色
  202.           parentNode.color = BLACK;
  203.           // 将叔叔节点颜色设为黑色
  204.           uncleNode.color = BLACK;
  205.           // 将当前节点更新为祖父节点，继续下一轮循环
  206.           node = grandParentNode;
  207.         } else {
  208.           // 如果当前节点是父节点的左子节点
  209.           if (node === parentNode.left) {
  210.             // 执行右旋操作
  211.             this.rotateRight(parentNode);
  212.             // 将当前节点更新为父节点
  213.             node = parentNode;
  214.             // 更新父节点为当前节点的父节点
  215.             parentNode = node.parent;
  216.           }
  217.           // 执行左旋操作
  218.           this.rotateLeft(grandParentNode);
  219.           // 交换父节点和祖父节点的颜色
  220.           [parentNode.color, grandParentNode.color] = [grandParentNode.color, parentNode.color];
  221.           // 将当前节点更新为父节点，继续下一轮循环
  222.           node = parentNode;
  223.         }
  224.       }
  225.     }
  226.     // 将根节点颜色设为黑色
  227.     this.root.color = BLACK;
  228.   }
  229. }
  230.  
  231. // 示例
  232. const rbTree = new RedBlackTree();
  233. rbTree.insert(10);
  234. rbTree.insert(20);
  235. rbTree.insert(30);
  236. console.log(rbTree.root); // RedBlackNode { key: 20, color: 'black', ... }

B树

B树是一种多路搜索树，它的每个节点可以存储多个关键字，并且可以有多个子节点。B树的节点拥有较大的容量，使得每个节点的关键字数量相对较少，这样可以降低树的高度，提高查询效率。B树常用于文件系统和数据库中，用于索引大量数据的情况。

代码示例：

  1. class BTreeNode {
  2.   /**
  3.    * 构造函数
  4.    *
  5.    * @param leaf 是否为叶子节点，默认为false
  6.    */
  7.   constructor(leaf = false) {
  8.     this.keys = [];
  9.     this.children = [];
  10.     this.leaf = leaf;
  11.   }
  12. }
  13.  
  14. class BTree {
  15.   /**
  16.    * 构造函数
  17.    *
  18.    * @param degree 树的度数
  19.    */
  20.   constructor(degree) {
  21.     this.root = null;
  22.     this.degree = degree;
  23.   }
  24.  
  25.   /**
  26.    * 搜索指定节点
  27.    *
  28.    * @param key 要搜索的节点值
  29.    * @returns 返回与key值相等的节点
  30.    */
  31.   search(key) {
  32.     // 调用 searchNode 方法，传入根节点和关键字进行搜索
  33.     return this.searchNode(this.root, key);
  34.   }
  35.  
  36.   /**
  37.    * 在 B-tree 节点中查找给定的键值，并返回该键值所在的节点
  38.    *
  39.    * @param node B-tree 节点
  40.    * @param key 要查找的键值
  41.    * @returns 返回找到的节点，如果未找到则返回 null
  42.    */
  43.   searchNode(node, key) {
  44.     let i = 0;
  45.  
  46.     // 遍历节点的 keys 数组，查找 key 所在的索引位置
  47.     while (i < node.keys.length && key > node.keys[i]) {
  48.       i++;
  49.     }
  50.  
  51.     // 如果找到了 key，并且 key 等于当前索引位置的元素，则返回当前节点
  52.     if (i < node.keys.length && key === node.keys[i]) {
  53.       return node;
  54.       // 如果当前节点是叶子节点，则返回 null
  55.     } else if (node.leaf) {
  56.       return null;
  57.       // 否则，在子节点中继续搜索 key
  58.     } else {
  59.       return this.searchNode(node.children[i], key);
  60.     }
  61.   }
  62.  
  63.   /**
  64.    * 向B树中插入一个键值
  65.    *
  66.    * @param key 要插入的键值
  67.    */
  68.   insert(key) {
  69.     // 如果根节点不存在
  70.     if (!this.root) {
  71.       // 创建一个新的B树节点作为根节点，并且标记为叶子节点
  72.       this.root = new BTreeNode(true);
  73.       // 将传入的键值添加到根节点的键值数组中
  74.       this.root.keys.push(key);
  75.     } else {
  76.       // 如果根节点的键值数组已满（达到2倍的度数减1）
  77.       if (this.root.keys.length === (2 * this.degree) - 1) {
  78.         // 创建一个新的B树节点作为新的根节点，并且标记为非叶子节点
  79.         let newRoot = new BTreeNode(false);
  80.         // 将原来的根节点添加到新根节点的子节点数组中
  81.         newRoot.children.push(this.root);
  82.         // 调用splitChild方法拆分子节点
  83.         this.splitChild(newRoot, 0, this.root);
  84.         // 更新根节点为新创建的节点
  85.         this.root = newRoot;
  86.       }
  87.       // 在非满的节点中插入键值
  88.       this.insertNonFull(this.root, key);
  89.     }
  90.   }
  91.  
  92.   /**
  93.    * 在非满节点中插入键值对
  94.    *
  95.    * @param node 节点对象
  96.    * @param key 待插入的键
  97.    */
  98.   insertNonFull(node, key) {
  99.     // 获取节点中键的最后一个索引
  100.     let i = node.keys.length - 1;
  101.  
  102.     // 如果节点是叶子节点
  103.     if (node.leaf) {
  104.       // 当索引大于等于0且key小于当前索引对应的键时，索引减1
  105.       while (i >= 0 && key < node.keys[i]) {
  106.         i--;
  107.       }
  108.       // 在索引i+1的位置插入key
  109.       node.keys.splice(i + 1, 0, key);
  110.     } else {
  111.       // 当索引大于等于0且key小于当前索引对应的键时，索引减1
  112.       while (i >= 0 && key < node.keys[i]) {
  113.         i--;
  114.       }
  115.       // 索引加1
  116.       i++;
  117.       // 如果当前索引对应的子节点的键的数量等于(2 * this.degree) - 1
  118.       if (node.children[i].keys.length === (2 * this.degree) - 1) {
  119.         // 调用splitChild方法拆分子节点
  120.         this.splitChild(node, i, node.children[i]);
  121.         // 如果key大于当前索引对应的键
  122.         if (key > node.keys[i]) {
  123.           // 索引加1
  124.           i++;
  125.         }
  126.       }
  127.       // 递归调用insertNonFull方法，将key插入到当前索引对应的子节点中
  128.       this.insertNonFull(node.children[i], key);
  129.     }
  130.   }
  131.  
  132.   /**
  133.    * 将子节点拆分为两个节点，并将拆分后的新节点插入到父节点中
  134.    *
  135.    * @param parent 父节点
  136.    * @param index 父节点中子节点的索引
  137.    * @param child 要拆分的子节点
  138.    */
  139.   splitChild(parent, index, child) {
  140.     // 创建一个新的B树节点，叶子节点状态与child相同
  141.     let newChild = new BTreeNode(child.leaf);
  142.     // 计算中间索引位置
  143.     let midIndex = Math.floor(this.degree - 1);
  144.  
  145.     // 将child节点的keys数组从中间索引位置后的部分赋值给newChild的keys数组
  146.     newChild.keys = child.keys.splice(midIndex + 1);
  147.     // 如果child节点不是叶子节点
  148.     if (!child.leaf) {
  149.       // 将child节点的children数组从中间索引位置后的部分赋值给newChild的children数组
  150.       newChild.children = child.children.splice(midIndex + 1);
  151.     }
  152.  
  153.     // 将child节点的keys数组中间索引位置的元素插入到parent节点的keys数组的指定位置
  154.     parent.keys.splice(index, 0, child.keys[midIndex]);
  155.     // 将newChild节点插入到parent节点的children数组的指定位置
  156.     parent.children.splice(index + 1, 0, newChild);
  157.   }
  158. }
  159.  
  160. // 示例
  161. const bTree = new BTree(2);
  162. bTree.insert(10);
  163. bTree.insert(20);
  164. bTree.insert(5);
  165. console.log(bTree.search(10)); // BTreeNode { keys: [ 10 ], children: [], leaf: true }
  166. console.log(bTree.search(15)); // null

B+树

B+树是B树的一种变体，它与B树的区别在于B+树的非叶子节点不存储关键字的值，只存储关键字和指向子节点的指针。所有的叶子节点按顺序连接起来，形成一个有序链表，方便范围查询。B+树适用于数据库索引等需要范围查询的场景。

代码示例：

  1. class BPlusTreeNode {
  2.   /**
  3.    * 构造函数
  4.    */
  5.   constructor() {
  6.     this.keys = [];
  7.     this.children = [];
  8.   }
  9. }
  10.  
  11. class BPlusTree {
  12.   /**
  13.    * 构造函数
  14.    *
  15.    * @param degree 树的度数
  16.    */
  17.   constructor(degree) {
  18.     this.root = null;
  19.     this.degree = degree;
  20.   }
  21.  
  22.   /**
  23.    * 搜索指定关键字
  24.    *
  25.    * @param key 关键字
  26.    * @returns 返回搜索到的节点，若未找到则返回null
  27.    */
  28.   search(key) {
  29.     // 调用 searchNode 方法进行搜索
  30.     return this.searchNode(this.root, key);
  31.   }
  32.  
  33.   /**
  34.    * 在树中搜索节点
  35.    *
  36.    * @param node 当前节点
  37.    * @param key 待搜索的键
  38.    * @returns 返回找到的节点，若未找到则返回null
  39.    */
  40.   searchNode(node, key) {
  41.     // 如果节点为空，则返回null
  42.     if (!node) return null;
  43.     // 初始化索引i为0
  44.     let i = 0;
  45.  
  46.     // 循环遍历节点的keys数组，直到找到key应该插入的位置
  47.     while (i < node.keys.length && key >= node.keys[i]) {
  48.       i++;
  49.     }
  50.     // 如果节点没有子节点，则返回当前节点
  51.     if (node.children.length === 0) {
  52.       return node;
  53.     }
  54.     // 递归调用searchNode方法，在子节点中继续搜索
  55.     return this.searchNode(node.children[i], key);
  56.   }
  57.  
  58.   /**
  59.    * 向B+树中插入键值
  60.    *
  61.    * @param key 键值
  62.    */
  63.   insert(key) {
  64.     // 如果根节点不存在
  65.     if (!this.root) {
  66.       // 创建一个新的根节点
  67.       this.root = new BPlusTreeNode();
  68.       // 将键值添加到根节点的键值数组中
  69.       this.root.keys.push(key);
  70.     } else {
  71.       // 如果根节点的键值数组已满
  72.       if (this.root.keys.length === (2 * this.degree) - 1) {
  73.         // 创建一个新的根节点
  74.         let newRoot = new BPlusTreeNode();
  75.         // 将原根节点添加到新根节点的子节点数组中
  76.         newRoot.children.push(this.root);
  77.         // 调用 splitChild 方法进行节点分裂
  78.         this.splitChild(newRoot, 0, this.root);
  79.         // 更新根节点为新创建的根节点
  80.         this.root = newRoot;
  81.       }
  82.       // 调用 insertNonFull 方法将键值插入到非满的节点中
  83.       this.insertNonFull(this.root, key);
  84.     }
  85.   }
  86.  
  87.   /**
  88.    * 在非满节点中插入一个键值对
  89.    *
  90.    * @param node 当前节点
  91.    * @param key 待插入的键
  92.    */
  93.   insertNonFull(node, key) {
  94.     // 获取节点最后一个键的索引
  95.     let i = node.keys.length - 1;
  96.     // 如果节点没有子节点
  97.     if (node.children.length === 0) {
  98.       // 当索引大于等于0且key小于当前索引对应的键时，索引减1
  99.       while (i >= 0 && key < node.keys[i]) {
  100.         i--;
  101.       }
  102.       // 在索引i+1的位置插入key
  103.       node.keys.splice(i + 1, 0, key);
  104.     } else {
  105.       // 当索引大于等于0且key小于当前索引对应的键时，索引减1
  106.       while (i >= 0 && key < node.keys[i]) {
  107.         i--;
  108.       }
  109.       // 索引加1，指向当前key应该插入的位置
  110.       i++;
  111.       // 如果当前子节点的键数量等于最大度减1
  112.       if (node.children[i].keys.length === (2 * this.degree) - 1) {
  113.         // 对当前子节点进行分裂
  114.         this.splitChild(node, i, node.children[i]);
  115.         // 如果key大于当前索引对应的键
  116.         if (key > node.keys[i]) {
  117.           // 索引加1，指向分裂后应该插入的位置
  118.           i++;
  119.         }
  120.       }
  121.       // 在指定子节点中递归插入key
  122.       this.insertNonFull(node.children[i], key);
  123.     }
  124.   }
  125.  
  126.   /**
  127.    * 将子节点从父节点中拆分，生成新的子节点并插入到父节点的子节点数组中
  128.    *
  129.    * @param parent 父节点
  130.    * @param index 父节点中子节点的索引
  131.    * @param child 要拆分的子节点
  132.    */
  133.   splitChild(parent, index, child) {
  134.     // 创建一个新的B+树节点
  135.     let newChild = new BPlusTreeNode();
  136.  
  137.     // 计算中间索引
  138.     let midIndex = Math.floor(this.degree - 1);
  139.  
  140.     // 将child节点的keys数组从midIndex+1处开始的部分赋值给newChild节点的keys
  141.     newChild.keys = child.keys.splice(midIndex + 1);
  142.  
  143.     // 如果child节点有子节点
  144.     if (child.children.length !== 0) {
  145.       // 将child节点的children数组从midIndex+1处开始的部分赋值给newChild节点的children
  146.       newChild.children = child.children.splice(midIndex + 1);
  147.     }
  148.  
  149.     // 将child节点的keys数组中midIndex位置的元素插入到parent节点的keys数组的index位置
  150.     parent.keys.splice(index, 0, child.keys[midIndex]);
  151.  
  152.     // 将newChild节点插入到parent节点的children数组的index+1位置
  153.     parent.children.splice(index + 1, 0, newChild);
  154.   }
  155. }
  156.  
  157. // 示例
  158. const bPlusTree = new BPlusTree(2);
  159. bPlusTree.insert(10);
  160. bPlusTree.insert(20);
  161. bPlusTree.insert(5);
  162. console.log(bPlusTree.search(10)); // BPlusTreeNode { keys: [ 10 ], children: [] }
  163. console.log(bPlusTree.search(15)); // BPlusTreeNode { keys: [ 10 ], children: [] }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/492207
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号