• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?