Skip to content

Instantly share code, notes, and snippets.

@kyledcline

kyledcline/binary_search_tree.rb

Last active August 29, 2015 14:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kyledcline/415b2b133a8c1bc3fbd2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kyledcline/415b2b133a8c1bc3fbd2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. kyledcline revised this gist May 18, 2014. 1 changed file with 35 additions and 33 deletions.
    68 changes: 35 additions & 33 deletions binary_search_tree.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -8,8 +8,10 @@ def initialize(root=nil, *keys)
    build_tree(*keys) unless keys.empty?
    end

    def build_tree(*key_values)
    key_values.each { |key| insert_node(key) }
    def ordered_keys
    @ordered_keys = []
    traverse
    @ordered_keys
    end

    def find(value)
    @@ -26,39 +28,39 @@ def find(value)
    false
    end

    def insert_node(value)
    node = root
    until node.nil?
    if node.key > value && node.left
    node = node.left
    elsif node.key < value && node.right
    node = node.right
    elsif node.key > value
    node.left = Node.new(value)
    return value
    elsif node.key < value
    node.right = Node.new(value)
    return value
    elsif node.key == value
    return value
    end
    private

    def build_tree(*key_values)
    key_values.each { |key| insert_node(key) }
    end
    end

    def ordered_keys
    @ordered_keys = []
    traverse
    @ordered_keys
    end
    def insert_node(value)
    node = root
    until node.nil?
    if node.key > value && node.left
    node = node.left
    elsif node.key < value && node.right
    node = node.right
    elsif node.key > value
    node.left = Node.new(value)
    return value
    elsif node.key < value
    node.right = Node.new(value)
    return value
    elsif node.key == value
    return value
    end
    end
    end

    def add_key(node_key)
    @ordered_keys << node_key
    end
    def add_key(node_key)
    @ordered_keys << node_key
    end

    def traverse(node=@root)
    return if node.nil?
    traverse(node.left)
    add_key(node.key)
    traverse(node.right)
    end
    def traverse(node=@root)
    return if node.nil?
    traverse(node.left)
    add_key(node.key)
    traverse(node.right)
    end
    end
  2. kyledcline created this gist May 18, 2014.
    64 changes: 64 additions & 0 deletions binary_search_tree.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,64 @@
    class BinarySearchTree

    Node = Struct.new(:key, :left, :right)
    attr_reader :root

    def initialize(root=nil, *keys)
    @root = Node.new(root)
    build_tree(*keys) unless keys.empty?
    end

    def build_tree(*key_values)
    key_values.each { |key| insert_node(key) }
    end

    def find(value)
    node = root
    until node.nil?
    if node.key > value
    node = node.left
    elsif node.key < value
    node = node.right
    elsif node.key == value
    return true
    end
    end
    false
    end

    def insert_node(value)
    node = root
    until node.nil?
    if node.key > value && node.left
    node = node.left
    elsif node.key < value && node.right
    node = node.right
    elsif node.key > value
    node.left = Node.new(value)
    return value
    elsif node.key < value
    node.right = Node.new(value)
    return value
    elsif node.key == value
    return value
    end
    end
    end

    def ordered_keys
    @ordered_keys = []
    traverse
    @ordered_keys
    end

    def add_key(node_key)
    @ordered_keys << node_key
    end

    def traverse(node=@root)
    return if node.nil?
    traverse(node.left)
    add_key(node.key)
    traverse(node.right)
    end
    end