This project is the implementation of one of the data structures "AVL Tree".
If you are someone who is interested in data structures, trees, one of the first structures that come to your mind, are very important to us. For this reason, I implemented AVL trees in order to learn these structures better and to improve myself and I am sharing them with you.
In addition to other AVL Tree implementation, it also stores the movement of nodes in the stack.
Before examining the project, we need to know about AVL trees.
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree.
It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this video lecture for proof).
- Get a MinGW at HERE and Install
- Open file folder from command line
cd desktop/AVL-Tree-Data-Structures- Run Makefile for compile process
mingw32-make- Open bin folder from command line or file explorer
cd.. / for move back folder
cd bin
program.exe
Distributed under the GNU General Public License v3.0. See LICENSE for more information.
Twitter: twitter.com/fehmiisener
Mail: [email protected]
Project Link: AVL-Tree-Data-Structures