{"id":5,"date":"2013-05-11T11:59:00","date_gmt":"2013-05-11T18:59:00","guid":{"rendered":"http:\/\/samueldotj.com\/blog\/?p=5"},"modified":"2013-08-26T18:57:59","modified_gmt":"2013-08-27T01:57:59","slug":"self-balancing-tree-as-heap","status":"publish","type":"post","link":"http:\/\/samueldotj.com\/blog\/self-balancing-tree-as-heap\/","title":{"rendered":"Self Balancing Tree as Heap"},"content":{"rendered":"

Here is my thoughts about how to combine a Heap<\/a> and AVL tree<\/a> and get benefit of both them from a single data structure.<\/p>\n

A self balancing binary search tree<\/a> such as AVL tree<\/a> can do faster lookup for a item in the tree in O(log n).\u00a0Heap<\/a>s are mainly used to implement priority queues which needs to find min\/max elements quickly. Heap\u00a0achieves\u00a0this in O(1) time complexity.<\/p>\n

\"Balanced<\/a> Lets revisit a basic property of binary search tree – In a binary search tree min element is at the left most leaf position. Similarly in a BST max element is at the right most leaf position. So finding min\/max element in a BST is O(h) where h is the depth of the tree. If the BST is a balanced tree then O(h) is O(log n) in worst case(otherwise the worst case O(n), since we considering only balanced trees here lets ignore the unbalanced cases). The following diagram illustrates a basic property of the BST – min element is always on the left most node.<\/p>\n

\"Cached<\/a>

Cached pointer to Min element at the root<\/p><\/div> Using this basic property, min remove operation can be optimized. The first and simplest optimization comes to mind is store a pointer to min\/max elements. This caching will result in O(1) time complexity for finding min\/max elements. However this would increase the cost of node insert\/delete because the min\/max pointer has to be updated during insert and deletion. The cost of finding and deleting a min node is O(log(n)) which is same as if we havent had the cache pointers. The picture in the right shows\u00a0advantage\u00a0of having cached pointer to find a min element.\u00a0Obviously\u00a0this method cant be used for priority queues where find min\/delete operation is used together.<\/p>\n

In the above method the problem was the complexity finding next smallest element in the tree from min element is O(log n). So if we have pointer to next smallest element from all nodes then find and delete opearation would be of complexity O(1).<\/p>\n

Lets look at the BST from slightly different angle. Usual declaration of BST in C as follows:<\/p>\n

[c]
\nstruct binary_tree
\n{
\n struct binary_tree *left;
\n struct binary_tree *right;
\n};
\n[\/c]<\/p>\n

When we(me and\u00a0+Dilip Simha<\/a>)\u00a0were implementing ADT for AceOS we decided to\u00a0experiment BST in a different way. We saw tree as recursive lists rather than a recursive pointers. <\/p>\n

In the following picture you could see 6 lists(not counting sub-lists):
\n\"A<\/a><\/p>\n

    \n
  1. (300, 200, 100, 50)<\/li>\n
  2. (300, 400, 500, 600)<\/li>\n
  3. (200, 250, 275)<\/li>\n
  4. (100, 150)<\/li>\n
  5. (400, 350)<\/li>\n
  6. (500, 450)<\/li>\n<\/ol>\n

    Now consider this list is a doubly linked circular list. This is illustrated in the following figure. You may argue that this will make the BST to become cyclic directed graph. But for the sake of simplicity lets continue to call this as balanced BST. In the picture I left out few arrows to keep it cleaner.<\/p>\n

    \"Binary<\/a>

    Binary Search Tree with nodes having pointer to parent also<\/p><\/div>\n

    [c]
    \ntypedef struct list LIST, * LIST_PTR;
    \nstruct list {
    \n LIST_PTR next;
    \n LIST_PTR prev;
    \n};<\/p>\n

    typedef struct binary_tree
    \n{
    \n LIST left;
    \n LIST right;
    \n}BINARY_TREE;<\/p>\n

    typedef struct avl_tree
    \n{
    \n int height; \/*! height of the node*\/
    \n BINARY_TREE bintree; \/*! low level binary tree*\/
    \n}AVL_TREE;
    \n[\/c]<\/p>\n

    AVL tree in Ace OS \u00a0is implemented in this way. You can see the data structure declarations below.\u00a0Initially\u00a0we did it for reusing the code. But after implementing this we\u00a0figured out some interesting properties. This balanced tree\/graph can find any node in O(log(n)) and also offers findmin<\/strong> operation\u00a0in O(1) complexity. This also reduces the complexity of delete\u00a0operation(since we can find right node’s left most child in O(1) operation). But delete operation might result in balancing the tree.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Here is my thoughts about how to combine a Heap and AVL tree and get benefit of both them from a single data structure. A self balancing binary search tree such as AVL tree can do faster lookup for a item in the tree in O(log n).\u00a0Heaps are mainly used to implement priority queues which […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-5","post","type-post","status-publish","format-standard","hentry","category-ace"],"_links":{"self":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/5","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/comments?post=5"}],"version-history":[{"count":5,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/5\/revisions"}],"predecessor-version":[{"id":133,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/posts\/5\/revisions\/133"}],"wp:attachment":[{"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/media?parent=5"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/categories?post=5"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/samueldotj.com\/blog\/wp-json\/wp\/v2\/tags?post=5"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}