What is the difference between avl tree and binary search tree?
A binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps.
A binary search tree (BST) is a binary tree data structure which has the following properties:
->each node has a value;
->a total order is defined on these values;
->the left subtree of a node contains only values less than the node's value;
->the right subtree of a node contains only values greater than or equal to the node's value.
An AVL tree is a self-balancing binary search tree.
In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.
A regular Binary Search tree is not self balancing, meaning depending on the order of insertions you will get different time complexities.
For example;
In short;
Red Black Tree : best case O(logN), worst case O(logN)
Binary Search Tree: best case O(logN), worst case O(N)
A binary search tree (BST) is a binary tree data structure which has the following properties:
->each node has a value;
->a total order is defined on these values;
->the left subtree of a node contains only values less than the node's value;
->the right subtree of a node contains only values greater than or equal to the node's value.
An AVL tree is a self-balancing binary search tree.
In an AVL tree the heights of the two child subtrees of any node differ by at most one, therefore it is also called height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more tree rotations.
A regular Binary Search tree is not self balancing, meaning depending on the order of insertions you will get different time complexities.
For example;
- if you inserted in order {2, 3, 1}, the BST will be O( log(N) )
- however if you inserted {1,2,3}, the BST will be O( N ), like a linked list.
In short;
Red Black Tree : best case O(logN), worst case O(logN)
Binary Search Tree: best case O(logN), worst case O(N)
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment