A self balancing binary search tree such as AVL tree can do faster lookup for a item in the tree in O(log n). Heap s mainly used implement priority queues which needs to find min/max elements quickly. Heap achieve this in O(1) time complexity.
![]() |
Min element of a BST is always at the left most |
![]() |
Cached pointer to Min element at the root |
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).
Lets look at the BST from slightly different angle. Usual declaration of BST in C as follows:

- (300, 200, 100, 50)
- (300, 400, 500, 600)
- (200, 250, 275)
- (100, 150)
- (400, 350)
- (500, 450)

AVL tree in Ace OS is implemented in this way. You can see the data structure declarations below. Initially we did it for reusing the code. But after implementing this we figured out some interesting properties. This balanced tree/graph can find any node in O(log(n)) and also offers findmin operation in O(1) complexity. This also reduces the complexity of delete operation(since we can find right node's left most child in O(1) operation). But delete operation might result in balancing the tree.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
typedef struct list LIST, * LIST_PTR; | |
struct list { | |
LIST_PTR next; | |
LIST_PTR prev; | |
}; | |
typedef struct binary_tree | |
{ | |
LIST left; | |
LIST right; | |
}BINARY_TREE; | |
typedef struct avl_tree | |
{ | |
int height; /*! height of the node*/ | |
BINARY_TREE bintree; /*! low level binary tree*/ | |
}AVL_TREE; |
0 comments:
Post a Comment