AVL Tree & B-Tree

AVL Tree 

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where {\displaystyle n}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.
AVL tree was made to simplify BST to make data gathering of one(AVL) easier than the other(BST) due to AVL nature to always having itself balanced.
The AVL Tree is considered balanced if the total height of the right child subtracted by the total height of the right child is either 1,0, or -1.

AVL Rotation

To balance itself, an AVL tree may perform the following four kinds of rotations −
  • Left rotation
  • Right rotation
  • Left-Right rotation
  • Right-Left rotation
The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand them one by one.

Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation −

Left Rotation
In our example, node A has become unbalanced as a node is inserted in the right subtree of A's right subtree. We perform the left rotation by making A the left-subtree of B.

Right Rotation
AVL tree may become unbalanced if a node is inserted in the left subtree of the left subtree. The tree then needs the right rotation.
Right Rotation
As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.

Left-Right Rotation
Double rotations are slightly complex versions of already explained versions of rotations. To understand them better, we should take note of each action performed while rotation. Let's first check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation followed by a right rotation.

javascript-algorithms/src/data-structures/tree/avl-tree at master ...

Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by a left rotation.
AVL Tree – Introduction to LL, RR, LR, RL rotations and its ...


Insertion

avlinsert1
avlinsert2-jpg



Komentar

Posting Komentar

Postingan populer dari blog ini

Binary Search Tree

Gambar
Binary Search Tree is a binary tree based on nodes that has a certain attribute such as that the left node is smaller than its parents' node that the right node will always be bigger than its parents' node that both nodes must also be binary search tree and therefore cannot contains duplicates Above is an example of a Binary Search Tree Binary search tree can perform several operations such as: Searching, By comparing its roots to its nodes a program can climb through the node of a Binary search tree and find a specific node. by checking each root, comparing it to what it searched for climbing down to find the right node. sample code for searching in BST insertion, an operation to input certain data unto the Binary search tree on a specific node in the tree. by creating a space pushing the node and creating a new node either in the middle, the end or the beginning.  sample code of insertion in BST Deletion, an Operation that removes a node
Baca selengkapnya

Summary

SUMMARY Linked-list single Linked List is a data structure consisting of nodes. which together form a sequence. In its most basic form, each node contains data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to the pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists. Stack: In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the
Baca selengkapnya