SHARE
TWEET

BinarySearchTree

CloneTrooper1019 Jul 20th, 2019 (edited) 166 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. local BinarySearchTree = {}
  2. BinarySearchTree.__index = BinarySearchTree
  3.  
  4. local push = table.insert
  5. local pop = table.remove
  6.  
  7. -- Inserts a unique value into the binary search tree.
  8. -- Returns true if the value was valid and inserted.
  9. function BinarySearchTree:Insert(value)
  10.     if value == nil then
  11.         return false
  12.     end
  13.  
  14.     local node = self.Root
  15.    
  16.     while node.Value do
  17.         if value < node.Value then
  18.             node = node.Left
  19.         elseif value > node.Value then
  20.             node = node.Right
  21.         else
  22.             return false
  23.         end
  24.     end
  25.    
  26.     node.Value = value
  27.     node.Right = {}
  28.     node.Left = {}
  29.    
  30.     return true
  31. end
  32.  
  33. -- Returns an iterator function that performs an
  34. -- in-order traversal of the binary search tree.
  35. function BinarySearchTree:Iterate()
  36.     return coroutine.wrap(function ()
  37.         local stack = {}
  38.         local visited = {}
  39.        
  40.         local node = self.Root
  41.         local index = 1
  42.        
  43.         while node do
  44.             -- Visit the left node
  45.             local left = node.Left
  46.            
  47.             if left and not visited[left] then
  48.                 push(stack, node)
  49.                 node = left
  50.             else
  51.                 -- Visit this node
  52.                 if not visited[node] then
  53.                     local value = node.Value
  54.                    
  55.                     if value then
  56.                         coroutine.yield(index, value)
  57.                         index = index + 1
  58.                     end
  59.                    
  60.                     visited[node] = true
  61.                 end
  62.                
  63.                 -- Visit the right node
  64.                 local right = node.Right
  65.                
  66.                 if right and not visited[right] then
  67.                     push(stack, node)
  68.                     node = right
  69.                 else
  70.                     node = pop(stack)
  71.                 end
  72.             end
  73.         end
  74.     end)
  75. end
  76.  
  77. -- Constructs a new BinarySearchTree.
  78. function BinarySearchTree.new()
  79.     local tree = {}
  80.     tree.Root = {}
  81.    
  82.     return setmetatable(tree, BinarySearchTree)
  83. end
  84.  
  85. return BinarySearchTree
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top