AVL Interval Tree (non-recursive) | srgdev.com

AVL Interval Tree (non-recursive)

A self-balancing augmented interval binary search tree; non recursive insert/lookup PHP implementation with O(log n) time complexity.PHP, Interval Tree, BST Download (6KB): AVLIntervalTree.php

About

The data structure at the heart of this implementation is built on top of an Adelson-Velsky and Landis self-balancing binary search tree. Every node stores a 'low' value (start of interval), which is also used as the key, and a 'high' value (end of interval). In addition, the tree is augmented by storing maximum 'high' as an extra annotation in each node. For performance reasons duplicates are ignored and if multiple intervals have the same start value only the longer interval is stored. As of now, only insert and search functionality is implemented, although the tree is rigidly balanced and is optimized for lookup intensive tasks, both methods do perform in O(log n) time, with most inserts being as fast as lookups thanks to the "Non-recursive algorithm for AVL tree insertion" by Neil Brown.

Usage (interval-tree-test.php):
<?php
include 'AVLIntervalTree.php';

/**
 * @param AVLIntervalNode|null $node
 */
function printOverlapInfo($node){
    if($node===null){
        return "No Overlap".PHP_EOL;
    }else{
        return "Overlap Found: ".$node->l.",".$node->h.PHP_EOL;
    }
}


$tree=new AVLIntervalTree();

echo "Insert 1,10".PHP_EOL;
$tree->insert(1,10);
echo "Insert 20,29".PHP_EOL;
$tree->insert(20,29);

$low=10;$high=15;
$n=$tree->lookup($low,$high);
echo "Lookup $low,$high: ".printOverlapInfo($n);

$low=10;$high=20;
$n=$tree->lookupExclusive($low,$high);
echo "LookupExclusive $low,$high: ".printOverlapInfo($n);

$low=23;$high=27;
$n=$tree->lookup($low,$high);
echo "Lookup $low,$high: ".printOverlapInfo($n);
output: php interval-tree-test.php
Insert 1,10
Insert 20,29
Lookup 10,15: Overlap Found: 1,10
LookupExclusive 10,20: No Overlap
Lookup 23,27: Overlap Found: 20,29

AVLIntervalTree.php

<?php
// AVL tree code is ported from https://neil.brown.name/blog/20041124101820

class AVLIntervalNode{
    public $l; // low - also key
    public $h; // high
    public $m; // max
    /** @var AVLIntervalNode[] */
    public $next;
    public $longer;

    /**
     * @param int $l low
     * @param int $h high
     */
    public function __construct($l, $h)
    {
        $this->l = $l;
        $this->h = $h;
        $this->m = $h;
        $this->next = [null,null];
        $this->longer = -1;
    }
}

class AVLIntervalTree{

    /** @var AVLIntervalNode $tree */
    private $nt=null;

    /**
     * @param AVLIntervalNode $n
     * @return int
     */
    private function findNodeMax($n){
        $max=$n->h;
        $cn=$n->next[0];
        if($cn!==null && $cn->m > $max){
            $max=$cn->m;
        }
        $cn=$n->next[1];
        if($cn!==null && $cn->m > $max){
            $max=$cn->m;
        }
        return $max;
    }

    /**
     * @param AVLIntervalNode $path
     * @param int $dir
     * @return AVLIntervalNode
     */
    private function rotate_2(&$path,$dir){
        $b=$path;
        $d=$b->next[$dir];
        $c=$d->next[1-$dir];
        $e=$d->next[$dir];
        $path=$d;

        $d->next[1-$dir] = $b;
        $b->next[$dir] = $c;

        $b->longer = -1;
        $d->longer = -1;

        $b->m=$this->findNodeMax($b);
        $d->m=$this->findNodeMax($d);

        return $e;
    }

