This is the 26th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The AVL tree is a self-balanced binary search tree. The AVL tree is a self-balanced binary search tree.

This tree is not just any tree! Invented in 1962 by G. M. Adelson-Velsky and Evgenii Landis, the AVL tree was one of the first balanced binary tree implementations.

This article will continue to explore the basic principles of AVL tree.

Balanced Binary Search Trees with AVL in JavaScript

AVL rotation

In an AVL tree, adding and removing elements may require one or more tree rotations to rebalance the tree.

Therefore, the core operation of AVL tree is “AVL rotation”!

The following GIFs demonstrate continuous insertion of nodes into an AVL tree, including:

  • Left Rotation
  • Right Rotation
  • Right Left Rotation
  • Left-right Rotation
  • And the band tree’s Right Rotation with children.

Amway is an online dynamic demonstration of VAL tree rotation: www.cs.usfca.edu/~galles/vis… 👍 👍 👍

PNG indicated:

(Image: Wikipedia)

Operation cost analysis of AVL:

  1. Search cost: search efficiency is very good, the worst case is O(logN) order of magnitude;

  2. Insert price: AVL to ensure strict balance (| bf | < = 1), then every insert data makes some nodes in the AVL balance factor more than 1 rotation operation is a must. In fact, AVL requires at most one rotation (single or double) for each node insertion operation. Therefore, the overall cost of insert operations is still in the O(logN) level (insert nodes need to find the insert location first);

  3. Delete cost: Delete must check the balance factor of all nodes on the path from the delete node to the root node. So the cost of deletion is slightly higher. Each delete operation requires at most O(logN) rotations. Therefore, the time complexity of the deletion operation is O(logN)+O(logN)=O(2logN).

JS implementation

Left single screw:

function roateLeft(AvlNode) { var node = AvlNode.right; // Save the right child node avlnode. right = node.left; // The left child of the node is attached to the right child of the AvlNode. // AvlNode connects to node as its left child. Return node; // Return to node, connect to the original parent of AvlNode}Copy the code

Right single screw:

function roateRight(AvlNode) { var node = AvlNode.left; // Save the left child node avlnode. left = node.right; // Connect the right child of node to the left child of AvlNode. // AvlNode connects to node as its right child return node; // Return node to connect to AvlNode's original parent}Copy the code

Left-right double rotation:

function roateLeftRight(AvlNode) { AvlNode.right = roateLeft(AvlNode.right); Return roateRight(AvlNode); return roateRight(AvlNode); // do a single right turn}Copy the code

Right-left double rotation:

function roateRightLeft(AvlNode) { AvlNode.left = roateRight(AvlNode.left); Return roateLeft(AvlNode); // do left single turn}Copy the code

Function to get the height of the tree:

Function getAvlTreeHeight(node) {if (node == null) {return 0; } else { var leftHeight = getAvlTreeHeight(node.left); var rightHeight = getAvlTreeHeight(node.right); Return (leftHeight > rightHeight? leftHeight : rightHeight) + 1; }}Copy the code

Functions to implement a balanced tree:

function balance(node) { if (node == null) { return node; } if (getAvlTreeHeight(node.left) -getavlTreeheight (node.right) > 1) {if (getAvlTreeHeight(node.left) -getavlTreeheight (node.right) > 1) {if (getAvlTreeHeight(node.left.left) >= getAvlTreeHeight(node.left.right)) {// If the height of the left subtree is greater than or equal to the height of the right subtree // perform the right single-spin node = roateRight(node); } else {// Otherwise you need right-left double-rotation node = roateRightLeft(node); Else if (getAvlTreeHeight(node.right) -getavlTreeheight (node.left) > 1) {if (getAvlTreeHeight(node.right) -getavlTreeheight (node.left) > 1) {if (getAvlTreeHeight(node.right.right) >= getAvlTreeHeight(node.right.left)) {// If the height of the right subtree is greater than or equal to the height of the left subtree // the left single-spin node is performed directly = roateLeft(node); } else {roateLeftRight(node) = roateLeftRight; } } return node; }Copy the code

Each time a node is inserted, a tree balance is required:

var insertNode = function(node, newNode){ if (newNode.key < node.key){ if (node.left === null){ node.left = newNode; Node.left = balance(node.left); } else { insertNode(node.left, newNode); } } else { if (node.right === null){ node.right = newNode; Node.right = balance(node.right); } else { insertNode(node.right, newNode); }}}Copy the code

U1s1, when the trees started spinning, my head got a little dizzy

Chew not come down, collect first slowly chew bar ~~

Don’t panic, there will be more exercises on balancing binary trees, and red-black trees with minimal front-end contact…

OK, the above is the share ~ writing is not easy, like encourage 👍👍👍

I am Anthony Nuggets, the public account of the same name, every day a pawn, dig a gold, goodbye ~

Reference:

  • wikipedia
  • Self-balanced Binary Search Trees with AVL in JavaScript
  • Binary sorting tree, red black tree, AVL tree is the simplest understanding
  • Learn JavaScript data structures and algorithms – AVL trees