Module 5
Binary Trees
Remove Element

CC315 Fall 2020

Motivation

When we need to remove a node, we will replace it with its smallest right descendant

Types of Removal

  • Leaf
  • No Right Child
  • Right Child

Removing a Leaf

Removing a Node with No Right Child

Removing a Node with
Right Child

Needed Functions

  • Remove
  • Remove Smallest
  • Prune (Left and Right)

Pruning


    function PRUNERIGHT()
        if RIGHTCHILD has no value
            REMOVECHILD(RIGHTCHILD)
            set this nodes RIGHTCHILD former RIGHTCHILDs RIGHTCHILD
            if RIGHTCHLID is not none
                ADDCHILD(RIGHTCHILD)
 

    function PRUNELEFT()
        if LEFTCHILD has no value
            REMOVECHILD(LEFTCHILD)
            set this nodes LEFTCHILD former LEFTCHILDs RIGHTCHILD
            if LEFTCHILD is not none
                ADDCHILD(LEFTCHILD)

Remove Smallest


function REMOVESMALLEST()
    if node has left child
        REPLACEMENT = LEFTCHILD.REMOVESMALLEST
        prune left-side
        return REPLACEMENT
    else
        REPLACEMENT = node.ITEM
        if node has right child
            node.ITEM = RIGHTCHILD.REMOVESMALLEST()
            prune right-side
        else
            node.ITEM = NONE
        return REPLACEMENT
end function

Remove Smallest


function REMOVESMALLEST()
    if node has left child
        REPLACEMENT = LEFTCHILD.REMOVESMALLEST
        prune left-side
        return REPLACEMENT
    else
        REPLACEMENT = node.ITEM
        if node has right child
            node.ITEM = RIGHTCHILD.REMOVESMALLEST()
            prune right-side
        else
            node.ITEM = NONE
        return REPLACEMENT
end function

Remove Smallest


function REMOVESMALLEST()
    if node has left child
        REPLACEMENT = LEFTCHILD.REMOVESMALLEST()
        prune left-side
        return REPLACEMENT
    else
        REPLACEMENT = node.ITEM
        if node has right child
            node.ITEM = RIGHTCHILD.REMOVESMALLEST()
            prune right-side
        else
            node.ITEM = NONE
        return REPLACEMENT
end function

Remove


function REMOVE(VALUE)
    if node.ITEM is VALUE
        if node is a leaf
            set node.ITEM to none
            return TRUE
        else if node has no right child
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune left-side
            switch left child to right child
            return TRUE
        else
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune right-side
            return TRUE
    else
        if node.ITEM > VALUE
            if node has LEFTCHILD
                SUCCESS = LEFTCHILD.REMOVE(VALUE)
                prune left-side
                return SUCCESS
            else
                return FALSE
        else
            if node has RIGHTCHILD
                SUCCESS = RIGHTCHILD.REMOVE(VALUE)
                prune right-side
                return SUCCESS
            else
                return FALSE
end function

Remove


function REMOVE(VALUE)
    if node.ITEM is VALUE
        if node is a leaf
            set node.ITEM to none
            return TRUE
        else if node has no right child
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune left-side
            switch left child to right child
            return TRUE
        else
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune right-side
            return TRUE
    else
        if node.ITEM > VALUE
            if node has LEFTCHILD
                SUCCESS = LEFTCHILD.REMOVE(VALUE)
                prune left-side
                return SUCCESS
            else
                return FALSE
        else
            if node has RIGHTCHILD
                SUCCESS = RIGHTCHILD.REMOVE(VALUE)
                prune right-side
                return SUCCESS
            else
                return FALSE
end function

Remove


function REMOVE(VALUE)
    if node.ITEM is VALUE
        if node is a leaf
            set node.ITEM to none
            return TRUE
        else if node has no right child
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune left-side
            switch left child to right child
            return TRUE
        else
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune right-side
            return TRUE
    else
        if node.ITEM > VALUE
            if node has LEFTCHILD
                SUCCESS = LEFTCHILD.REMOVE(VALUE)
                prune left-side
                return SUCCESS
            else
                return FALSE
        else
            if node has RIGHTCHILD
                SUCCESS = RIGHTCHILD.REMOVE(VALUE)
                prune right-side
                return SUCCESS
            else
                return FALSE
end function

Remove


function REMOVE(VALUE)
    if node.ITEM is VALUE
        if node is a leaf
            set node.ITEM to none
            return TRUE
        else if node has no right child
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune left-side
            switch left child to right child
            return TRUE
        else
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune right-side
            return TRUE
    else
        if node.ITEM > VALUE
            if node has LEFTCHILD
                SUCCESS = LEFTCHILD.REMOVE(VALUE)
                prune left-side
                return SUCCESS
            else
                return FALSE
        else
            if node has RIGHTCHILD
                SUCCESS = RIGHTCHILD.REMOVE(VALUE)
                prune right-side
                return SUCCESS
            else
                return FALSE
end function

Remove


function REMOVE(VALUE)
    if node.ITEM is VALUE
        if node is a leaf
            set node.ITEM to none
            return TRUE
        else if node has no right child
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune left-side
            switch left child to right child
            return TRUE
        else
            node.ITEM = LEFTCHILD.REMOVESMALLEST()
            prune right-side
            return TRUE
    else
        if node.ITEM > VALUE
            if node has LEFTCHILD
                SUCCESS = LEFTCHILD.REMOVE(VALUE)
                prune left-side
                return SUCCESS
            else
                return FALSE
        else
            if node has RIGHTCHILD
                SUCCESS = RIGHTCHILD.REMOVE(VALUE)
                prune right-side
                return SUCCESS
            else
                return FALSE
end function
"/js/highlight.pack.js"