    /**
     * @param AVLIntervalNode $path
     * @param int $dir
     * @param int $third
     * @return AVLIntervalNode
     */
    private function rotate_3(&$path,$dir,$third){

        $B = $path;
        $F = $B->next[$dir];
        $D = $F->next[1-$dir];
        // node: C and E can be NULL
        $C = $D->next[1-$dir];
        $E = $D->next[$dir];
        $path = $D;
        $D->next[1-$dir] = $B;
        $D->next[$dir] = $F;
        $B->next[$dir] = $C;
        $F->next[1-$dir] = $E;
        $D->longer = -1;

        $B->m=$this->findNodeMax($B);
        $F->m=$this->findNodeMax($F);
        $D->m=$this->findNodeMax($D);

        // assume both trees are balanced
        $B->longer = $F->longer = -1;

        if ($third === -1) {
            return null;
        }

        if ($third === $dir) {
            // E holds the insertion so B is unbalanced
            $B->longer = 1-$dir;
            return $E;
        } else {
            // C holds the insertion so F is unbalanced
            $F->longer = $dir;
            return $C;
        }
    }

    /**
     * @param AVLIntervalNode $path
     * @param int $low
     */
    private function rebalance_path($path, $low){
        while ($path && $low !== $path->l) {
            $next_step = (int)($low > $path->l);
            $path->longer = $next_step;
            $path = $path->next[$next_step];
        }
    }


    /**
     * @param AVLIntervalNode $path
     * @param int $low
     */
    private function rebalance(&$path, $low){

        if($path->longer < 0){
            $this->rebalance_path($path,$low);
            return;
        }
        $first = (int)($low > $path->l);
        if($path->longer !== $first) {
            /* took the shorter path */
            $path->longer = -1;
            $this->rebalance_path($path->next[$first], $low);
            return;
        }

        $second = (int)($low > $path->next[$first]->l);
        if($first === $second){
           /* just a two-point rotate */
            $p = $this->rotate_2($path, $first);
            $this->rebalance_path($p, $low);
           return;
        }

        /* fine details of the 3 point rotate depend on the third step.
        * However there may not be a third step, if the third point of the
        * rotation is the newly inserted point.  In that case we record
        * the third step as NEITHER ( -1 )
        */
        $p = $path->next[$first]->next[$second];
        if($low === $p->l) $third = -1;
        else $third = (int)($low > $p->l);
        $p = $this->rotate_3($path, $first, $third);
        $this->rebalance_path($p, $low);
    }


    /**
     * @param AVLIntervalNode|null $tree
     * @param int $low
     * @param int $high
     * @return int
     */
    function insert($low,$high){
        $tree=&$this->nt;
        $path_top=&$tree;

        while ($tree!==null && $tree->l!==$low){
            if($tree->longer >= 0){
                $path_top=&$tree;
            }
            if($tree->m < $high){
                $tree->m=$high;
            }
            $tree=&$tree->next[(int)($low>$tree->l)];
        }

        if($tree!==null){
            // already exists
            if($tree->h < $high){
                $tree->h=$high;
            }
            if($tree->m < $high){
                $tree->m=$high;
            }
            return 0;
        }

         $tree=new AVLIntervalNode($low,$high);

        if($path_top!==null) {
            $this->rebalance($path_top, $low);
        }

        return 1;
    }



    /**
     * @param int $low
     * @param int $high
     * @return AVLIntervalNode|null null=no overlap
     */
    function lookup($low, $high){
        $tree=$this->nt;
        while ($tree!==null
            && ($tree->l > $high || $low > $tree->h)) {

            // If left child of root is present and max of left child is
            // greater than or equal to given interval, then i may
            // overlap with an interval is left subtree
            // Else interval can only overlap with right subtree

            $tree = $tree->next[
            (int)($tree->next[0]===null || $tree->next[0]->m < $low)];
        }
        return $tree;
    }

    /**
     * @param int $low
     * @param int $high
     * @return AVLIntervalNode|null null=no overlap
     */
    function lookupExclusive($low, $high){
        $tree=$this->nt;
        while ($tree!==null
            && ($tree->l >= $high || $low >= $tree->h)) {
            $tree = $tree->next[
                (int)($tree->next[0]===null || $tree->next[0]->m < $low)];
        }
        return $tree;
    }
}