10000 swift-algorithm-club/B-Tree at master · alanzhangg/swift-algorithm-club · GitHub
[go: up one dir, main page]
Skip to content
{"payload":{"allShortcutsEnabled":false,"path":"B-Tree","repo":{"id":172218010,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"alanzhangg","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-02-23T13:32:49.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/4179267?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1617413853.784398","canEdit":false,"refType":"branch","currentOid":"deae79c2010d1e7341b24314819c9736cdfc4387"},"tree":{"items":[{"name":"BTree.playground","path":"B-Tree/BTree.playground","contentType":"directory"},{"name":"Images","path":"B-Tree/Images","contentType":"directory"},{"name":"Tests","path":"B-Tree/Tests","contentType":"directory"},{"name":"BTree.swift","path":"B-Tree/BTree.swift","contentType":"file"},{"name":"README.md","path":"B-Tree/README.md","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eB-Tree\u003c/h1\u003e\u003ca id=\"user-content-b-tree\" class=\"anchor\" aria-label=\"Permalink: B-Tree\" href=\"#b-tree\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eA B-Tree is a self-balancing search tree, in which nodes can have more than two children.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eProperties\u003c/h3\u003e\u003ca id=\"user-content-properties\" class=\"anchor\" aria-label=\"Permalink: Properties\" href=\"#properties\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eA B-Tree of order \u003cem\u003en\u003c/em\u003e satisfies the following properties:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eEvery node has at most \u003cem\u003e2n\u003c/em\u003e keys.\u003c/li\u003e\n\u003cli\u003eEvery node (except root) has at least \u003cem\u003en\u003c/em\u003e keys.\u003c/li\u003e\n\u003cli\u003eEvery non-leaf node with \u003cem\u003ek\u003c/em\u003e keys has \u003cem\u003ek+1\u003c/em\u003e children.\u003c/li\u003e\n\u003cli\u003eThe keys in all nodes are sorted in increasing order.\u003c/li\u003e\n\u003cli\u003eThe subtree between two keys \u003cem\u003ek\u003c/em\u003e and \u003cem\u003el\u003c/em\u003e of a non-leaf node contains all the keys between \u003cem\u003ek\u003c/em\u003e and \u003cem\u003el\u003c/em\u003e.\u003c/li\u003e\n\u003cli\u003eAll leaves appear at the same level.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eA second order B-Tree with keys from 1 to 20 looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/alanzhangg/swift-algorithm-club/blob/master/B-Tree/Images/BTree20.png\"\u003e\u003cimg src=\"/alanzhangg/swift-algorithm-club/raw/master/B-Tree/Images/BTree20.png\" alt=\"A B-Tree with 20 keys.\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe representation of a B-Tree node in code\u003c/h3\u003e\u003ca id=\"user-content-the-representation-of-a-b-tree-node-in-code\" class=\"anchor\" aria-label=\"Permalink: The representation of a B-Tree node in code\" href=\"#the-representation-of-a-b-tree-node-in-code\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"class BTreeNode\u0026lt;Key: Comparable, Value\u0026gt; {\n unowned var owner: BTree\u0026lt;Key, Value\u0026gt;\n \n fileprivate var keys = [Key]()\n var children: [BTreeNode]?\n \n ...\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eclass\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBTreeNode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003eKey\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eComparable\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e Value\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n unowned \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003eowner\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBTree\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eKey\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eValue\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e\n \n \u003cspan class=\"pl-k\"\u003efileprivate\u003c/span\u003e \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003ekeys\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eKey\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003e\u003cspan class=\"pl-c1\"\u003echildren\u003c/span\u003e\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eBTreeNode\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e\n \n \u003cspan class=\"pl-c1\"\u003e...\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe main parts of a node are two arrays:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eAn array containing the keys\u003c/li\u003e\n\u003cli\u003eAn array containing the children\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/alanzhangg/swift-algorithm-club/blob/master/B-Tree/Images/Node.png\"\u003e\u003cimg src=\"/alanzhangg/swift-algorithm-club/raw/master/B-Tree/Images/Node.png\" alt=\"Node.\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eNodes also have a reference to the tree they belong to.\u003cbr\u003e\nThis is necessary because nodes have to know the order of the tree.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eNote: The array containing the children is an Optional, because leaf nodes don't have children.\u003c/em\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSearching\u003c/h2\u003e\u003ca id=\"user-content-searching\" class=\"anchor\" aria-label=\"Permalink: Searching\" href=\"#searching\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eSearching for a key \u003ccode\u003ek\u003c/code\u003e begins at the root node.\u003c/li\u003e\n\u003cli\u003eWe perform a linear search on the keys of the node, until we find a key \u003ccode\u003el\u003c/code\u003e that is not less than \u003ccode\u003ek\u003c/code\u003e,\u003cbr\u003e\nor reach the end of the array.\u003c/li\u003e\n\u003cli\u003eIf \u003ccode\u003ek == l\u003c/code\u003e then we have found the key.\u003c/li\u003e\n\u003cli\u003eIf \u003ccode\u003ek \u0026lt; l\u003c/code\u003e:\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eIf the node we are on is not a leaf, then we go to the left child of \u003ccode\u003el\u003c/code\u003e, and perform the steps 3 - 5 again.\u003c/li\u003e\n\u003cli\u003eIf we are on a leaf, then \u003ccode\u003ek\u003c/code\u003e is not in the tree.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003cli\u003eIf we have reached the end of the array:\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eIf we are on a non-leaf node, then we go to the last child of the node, and perform the steps 3 - 5 again.\u003c/li\u003e\n\u003cli\u003eIf we are on a leaf, then \u003ccode\u003ek\u003c/code\u003e is not in the tree.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe code\u003c/h3\u003e\u003ca id=\"user-content-the-code\" class=\"anchor\" aria-label=\"Permalink: The code\" href=\"#the-code\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003evalue(for:)\u003c/code\u003e method searches for the given key and if it's in the tree,\u003cbr\u003e\nit returns the value associated with it, else it returns \u003ccode\u003enil\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eInsertion\u003c/h2\u003e\u003ca id=\"user-content-insertion\" class=\"anchor\" aria-label=\"Permalink: Insertion\" href=\"#insertion\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eKeys can only be inserted to leaf nodes.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003ePerform a search for the key \u003ccode\u003ek\u003c/code\u003e we want to insert.\u003c/li\u003e\n\u003cli\u003eIf we haven't found it and we are on a leaf node, we can insert it.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eIf after the search the key \u003ccode\u003el\u003c/code\u003e which we are standing on is greater than \u003ccode\u003ek\u003c/code\u003e:\u003cbr\u003e\nWe insert \u003ccode\u003ek\u003c/code\u003e to the position before \u003ccode\u003el\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eElse:\u003cbr\u003e\nWe insert \u003ccode\u003ek\u003c/code\u003e to the position after \u003ccode\u003el\u003c/code\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eAfter insertion we should check if the number of keys in the node is in the correct range.\u003cbr\u003e\nIf there are more keys in the node than \u003ccode\u003eorder*2\u003c/code\u003e, we need to split the node.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch4 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSplitting a node\u003c/h4\u003e\u003ca id=\"user-content-splitting-a-node\" class=\"anchor\" aria-label=\"Permalink: Splitting a node\" href=\"#splitting-a-node\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eMove up the middle key of the node we want to split, to its parent (if it has one).\u003c/li\u003e\n\u003cli\u003eIf it hasn't got a parent(it is the root), then create a new root and insert to it.\u003cbr\u003e\nAlso add the old root as the left child of the new root.\u003c/li\u003e\n\u003cli\u003eSplit the node into two by moving the keys (and children, if it's a non-leaf) that were after the middle key\nto a new node.\u003c/li\u003e\n\u003cli\u003eAdd the new node as a right child for the key that we have moved up.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eAfter splitting a node it is possible that the parent node will also contain too many keys, so we need to split it also.\u003cbr\u003e\nIn the worst case the splitting goes up to the root (in this case the height of the tree increases).\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAn insertion to a first order tree looks like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/alanzhangg/swift-algorithm-club/blob/master/B-Tree/Images/InsertionSplit.png\"\u003e\u003cimg src=\"/alanzhangg/swift-algorithm-club/raw/master/B-Tree/Images/InsertionSplit.png\" alt=\"Splitting\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe code\u003c/h3\u003e\u003ca id=\"user-content-the-code-1\" class=\"anchor\" aria-label=\"Permalink: The code\" href=\"#the-code-1\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe method \u003ccode\u003einsert(_:for:)\u003c/code\u003e does the insertion.\nAfter it has inserted a key, as the recursion goes up every node checks the number of keys in its child.\u003cbr\u003e\nif a node has too many keys, its parent calls the \u003ccode\u003esplit(child:atIndex:)\u003c/code\u003e method on it.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe root node is checked by the tree itself.\u003cbr\u003e\nIf the root has too many nodes after the insertion the tree calls the \u003ccode\u003esplitRoot()\u003c/code\u003e method.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eRemoval\u003c/h2\u003e\u003ca id=\"user-content-removal\" class=\"anchor\" aria-label=\"Permalink: Removal\" href=\"#removal\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eKeys can only be removed from leaf nodes.\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003ePerform a search for the key \u003ccode\u003ek\u003c/code\u003e we want to remove.\u003c/li\u003e\n\u003cli\u003eIf we have found it:\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eIf we are on a leaf node:\u003cbr\u003e\nWe can remove the key.\u003c/li\u003e\n\u003cli\u003eElse:\u003cbr\u003e\nWe overwrite \u003ccode\u003ek\u003c/code\u003e with its inorder predecessor \u003ccode\u003ep\u003c/code\u003e, then we remove \u003ccode\u003ep\u003c/code\u003e from the leaf node.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eAfter a key have been removed from a node we should check that the node has enough keys.\nIf a node has fewer keys than the order of the tree, then we should move a key to it,\u003cbr\u003e\nor merge it with one of its siblings.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch4 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eMoving a key to the child\u003c/h4\u003e\u003ca id=\"user-content-moving-a-key-to-the-child\" class=\"anchor\" aria-label=\"Permalink: Moving a key to the child\" href=\"#moving-a-key-to-the-child\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eIf the problematic node has a nearest sibling that has more keys than the order of the tree,\u003cbr\u003e\nwe should perform this operation on the tree, else we should merge the node with one of its siblings.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eLet's say the child we want to fix \u003ccode\u003ec1\u003c/code\u003e is at index \u003ccode\u003ei\u003c/code\u003e in its parent node's children array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf the child \u003ccode\u003ec2\u003c/code\u003e at index \u003ccode\u003ei-1\u003c/code\u003e has more keys than the order of the tree:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eWe move the key at index \u003ccode\u003ei-1\u003c/code\u003e from the parent node to the child \u003ccode\u003ec1\u003c/code\u003e's keys array at index \u003ccode\u003e0\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eWe move the last key from \u003ccode\u003ec2\u003c/code\u003e to the parent's keys array at index \u003ccode\u003ei-1\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e(If \u003ccode\u003ec1\u003c/code\u003e is non-leaf) We move the last child from \u003ccode\u003ec2\u003c/code\u003e to \u003ccode\u003ec1\u003c/code\u003e's children array at index 0.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eElse:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eWe move the key at index \u003ccode\u003ei\u003c/code\u003e from the parent node to the end of child \u003ccode\u003ec1\u003c/code\u003e's keys array.\u003c/li\u003e\n\u003cli\u003eWe move the first key from \u003ccode\u003ec2\u003c/code\u003e to the parent's keys array at index \u003ccode\u003ei\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e(If \u003ccode\u003ec1\u003c/code\u003e isn't a leaf) We move the first child from \u003ccode\u003ec2\u003c/code\u003e to the end of \u003ccode\u003ec1\u003c/code\u003e's children array.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/alanzhangg/swift-algorithm-club/blob/master/B-Tree/Images/MovingKey.png\"\u003e\u003cimg src=\"/alanzhangg/swift-algorithm-club/raw/master/B-Tree/Images/MovingKey.png\" alt=\"Moving Key\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch4 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eMerging two nodes\u003c/h4\u003e\u003ca id=\"user-content-merging-two-nodes\" class=\"anchor\" aria-label=\"Permalink: Merging two nodes\" href=\"#merging-two-nodes\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's say we want to merge the child \u003ccode\u003ec1\u003c/code\u003e at index \u003ccode\u003ei\u003c/code\u003e in its parent's children array.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf \u003ccode\u003ec1\u003c/code\u003e has a left sibling \u003ccode\u003ec2\u003c/code\u003e:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eWe move the key from the parent at index \u003ccode\u003ei-1\u003c/code\u003e to the end of \u003ccode\u003ec2\u003c/code\u003e's keys array.\u003c/li\u003e\n\u003cli\u003eWe move the keys and the children(if it's a non-leaf) from \u003ccode\u003ec1\u003c/code\u003e to the end of \u003ccode\u003ec2\u003c/code\u003e's keys and children array.\u003c/li\u003e\n\u003cli\u003eWe remove the child at index \u003ccode\u003ei-1\u003c/code\u003e from the parent node.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eElse if \u003ccode\u003ec1\u003c/code\u003e only has a right sibling \u003ccode\u003ec2\u003c/code\u003e:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eWe move the key from the parent at index \u003ccode\u003ei\u003c/code\u003e to the beginning of \u003ccode\u003ec2\u003c/code\u003e's keys array.\u003c/li\u003e\n\u003cli\u003eWe move the keys and the children(if it's a non-leaf) from \u003ccode\u003ec1\u003c/code\u003e to the beginning of \u003ccode\u003ec2\u003c/code\u003e's keys and children array.\u003c/li\u003e\n\u003cli\u003eWe remove the child at index \u003ccode\u003ei\u003c/code\u003e from the parent node.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp dir=\"auto\"\u003eAfter merging it is possible that now the parent node contains too few keys,\u003cbr\u003e\nso in the worst case merging also can go up to the root, in which case the height of the tree decreases.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/alanzhangg/swift-algorithm-club/blob/master/B-Tree/Images/MergingNodes.png\"\u003e\u003cimg src=\"/alanzhangg/swift-algorithm-club/raw/master/B-Tree/Images/MergingNodes.png\" alt=\"Merging Nodes\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eThe code\u003c/h3\u003e\u003ca id=\"user-content-the-code-2\" class=\"anchor\" aria-label=\"Permalink: The code\" href=\"#the-code-2\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003eremove(_:)\u003c/code\u003e method removes the given key from the tree. After a key has been deleted,\u003cbr\u003e\nevery node checks the number of keys in its child. If a child has less nodes than the order of the tree,\nit calls the \u003ccode\u003efix(childWithTooFewKeys:atIndex:)\u003c/code\u003e method.\u003c/p\u003e\n\u003c/li\u003e\n\u003cli\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003efix(childWithTooFewKeys:atIndex:)\u003c/code\u003e method decides which way to fix the child (by moving a key to it,\nor by merging it), then calls \u003ccode\u003emove(keyAtIndex:to:from:at:)\u003c/code\u003e or\n\u003ccode\u003emerge(child:atIndex:to:)\u003c/code\u003e method according to its choice.\u003c/p\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eSee also\u003c/h2\u003e\u003ca id=\"user-content-see-also\" class=\"anchor\" aria-label=\"Permalink: See also\" href=\"#see-also\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ca href=\"https://en.wikipedia.org/wiki/B-tree\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003cbr\u003e\n\u003ca href=\"http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/\" rel=\"nofollow\"\u003eGeeksforGeeks\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Viktor Szilárd Simkó\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"B-Tree","anchor":"b-tree","htmlText":"B-Tree"},{"level":3,"text":"Properties","anchor":"properties","htmlText":"Properties"},{"level":3,"text":"The representation of a B-Tree node in code","anchor":"the-representation-of-a-b-tree-node-in-code","htmlText":"The representation of a B-Tree node in code"},{"level":2,"text":"Searching","anchor":"searching","htmlText":"Searching"},{"level":3,"text":"The code","anchor":"the-code","htmlText":"The code"},{"level":2,"text":"Insertion","anchor":"insertion","htmlText":"Insertion"},{"level":4,"text":"Splitting a node","anchor":"splitting-a-node","htmlText":"Splitting a node"},{"level":3,"text":"The code","anchor":"the-code-1","htmlText":"The code"},{"level":2,"text":"Removal","anchor":"removal","htmlText":"Removal"},{"level":4,"text":"Moving a key to the child","anchor":"moving-a-key-to-the-child","htmlText":"Moving a key to the child"},{"level":4,"text":"Merging two nodes","anchor":"merging-two-nodes","htmlText":"Merging two nodes"},{"level":3,"text":"The code","anchor":"the-code-2","htmlText":"The code"},{"level":2,"text":"See also","anchor":"see-also","htmlText":"See also"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Falanzhangg%2Fswift-algorithm-club%2Ftree%2Fmaster%2FB-Tree"}},"totalCount":5,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":116}},"fileTreeProcessingTime":11.216198,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/alanzhangg/swift-algorithm-club/branches":{"post":"BtXLwJ5-8UEjO5LUcsATT42nKThKQbpDXAAj1TajbZTp3pYCgbd9xdQGjbN8ha50_Y801rzMqBjo0VJs5Pgq7A"},"/alanzhangg/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"sTQnDAekiK-oiEJIDD-w14NXLE5byoi7B6kVjoNx3KaU7_h_P4oge0sBPwj-N0U74Mec93efZuxlq6TxMbIrCA"},"/alanzhangg/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"_Y20MWsCWQVzoDgRqmSLhCjpGKEZZbGo5L917NtffkrYVmtCUyzx0ZApRVFYbH5oS3moGDUwX_-GvcSTaZyJ5A"}}},"title":"swift-algorithm-club/B-Tree at master · alanzhangg/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
0