<
6AD6
script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"path":"src/data-structures/tree/avl-tree","repo":{"id":176854347,"defaultBranch":"master","name":"javascript-algorithms","ownerLogin":"nillswe","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-03-21T02:28:07.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/6744730?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1614227171.2437592","canEdit":false,"refType":"branch","currentOid":"2267642a3dc78e4f5db2ed017f4438839b26d492"},"tree":{"items":[{"name":"__test__","path":"src/data-structures/tree/avl-tree/__test__","contentType":"directory"},{"name":"AvlTree.js","path":"src/data-structures/tree/avl-tree/AvlTree.js","contentType":"file"},{"name":"README.md","path":"src/data-structures/tree/avl-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\"\u003eAVL Tree\u003c/h1\u003e\u003ca id=\"user-content-avl-tree\" class=\"anchor\" aria-label=\"Permalink: AVL Tree\" href=\"#avl-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\"\u003eIn computer science, an \u003cstrong\u003eAVL tree\u003c/strong\u003e (named after inventors\nAdelson-Velsky and Landis) is a self-balancing binary search\ntree. It was the first such data structure to be invented.\nIn an AVL tree, the heights of the two child subtrees of any\nnode differ by at most one; if at any time they differ by\nmore than one, rebalancing is done to restore this property.\nLookup, insertion, and deletion all take \u003ccode\u003eO(log n)\u003c/code\u003e time in\nboth the average and worst cases, where n is the number of\nnodes in the tree prior to the operation. Insertions and\ndeletions may require the tree to be rebalanced by one or\nmore tree rotations.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAnimation showing the insertion of several elements into an AVL\ntree. It includes left, right, left-right and right-left rotations.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/ae0c83f953471465bb6d1aee52f6da1c846dfca842ca1fbe85832502a333e0d7/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f662f66642f41564c5f547265655f4578616d706c652e676966\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/ae0c83f953471465bb6d1aee52f6da1c846dfca842ca1fbe85832502a333e0d7/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f662f66642f41564c5f547265655f4578616d706c652e676966\" alt=\"AVL Tree\" data-animated-image=\"\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/f/fd/AVL_Tree_Example.gif\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAVL tree with balance factors (green)\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/5db4aa217eecee87c3a7244c4c7c1bc7b11474b707c513aaad98205f5e553d07/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f612f61642f41564c2d747265652d7742616c616e63655f4b2e737667\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/5db4aa217eecee87c3a7244c4c7c1bc7b11474b707c513aaad98205f5e553d07/68747470733a2f2f75706c6f61642e77696b696d656469612e6f72672f77696b6970656469612f636f6d6d6f6e732f612f61642f41564c2d747265652d7742616c616e63655f4b2e737667\" alt=\"AVL Tree\" data-canonical-src=\"https://upload.wikimedia.org/wikipedia/commons/a/ad/AVL-tree-wBalance_K.svg\" 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\"\u003eAVL Tree Rotations\u003c/h3\u003e\u003ca id=\"user-content-avl-tree-rotations\" class=\"anchor\" aria-label=\"Permalink: AVL Tree Rotations\" href=\"#avl-tree-rotations\"\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\u003cstrong\u003eLeft-Left Rotation\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/a2d0ae09a9d058dc30a34a7a6fcdefa547d9460cbd1a5538c997d1f9da000465/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f4c4c253230526f746174696f6e2e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/a2d0ae09a9d058dc30a34a7a6fcdefa547d9460cbd1a5538c997d1f9da000465/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f4c4c253230526f746174696f6e2e706e67\" alt=\"Left-Left Rotation\" data-canonical-src=\"http://btechsmartclass.com/data_structures/ds_images/LL%20Rotation.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eRight-Right Rotation\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/cb4b59adf2ff1c405ce4cd1419e2cb0a9f1733df851032abbd72f3e8481eb5a4/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f5252253230526f746174696f6e2e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/cb4b59adf2ff1c405ce4cd1419e2cb0a9f1733df851032abbd72f3e8481eb5a4/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f5252253230526f746174696f6e2e706e67\" alt=\"Right-Right Rotation\" data-canonical-src=\"http://btechsmartclass.com/data_structures/ds_images/RR%20Rotation.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eLeft-Right Rotation\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/f06029ac9691bb6986f4b851420020977ce0fd8b5b5d03cb25889fb842ff05d1/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f4c52253230526f746174696f6e2e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/f06029ac9691bb6986f4b851420020977ce0fd8b5b5d03cb25889fb842ff05d1/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f4c52253230526f746174696f6e2e706e67\" alt=\"Left-Right Rotation\" data-canonical-src=\"http://btechsmartclass.com/data_structures/ds_images/LR%20Rotation.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eRight-Left Rotation\u003c/strong\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer nofollow\" href=\"https://camo.githubusercontent.com/3711f721b442839ac65b10ab2d8736a774b1d57e1fcf01c729c50e092b6938a8/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f524c253230526f746174696f6e2e706e67\"\u003e\u003cimg src=\"https://camo.githubusercontent.com/3711f721b442839ac65b10ab2d8736a774b1d57e1fcf01c729c50e092b6938a8/687474703a2f2f6274656368736d617274636c6173732e636f6d2f646174615f737472756374757265732f64735f696d616765732f524c253230526f746174696f6e2e706e67\" alt=\"Right-Right Rotation\" data-canonical-src=\"http://btechsmartclass.com/data_structures/ds_images/RL%20Rotation.png\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eReferences\u003c/h2\u003e\u003ca id=\"user-content-references\" class=\"anchor\" aria-label=\"Permalink: References\" href=\"#references\"\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\u003ca href=\"https://en.wikipedia.org/wiki/AVL_tree\" rel=\"nofollow\"\u003eWikipedia\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm\" rel=\"nofollow\"\u003eTutorials Point\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"http://btechsmartclass.com/data_structures/avl-trees.html\" rel=\"nofollow\"\u003eBTech\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.youtube.com/watch?v=rbg7Qf8GkQ4\u0026amp;list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8\u0026amp;index=12\u0026amp;\" rel=\"nofollow\"\u003eAVL Tree Insertion on YouTube\u003c/a\u003e\u003c/li\u003e\n\u003cli\u003e\u003ca href=\"https://www.cs.usfca.edu/~galles/visualization/AVLtree.html\" rel=\"nofollow\"\u003eAVL Tree Interactive Visualisations\u003c/a\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"AVL Tree","anchor":"avl-tree","htmlText":"AVL Tree"},{"level":3,"text":"AVL Tree Rotations","anchor":"avl-tree-rotations","htmlText":"AVL Tree Rotations"},{"level":2,"text":"References","anchor":"references","htmlText":"References"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fnillswe%2Fjavascript-algorithms%2Ftree%2Fmaster%2Fsrc%2Fdata-structures%2Ftree%2Favl-tree"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"src/data-structures/tree":{"items":[{"name":"__test__","path":"src/data-structures/tree/__test__","contentType":"directory"},{"name":"avl-tree","path":"src/data-structures/tree/avl-tree","contentType":"directory"},{"name":"binary-search-tree","path":"src/data-structures/tree/binary-search-tree","contentType":"directory"},{"name":"fenwick-tree","path":"src/data-structures/tree/fenwick-tree","contentType":"directory"},{"name":"red-black-tree","path":"src/data-structures/tree/red-black-tree","contentType":"directory"},{"name":"segment-tree","path":"src/data-structures/tree/segment-tree","contentType":"directory"},{"name":"BinaryTreeNode.js","path":"src/data-structures/tree/BinaryTreeNode.js","contentType":"file"},{"name":"README.md","path":"src/data-structures/tree/README.md","contentType":"file"},{"name":"README.zh-CN.md","path":"src/data-structures/tree/README.zh-CN.md","contentType":"file"}],"totalCount":9},"src/data-structures":{"items":[{"name":"bloom-filter","path":"src/data-structures/bloom-filter","contentType":"directory"},{"name":"disjoint-set","path":"src/data-structures/disjoint-set","contentType":"directory"},{"name":"doubly-linked-list","path":"src/data-structures/doubly-linked-list","contentType":"directory"},{"name":"graph","path":"src/data-structures/graph","contentType":"directory"},{"name":"hash-table","path":"src/data-structures/hash-table","contentType":"directory"},{"name":"heap","path":"src/data-structures/heap","contentType":"directory"},{"name":"linked-list","path":"src/data-structures/linked-list","contentType":"directory"},{"name":"priority-queue","path":"src/data-structures/priority-queue","contentType":"directory"},{"name":"queue","path":"src/data-structures/queue","contentType":"directory"},{"name":"stack","path":"src/data-structures/stack","contentType":"directory"},{"name":"tree","path":"src/data-structures/tree","contentType":"directory"},{"name":"trie","path":"src/data-structures/trie","contentType":"directory"}],"totalCount":12},"src":{"items":[{"name":"algorithms","path":"src/algorithms","contentType":"directory"},{"name":"data-structures","path":"src/data-structures","contentType":"directory"},{"name":"playground","path":"src/playground","contentType":"directory"},{"name":"utils","path":"src/utils","contentType":"directory"}],"totalCount":4},"":{"items":[{"name":"assets","path":"assets","contentType":"directory"},{"name":"src","path":"src","contentType":"directory"},{"name":".babelrc","path":".babelrc","contentType":"file"},{"name":".editorconfig","path":".editorconfig","contentType":"file"},{"name":".eslintrc","path":".eslintrc","contentType":"file"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".huskyrc.json","path":".huskyrc.json","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"CODE_OF_CONDUCT.md","path":"CODE_OF_CONDUCT.md","contentType":"file"},{"name":"CONTRIBUTING.md","path":"CONTRIBUTING.md","contentType":"file"},{"name":"LICENSE","path":"LICENSE","contentType":"file"},{"name":"README.es-ES.md","path":"README.es-ES.md","contentType":"file"},{"name":"README.fr-FR.md","path":"README.fr-FR.md","contentType":"file"},{"name":"README.ja-JP.md","path":"README.ja-JP.md","contentType":"file"},{"name":"README.ko-KR.md","path":"README.ko-KR.md","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"README.pl-PL.md","path":"README.pl-PL.md","contentType":"file"},{"name":"README.pt-BR.md","path":"README.pt-BR.md","contentType":"file"},{"name":"README.zh-CN.md","path":"README.zh-CN.md","contentType":"file"},{"name":"README.zh-TW.md","path":"README.zh-TW.md","contentType":"file"},{"name":"jest.config.js","path":"jest.config.js","contentType":"file"},{"name":"package-lock.json","path":"package-lock.json","contentType":"file"},{"name":"package.json","path":"package.json","contentType":"file"}],"totalCount":23}},"fileTreeProcessingTime":24.718615999999997,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/nillswe/javascript-algorithms/branches":{"post":"T0iEAFITULSEzS1vBtVhLO7FQG-bFyr76Kewa7eOK1qof1PVFXWCBTQ7jYeMVXW1sbSfvLPMbz2mNIfB8xt7yg"},"/nillswe/javascript-algorithms/branches/fetch_and_merge/master":{"post":"9ygTmw8MEoBYv59xs1xJxvcMzxXvJdVrCPTWmVm7yPcUOu3ml6G70c3mfPg9QmWZAU2WIRKEs66yoybqRindbg"},"/nillswe/javascript-algorithms/branches/fetch_and_merge/master?discard_changes=true":{"post":"oT8rmic-SF_MeFBvBSGFWbvh1GUKZzniZlPpid-tZjFCLdXnv5PhDlkhs-aLP6kGTaCNUffGXyfcBBn6wD9zqA"}}},"title":"javascript-algorithms/src/data-structures/tree/avl-tree at master · nillswe/javascript-algorithms","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-b84e9496fc59.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.