codepad

Language:

class BinaryTreeNode
  attr_accessor :left_child, :right_child, :parent, :data

def initialize(data)
    @left_child = @right_child = @parent = nil
    @data = data
  end
end

class DigitalSearchTree
  def initialize
    @root = nil

end

# assume field is 5 bit
  def insert(data)
    node = BinaryTreeNode.new(data)
    offset = data[0] - 'A'[0] + 1

mask = 0b10000

if !@root
      @root = node
      return true
    end

node_ptr = @root

begin
      bit = offset & mask

if node_ptr.data == node.data
        p "Already found"
        return false
      end

if bit == 0
        if !node_ptr.left_child
          node_ptr.left_child = node
          node.parent = node_ptr
          return true
        end

node_ptr = node_ptr.left_child
      else  # bit > 0
        if !node_ptr.right_child
          node_ptr.right_child = node
          node.parent = node_ptr
          return true
        end

node_ptr = node_ptr.right_child
      end

mask = mask >> 1
    end while mask > 0

return false
  end

def delete(data)
    target_node = search(data)

return nil if !target_node

if @root == target_node
      @root = nil

return target_node
    end

parent_node = target_node.parent

is_target_left_child = (parent_node.left_child == target_node)

if !target_node.left_child && !target_node.right_child
      # if node has no child
      if is_target_left_child
        parent_node.left_child = nil
      else
        parent_node.right_child = nil
      end

elsif target_node.left_child && !target_node.right_child
      # node has left child
      if is_target_left_child
        parent_node.left_child = target_node.left_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.left_child
        parent_node.right_child.parent = parent_node
      end

elsif !target_node.left_child && target_node.right_child
      # node has right child
      if is_target_left_child
        parent_node.left_child = target_node.right_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.right_child
        parent_node.right_child.parent = parent_node
      end
    else
      # node has both children

# move node's right child to node's left_child's right child
      target_node.left_child.right_child = target_node.right_child
      target_node.right_child.parent = target_node.left_child

# at now, assume node has only left child
      if is_target_left_child
        parent_node.left_child = target_node.left_child
        parent_node.left_child.parent = parent_node
      else
        parent_node.right_child = target_node.left_child
        parent_node.right_child.parent = parent_node
      end
      
    end

return target_node

end

# assume field is 5 bit
  def search(data)
    offset = data[0] - 'A'[0] + 1

mask = 0b10000

return nil if !@root

node_ptr = @root

begin
      bit = offset & mask

return node_ptr if node_ptr.data == data

if bit == 0
        return nil if !node_ptr.left_child
          
        node_ptr = node_ptr.left_child
      else  # bit > 0
        return nil if !node_ptr.right_child

node_ptr = node_ptr.right_child
      end

mask = mask >> 1
    end while mask > 0

return nil
  end

def inorder_traversal
    travel_list = []

inorder_traversal_recursive(travel_list, @root) unless @root == nil

return travel_list
  end

private

def inorder_traversal_recursive(travel_list, node)
    return if node == nil

inorder_traversal_recursive(travel_list, node.left_child)
    travel_list.push(node)
    inorder_traversal_recursive(travel_list, node.right_child)

end

def print_travel_node_list(travel_list)
  print '[ '

travel_list.each do |node|
    print node.data.to_s
    print " "
  end

puts ']'
end

dst = DigitalSearchTree.new

dst.insert('A')
dst.insert('S')
dst.insert('E')
dst.insert('R')
dst.insert('C')
dst.insert('H')
dst.insert('X')
dst.insert('X')
puts "------------------------------"

traversal_list = dst.inorder_traversal
print_travel_node_list traversal_list

puts "------------------------------"
puts dst.search('B') != nil
puts dst.search('E') != nil
puts dst.search('X') != nil
puts dst.search('F') != nil
puts "------------------------------"

dst.delete('H')
puts dst.search('H') != nil
puts dst.search('C') != nil
puts "------------------------------"

dst.delete('E')
puts dst.search('E') != nil
puts dst.search('C') != nil
puts "------------------------------"

dst.delete('S')
puts dst.search('S') != nil
puts dst.search('X') != nil
puts dst.search('R') != nil
puts "------------------------------"

traversal_list = dst.inorder_traversal
print_travel_node_list traversal_list
puts "------------------------------"

Private [?]

Run code