

 This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



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.



Task

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




with javascript_semantics
enum KEY = 0,
     LEFT,
     HEIGHT,    -- (NB +/-1 gives LEFT or RIGHT)
     RIGHT
 
sequence tree = {}
integer freelist = 0
 
function newNode(object key)
integer node
    if freelist=0 then
        node = length(tree)+1
        tree &= {key,NULL,1,NULL}
    else
        node = freelist
        freelist = tree[freelist]
        tree[node+KEY..node+RIGHT] = {key,NULL,1,NULL}
    end if
    return node
end function
 
function height(integer node)
    return iff(node=NULL?0:tree[node+HEIGHT])
end function
 
procedure setHeight(integer node)
    tree[node+HEIGHT] = max(height(tree[node+LEFT]), height(tree[node+RIGHT]))+1
end procedure
 
function rotate(integer node, integer direction)
integer idirection = LEFT+RIGHT-direction
integer pivot = tree[node+idirection]
    {tree[pivot+direction],tree[node+idirection]} = {node,tree[pivot+direction]}
    setHeight(node)
    setHeight(pivot)
    return pivot
end function
 
function getBalance(integer N)
    return iff(N==NULL ? 0 : height(tree[N+LEFT])-height(tree[N+RIGHT]))
end function
 
function insertNode(integer node, object key)
    if node==NULL then
        return newNode(key)
    end if
    integer c = compare(key,tree[node+KEY])
    if c!=0 then
        integer direction = HEIGHT+c    -- LEFT or RIGHT
-- note this crashes under p2js... (easy to fix, not so easy to find)
--      tree[node+direction] = insertNode(tree[node+direction], key)
        atom tnd = insertNode(tree[node+direction], key)
        tree[node+direction] = tnd
        setHeight(node)
        integer balance = trunc(getBalance(node)/2) -- +/-1 (or 0)
        if balance then
            direction = HEIGHT-balance  -- LEFT or RIGHT
            c = compare(key,tree[tree[node+direction]+KEY])
            if c=balance then
                tree[node+direction] = rotate(tree[node+direction],direction)
            end if
            if c!=0 then
                node = rotate(node,LEFT+RIGHT-direction)
            end if
        end if
    end if
    return node
end function
 
function minValueNode(integer node)
    while 1 do
        integer next = tree[node+LEFT]
        if next=NULL then exit end if
        node = next
    end while
    return node
end function
 
function deleteNode(integer root, object key)
integer c
    if root=NULL then return root end if
    c = compare(key,tree[root+KEY])
    if c=-1 then
        tree[root+LEFT] = deleteNode(tree[root+LEFT], key)
    elsif c=+1 then
        tree[root+RIGHT] = deleteNode(tree[root+RIGHT], key)
    elsif tree[root+LEFT]==NULL
       or tree[root+RIGHT]==NULL then
        integer temp = iff(tree[root+LEFT] ? tree[root+LEFT] : tree[root+RIGHT])
        if temp==NULL then  -- No child case
            {temp,root} = {root,NULL}
        else                -- One child case
            tree[root+KEY..root+RIGHT] = tree[temp+KEY..temp+RIGHT]
        end if
        tree[temp+KEY] = freelist
        freelist = temp
    else                    -- Two child case
        integer temp = minValueNode(tree[root+RIGHT])
        tree[root+KEY] = tree[temp+KEY]
        tree[root+RIGHT] = deleteNode(tree[root+RIGHT], tree[temp+KEY])
    end if
    if root=NULL then return root end if
    setHeight(root)
    integer balance = trunc(getBalance(root)/2)
    if balance then
        integer direction = HEIGHT-balance
        c = compare(getBalance(tree[root+direction]),0)
        if c=-balance then
            tree[root+direction] = rotate(tree[root+direction],direction)
        end if
        root = rotate(root,LEFT+RIGHT-direction)
    end if
    return root
end function
 
procedure inOrder(integer node)
    if node!=NULL then
        inOrder(tree[node+LEFT])
        printf(1, "%d ", tree[node+KEY])
        inOrder(tree[node+RIGHT])
    end if
end procedure
 
integer root = NULL
sequence test = shuffle(tagset(50003))
for i=1 to length(test) do
    root = insertNode(root,test[i])
end for
test = shuffle(tagset(50000))
for i=1 to length(test) do
    root = deleteNode(root,test[i])
end for
inOrder(root)
