AVL Tree
Step-by-Step Animation
Animation Speed
Elaboration:
?
2. If the right subtree is not empty, the values of all nodes on the right subtree are greater than its rooted node
3. The heights of two children can not differ by more than one
2. Delete: Deleted a new node given a key - O(log(n))
3. Find: Find the node given a key - O(log(n))
4. Inorder Print: Print keys in ascending order - O(n)
6. Clear Tree: Clear the entire tree
2. Delete: Deleted a new node given a key - O(log(n))
3. Find: Find the node given a key - O(log(n))
4. Inorder Print: Print keys in ascending order - O(n)
6. Clear Tree: Clear the entire tree
AVL Tree: A self-balancing binary search tree. Find operation is exactly like the binary search tree(BST). Deletion and Insertion operations follow the same step as the BST. Subsequently, AVL tree potentially needs to perform rotation and update nodes' height. AVL tree has the following properties:
1. If the left subtree is not empty, the values of all nodes on the left subtree are less than its rooted node 2. If the right subtree is not empty, the values of all nodes on the right subtree are greater than its rooted node
3. The heights of two children can not differ by more than one
API explanation:
1. Insert: Insert a new node - O(log(n))2. Delete: Deleted a new node given a key - O(log(n))
3. Find: Find the node given a key - O(log(n))
4. Inorder Print: Print keys in ascending order - O(n)
6. Clear Tree: Clear the entire tree
AVL树定义：AVL树又名自平衡二叉查找树，它是一种特殊的二叉搜索树, 相对于数据极端情况下, 二叉搜索树会退化成为单链表, 它定义了旋转操作, 在平衡因子大于等于2时, AVL树会旋转来调整树的结构, 来重新满足平衡因子小于2。故而AVL树中的任意一个结点, 其平衡因子的绝对值小于2。（平衡因子：树中某结点其左子树的高度和右子树的高度之差）
API explanations:
1. Insert: Insert a new node - O(log(n))2. Delete: Deleted a new node given a key - O(log(n))
3. Find: Find the node given a key - O(log(n))
4. Inorder Print: Print keys in ascending order - O(n)
6. Clear Tree: Clear the entire tree