How to resolve the algorithm AVL tree step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm AVL tree step by step in the J programming language

Table of Contents

Problem Statement

In computer science, 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; at no time do they differ by more than one because rebalancing is done ensure this is the case. 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. Note the tree of nodes comprise a set, so duplicate node keys are not allowed. AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.

Implement an AVL tree in the language of choice, and provide at least basic operations.

Red_black_tree_sort

Let's start with the solution:

Step by Step solution about How to resolve the algorithm AVL tree step by step in the J programming language

Source code in the j programming language

insert=: {{
  X=.1 {::2{.x,x  NB. middle element of x (don't fail on empty x)
  Y=.1 {::2{.y,y  NB. middle element of y (don't fail on empty y)
  select.#y
    case.0 do.x   NB. y is an empty node
    case.1 do.    NB. y is a leaf node
      select.*Y-X
        case._1 do.a:,y;<x
        case. 0 do.y
        case. 1 do.x;y;a:
      end.
    case.3 do.   NB. y is a parent node
      select.*Y-X
        case._1 do.balance (}:y),<x insert 2{::y
        case. 0 do.y
        case. 1 do.balance (x insert 0{::y);}.y
      end.
  end.
}}

delete=: {{
  select.#y
    case.0 do.y
    case.1 do.y-.x
    case.3 do.
      select.*(1{::y)-x
        case._1 do.balance (}:y),<x delete 2{::y
        case. 0 do.balance (0{::y) insert 2{::y
        case. 1 do.balance (x delete 0{::y);}.y
      end.
    end.
}}

lookup=: {{
  select.#y
    case.0 do.y
    case.1 do.if.x=y do.y else.'' end.
    case.3 do.
      select.*(1{::y)-x
        case._1 do.x lookup 2{::y
        case. 0 do.y
        case. 1 do.x lookup 0{::y
      end.
  end.
}}

clean=: {{
  's0 x s2'=. #every y
  if.*/0=s0,s2 do. 1{:: y NB. degenerate to leaf
  else. y end.
}}

balance=: {{
  if. 2>#y do. y return.end. NB. leaf or empty
  's0 x s2'=. ,#every y
  if. */0=s0,s2 do. 1{:: y return.end. NB. degenerate to leaf
  'l0 x l2'=. L.every y
  if. 2>|l2-l0 do. y return.end. NB. adequately balanced
  if. l2>l0 do.
    'l20 x l22'=. L.every 2{::y
    if. l22 >: l20 do. rotLeft y
    else. rotRightLeft y end.
  else.
    'l00 x l02'=. L.every 0{::y
    if. l00 >: l02 do. rotRight y
    else. rotLeftRight y end.
  end. 
}}

rotLeft=: {{
  't0 t1 t2'=. y
  't20 t21 t22'=. t2
  (clean t0;t1;<t20);t21;<t22
}}

rotRight=: {{
  't0 t1 t2'=. y
  't00 t01 t02'=. t0
  t00;t01;<clean t02;t1;<t2
}}

rotRightLeft=: {{
  't0 t1 t2'=. y
  rotLeft t0;t1;<rotRight t2
}}

rotLeftRight=: {{
  't0 t1 t2'=. y
  rotRight (rotLeft t0);t1;<t2
}}

You may also check:How to resolve the algorithm Binary search step by step in the CoffeeScript programming language
You may also check:How to resolve the algorithm Reverse words in a string step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Random numbers step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Price fraction step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Leap year step by step in the PL/M programming language