{"id":1127,"date":"2017-04-03T07:07:10","date_gmt":"2017-04-03T14:07:10","guid":{"rendered":"http:\/\/somethingk.com\/main\/?p=1127"},"modified":"2017-04-03T07:07:10","modified_gmt":"2017-04-03T14:07:10","slug":"simple-avl-tree-in-c","status":"publish","type":"post","link":"https:\/\/somethingk.com\/main\/simple-avl-tree-in-c\/","title":{"rendered":"Simple AVL Tree in C++"},"content":{"rendered":"<section id=\"text-4\" class=\"widget boka-widget widget_text amr_widget\">\t\t\t<div class=\"textwidget\"><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script>\r\n<ins class=\"adsbygoogle\"\r\n     style=\"display:block; text-align:center;\"\r\n     data-ad-layout=\"in-article\"\r\n     data-ad-format=\"fluid\"\r\n     data-ad-client=\"ca-pub-7619916617995509\"\r\n     data-ad-slot=\"9102150708\"><\/ins>\r\n<script>\r\n     (adsbygoogle = window.adsbygoogle || []).push({});\r\n<\/script><\/div>\n\t\t<\/section>\n<p>An AVL tree is a binary search tree(BST)\u00a0however, unlike binary search trees, an AVL tree (named after\u00a0<a title=\"Georgy Adelson-Velsky\" href=\"https:\/\/en.wikipedia.org\/wiki\/Georgy_Adelson-Velsky\">Georgy Adelson-Velsky<\/a> and <a title=\"Evgenii Landis\" href=\"https:\/\/en.wikipedia.org\/wiki\/Evgenii_Landis\">Evgenii Landis<\/a>) is self balancing. So no matter how many nodes you insert into the tree, it will adjust it&#8217;s branches and ensure the tree is balanced at all times. Making sure the subtree heights only differ by at most 1. BSTs are great for segregating and storing data with a O(log n) search time. Downside with BST is that it can get weighted on one side and doesn&#8217;t have an restrictions to prevent it from getting skewed. By switching to an AVL, data is balanced in the tree and the search time is decreased to log n.<\/p>\n<p>So it is more efficient in most cases to use the AVL tree, below is an example of how to code this in C++. Note that the AVL tree uses a lot of the same code the BST did from this <a href=\"http:\/\/somethingk.com\/main\/?p=1075\">post<\/a>.<\/p>\n<div class=\"snippetcpt-wrap\" id=\"snippet-1129\" data-id=\"1129\" data-edit=\"\" data-copy=\"\/main\/wp-json\/wp\/v2\/posts\/1127?snippet=17b1fac833&#038;id=1129\" data-fullscreen=\"https:\/\/somethingk.com\/main\/code-snippets\/simple-avl-tree-in-c\/?full-screen=1\">\n\t\t\t\t<pre class=\"prettyprint linenums lang-c_cpp\" title=\"Simple AVL Tree in C++\">#pragma once\r\n\r\n#include &lt;iomanip&gt;\r\n#include &lt;iostream&gt;\r\n\r\nusing namespace std;\r\n\r\nclass AVL\r\n{\r\npublic:\r\n    AVL(){\r\n        root = nullptr;\r\n    }\r\n    ~AVL(){\r\n        destroy(root);\r\n    }\r\n    \r\n    \/\/My Node class for storing data, note how I add height\r\n    struct Node{\r\n        int data;\r\n        Node *left;\r\n        Node *right;\r\n        int height;\r\n\r\n        Node(int d){\r\n            data = d;\r\n            left = nullptr;\r\n            right = nullptr;\r\n            height = 0;\r\n        }\r\n\r\n        void updateHeight(){\r\n            int lHeight = 0;\r\n            int rHeight = 0;\r\n            if (left != nullptr) {\r\n                lHeight = left-&gt;height;\r\n            }\r\n            if (right != nullptr) {\r\n                rHeight = right-&gt;height;\r\n            }\r\n            int max = (lHeight &gt; rHeight) ? lHeight : rHeight;\r\n            height = max + 1;\r\n        }\r\n\r\n    };\r\n\r\n    void insert(int val){\r\n        insert(val, root);\r\n    }\r\n\r\n    \/\/Rotate a Node branch to the left, in order to balance things\r\n    Node* rotateLeft(Node *&amp;leaf){\r\n        Node* temp = leaf-&gt;right;\r\n        leaf-&gt;right = temp-&gt;left;\r\n        temp-&gt;left = leaf;\r\n\r\n        \/\/update the Nodes new height\r\n        leaf-&gt;updateHeight();\r\n\r\n        return temp;\r\n    }\r\n\r\n    \/\/Rotate a Node branch to the right, in order to balance things\r\n    Node* rotateRight(Node *&amp;leaf){\r\n        Node* temp = leaf-&gt;left;\r\n        leaf-&gt;left = temp-&gt;right;\r\n        temp-&gt;right = leaf;\r\n\r\n        \/\/update the Nodes new height\r\n        leaf-&gt;updateHeight();\r\n\r\n        return temp;\r\n    }\r\n\r\n    \/\/Rotate a Node branch to the right then the left, in order to balance things\r\n    Node* rotateRightLeft(Node *&amp;leaf){\r\n        Node* temp = leaf-&gt;right;\r\n        leaf-&gt;right = rotateRight(temp);\r\n        return rotateLeft(leaf);\r\n    }\r\n\r\n    \/\/Rotate a Node branch to the left then the right, in order to balance things\r\n    Node* rotateLeftRight(Node *&amp;leaf){\r\n        Node* temp = leaf-&gt;left;\r\n        leaf-&gt;left = rotateLeft(temp);\r\n        return rotateRight(leaf);\r\n    }\r\n\r\n    \/\/Function that checks each Node's left and right branches to determine if they are unbalanced\r\n    \/\/If they are, we rotate the branches\r\n    void rebalance(Node *&amp;leaf){\r\n        int hDiff = getDiff(leaf);\r\n        if (hDiff &gt; 1){\r\n            if (getDiff(leaf-&gt;left) &gt; 0) {\r\n                leaf = rotateRight(leaf);\r\n            } else {\r\n                leaf = rotateLeftRight(leaf);\r\n            }\r\n        } else if(hDiff &lt; -1) {\r\n            if (getDiff(leaf-&gt;right) &lt; 0) {\r\n                leaf = rotateLeft(leaf);\r\n            } else {\r\n                leaf = rotateRightLeft(leaf);\r\n            }\r\n        }\r\n    }\r\n\r\nprivate:\r\n    Node *root;\r\n    \/\/Insert a Node (very similar to BST, except we need to update Node height and then check for rebalance)\r\n    void insert(int d, Node *&amp;leaf){\r\n        if (leaf == nullptr){\r\n            leaf = new Node(d);\r\n            leaf-&gt;updateHeight();\r\n        }\r\n        else {\r\n            if (d &lt; leaf-&gt;data){\r\n                insert(d, leaf-&gt;left);\r\n                leaf-&gt;updateHeight();\r\n                rebalance(leaf);\r\n            }\r\n            else{\r\n                insert(d, leaf-&gt;right);\r\n                leaf-&gt;updateHeight();\r\n                rebalance(leaf);\r\n            }\r\n        }\r\n    }\r\n\r\n    \/\/Same as BST\r\n    void destroy(Node *&amp;leaf){\r\n        if (leaf != nullptr){\r\n            destroy(leaf-&gt;left);\r\n            destroy(leaf-&gt;right);\r\n            delete leaf;\r\n        }\r\n    }\r\n    \r\n    \/\/Get the difference between Node right and left branch heights, if it returns positive\r\n    \/\/We know the left side is greater, if negative, we know the right side is greater\r\n    int getDiff(Node *leaf){\r\n        int lHeight = 0;\r\n        int rHeight = 0;\r\n        if (leaf-&gt;left != nullptr) {\r\n            lHeight =  leaf-&gt;left-&gt;height;\r\n        }\r\n        if (leaf-&gt;right != nullptr) {\r\n            rHeight = leaf-&gt;right-&gt;height\r\n        }\r\n        return lHeight - rHeight;\r\n    }\r\n};<\/pre>\n\t\t\t<\/div>\n<p>Let me know if you have any issues!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>An AVL tree is a binary search tree(BST)\u00a0however, unlike binary search trees, an AVL tree (named after\u00a0Georgy Adelson-Velsky and Evgenii Landis) is self balancing. So no matter how many nodes you insert into the tree, it will adjust it&#8217;s branches and ensure the tree is balanced at all times. Making sure the subtree heights only differ by at most 1. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[177],"tags":[595,575,539,303,540,487,505,576],"class_list":["post-1127","post","type-post","status-publish","format-standard","hentry","category-development","tag-avl","tag-binary","tag-bst","tag-c","tag-class","tag-search","tag-simple","tag-tree"],"_links":{"self":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/comments?post=1127"}],"version-history":[{"count":2,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1127\/revisions"}],"predecessor-version":[{"id":1130,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/posts\/1127\/revisions\/1130"}],"wp:attachment":[{"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/media?parent=1127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/categories?post=1127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/somethingk.com\/main\/wp-json\/wp\/v2\/tags?post=1127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}