10000 Updating playground · codee/swift-algorithm-club@c104087 · GitHub
[go: up one dir, main page]
Skip to content

Commit c104087

Browse files
author
Chris Pilcher
committed
Updating playground
1 parent 0267f61 commit c104087

File tree

3 files changed

+65
-71
lines changed

3 files changed

+65
-71
lines changed

‎AVL Tree/AVLTree.playground/Contents.swift

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2,26 +2,26 @@
22

33
let tree = AVLTree<Int, String>()
44

5-
tree.insert(5, "five")
5+
tree.insert(key: 5, payload: "five")
66
print(tree)
77

8-
tree.insert(4, "four")
8+
tree.insert(key: 4, payload: "four")
99
print(tree)
1010

11-
tree.insert(3, "three")
11+
tree.insert(key: 3, payload: "three")
1212
print(tree)
1313

14-
tree.insert(2, "two")
14+
tree.insert(key: 2, payload: "two")
1515
print(tree)
1616

17-
tree.insert(1, "one")
17+
tree.insert(key: 1, payload: "one")
1818
print(tree)
1919
print(tree.debugDescription)
2020

21-
let node = tree.search(2) // "two"
21+
let node = tree.search(input: 2) // "two"
2222

23-
tree.delete(5)
24-
tree.delete(2)
25-
tree.delete(1)
26-
tree.delete(4)
27-
tree.delete(3)
23+
tree.delete(key: 5)
24+
tree.delete(key: 2)
25+
tree.delete(key: 1)
26+
tree.delete(key: 4)
27+
tree.delete(key: 3)

‎AVL Tree/AVLTree.playground/Sources/AVLTree.swift

Lines changed: 54 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -23,13 +23,13 @@
2323
public class TreeNode<Key: Comparable, Payload> {
2424
public typealias Node = TreeNode<Key, Payload>
2525

26-
public var payload: Payload?
26+
var payload: Payload?
2727

28-
private var key: Key
28+
fileprivate var key: Key
2929
internal var leftChild: Node?
3030
internal var rightChild: Node?
31-
private var height: Int
32-
weak private var parent: Node?
31+
fileprivate var height: Int
32+
weak fileprivate var parent: Node?
3333

3434
public init(key: Key, payload: Payload?, leftChild: Node?, rightChild: Node?, parent: Node?, height: Int) {
3535
self.key = key
@@ -51,46 +51,46 @@ public class TreeNode<Key: Comparable, Payload> {
5151
self.init(key: key, payload: nil)
5252
}
5353

54-
public var isRoot: Bool {
54+
var isRoot: Bool {
5555
return parent == nil
5656
}
5757

58-
public var isLeaf: Bool {
58+
var isLeaf: Bool {
5959
return rightChild == nil && leftChild == nil
6060
}
6161

62-
public var isLeftChild: Bool {
62+
var isLeftChild: Bool {
6363
return parent?.leftChild === self
6464
}
6565

66-
public var isRightChild: Bool {
66+
var isRightChild: Bool {
6767
return parent?.rightChild === self
6868
}
6969

70-
public var hasLeftChild: Bool {
70+
var hasLeftChild: Bool {
7171
return leftChild != nil
7272
}
7373

74-
public var hasRightChild: Bool {
74+
var hasRightChild: Bool {
7575
return rightChild != nil
7676
}
7777

78-
public var hasAnyChild: Bool {
78+
var hasAnyChild: Bool {
7979
return leftChild != nil || rightChild != nil
8080
}
8181

82-
public var hasBothChildren: Bool {
82+
var hasBothChildren: Bool {
8383
return leftChild != nil && rightChild != nil
8484
}
8585
}
8686

8787
// MARK: - The AVL tree
8888

89-
public class AVLTree<Key: Comparable, Payload> {
89+
open class AVLTree<Key: Comparable, Payload> {
9090
public typealias Node = TreeNode<Key, Payload>
9191

92-
private(set) public var root: Node?
93-
private(set) public var size = 0
92+
fileprivate(set) var root: Node?
93+
fileprivate(set) var size = 0
9494

9595
public init() { }
9696
}
@@ -115,26 +115,26 @@ extension TreeNode {
115115

116116
extension AVLTree {
117117
subscript(key: Key) -> Payload? {
118-
get { return search(key) }
119-
set { insert(key, newValue) }
118+
get { return search(input: key) }
119+
set { insert(key: key, payload: newValue) }
120120
}
121121

122122
public func search(input: Key) -> Payload? {
123-
if let result = search(input, root) {
123+
if let result = search(key: input, node: root) {
124124
return result.payload
125125
} else {
126126
return nil
127127
}
128128
}
129129

130-
private func search(key: Key, _ node: Node?) -> Node? {
130+
fileprivate func search(key: Key, node: Node?) -> Node? {
131131
if let node = node {
132132
if key == node.key {
133133
return node
134134
} else if key < node.key {
135-
return search(key, node.leftChild)
135+
return search(key: key, node: node.leftChild)
136136
} else {
137-
return search(key, node.rightChild)
137+
return search(key: key, node: node.rightChild)
138138
}
139139
}
140140
return nil
@@ -144,31 +144,31 @@ extension AVLTree {
144144
// MARK: - Inserting new items
145145

146146
extension AVLTree {
147-
public func insert(key: Key, _ payload: Payload? = nil) {
147+
public func insert(key: Key, payload: Payload? = nil) {
148148
if let root = root {
149-
insert(key, payload, root)
149+
insert(input: key, payload: payload, node: root)
150150
} else {
151151
root = Node(key: key, payload: payload)
152152
}
153153
size += 1
154154
}
155155

156-
private func insert(input: Key, F987 _ payload: Payload?, _ node: Node) {
156+
private func insert(input: Key, payload: Payload?, node: Node) {
157157
if input < node.key {
158158
if let child = node.leftChild {
159-
insert(input, payload, child)
159+
insert(input: input, payload: payload, node: child)
160160
} else {
161161
let child = Node(key: input, payload: payload, leftChild: nil, rightChild: nil, parent: node, height: 1)
162162
node.leftChild = child
163-
balance(child)
163+
balance(node: child)
164164
}
165165
} else {
166166
if let child = node.rightChild {
167-
insert(input, payload, child)
167+
insert(input: input, payload: payload, node: child)
168168
} else {
169169
let child = Node(key: input, payload: payload, leftChild: nil, rightChild: nil, parent: node, height: 1)
170170
node.rightChild = child
171-
balance(child)
171+
balance(node: child)
172172
}
173173
}
174174
}
@@ -177,37 +177,37 @@ extension AVLTree {
177177
// MARK: - Balancing tree
178178

179179
extension AVLTree {
180-
private func updateHeightUpwards(node: Node?) {
180+
fileprivate func updateHeightUpwards(node: Node?) {
181181
if let node = node {
182182
let lHeight = node.leftChild?.height ?? 0
183183
let rHeight = node.rightChild?.height ?? 0
184184
node.height = max(lHeight, rHeight) + 1
185-
updateHeightUpwards(node.parent)
185+
updateHeightUpwards(node: node.parent)
186186
}
187187
}
188188

189-
private func lrDifference(node: Node?) -> Int {
189+
fileprivate func lrDifference(node: Node?) -> Int {
190190
let lHeight = node?.leftChild?.height ?? 0
191191
let rHeight = node?.rightChild?.height ?? 0
192192
return lHeight - rHeight
193193
}
194194

195-
private func balance(node: Node?) {
195+
fileprivate func balance(node: Node?) {
196196
guard let node = node else {
197197
return
198198
}
199199

200-
updateHeightUpwards(node.leftChild)
201-
updateHeightUpwards(node.rightChild)
200+
updateHeightUpwards(node: node.leftChild)
201+
updateHeightUpwards(node: node.rightChild)
202202

203-
var nodes = [Node?](count: 3, repeatedValue: nil)
204-
var subtrees = [Node?](count: 4, repeatedValue: nil)
203+
var nodes = [Node?](repeating: nil, count: 3)
204+
var subtrees = [Node?](repeating: nil, count: 4)
205205
let nodeParent = node.parent
206206

207-
let lrFactor = lrDifference(node)
207+
let lrFactor = lrDifference(node: node)
208208
if lrFactor > 1 {
209209
// left-left or left-right
210-
if lrDifference(node.leftChild) > 0 {
210+
if lrDifference(node: node.leftChild) > 0 {
211211
// left-left
212212
nodes[0] = node
213213
nodes[2] = node.leftChild
@@ -230,7 +230,7 @@ extension AVLTree {
230230
}
231231
} else if lrFactor < -1 {
232232
// right-left or right-right
233-
if lrDifference(node.rightChild) < 0 {
233+
if lrDifference(node: node.rightChild) < 0 {
234234
// right-right
235235
nodes[1] = node
236236
nodes[2] = node.rightChild
@@ -253,7 +253,7 @@ extension AVLTree {
253253
}
254254
} else {
255255
// Don't need to balance 'node', go for parent
256-
balance(node.parent)
256+
balance(node: node.parent)
257257
return
258258
}
259259

@@ -285,19 +285,19 @@ extension AVLTree {
285285
nodes[0]?.rightChild = subtrees[3]
286286
subtrees[3]?.parent = nodes[0]
287287

288-
updateHeightUpwards(nodes[1]) // Update height from left
289-
updateHeightUpwards(nodes[0]) // Update height from right
288+
updateHeightUpwards(node: nodes[1]) // Update height from left
289+
updateHeightUpwards(node: nodes[0]) // Update height from right
290290

291-
balance(nodes[2]?.parent)
291+
balance(node: nodes[2]?.parent)
292292
}
293293
}
294294

295295
// MARK: - Displaying tree
296296

297297
extension AVLTree {
298-
private func display(node: Node?, level: Int) {
298+
fileprivate func display(node: Node?, level: Int) {
299299
if let node = node {
300-
display(node.rightChild, level: level + 1)
300+
display(node: node.rightChild, level: level + 1)
301301
print("")
302302
if node.isRoot {
303303
print("Root -> ", terminator: "")
@@ -306,12 +306,12 @@ extension AVLTree {
306306
print(" ", terminator: "")
307307
}
308308
print("(\(node.key):\(node.height))", terminator: "")
309-
display(node.leftChild, level: level + 1)
309+
display(node: node.leftChild, level: level + 1)
310310
}
311311
}
312312

313313
public func display(node: Node) {
314-
display(node, level: 0)
314+
display(node: node, level: 0)
315315
print("")
316316
}
317317
}
@@ -323,8 +323,8 @@ extension AVLTree {
323323
if size == 1 {
324324
root = nil
325325
size -= 1
326-
} else if let node = search(key, root) {
327-
delete(node)
326+
} else if let node = search(key: key, node: root) {
327+
delete(node: node)
328328
size -= 1
329329
}
330330
}
@@ -344,21 +344,21 @@ extension AVLTree {
344344
parent.rightChild = nil
345345
}
346346

347-
balance(parent)
347+
balance(node: parent)
348348
} else {
349349
// at root
350350
root = nil
351351
}
352352
} else {
353353
// Handle stem cases
354-
if let replacement = node.leftChild?.maximum() where replacement !== node {
354+
if let replacement = node.leftChild?.maximum() , replacement !== node {
355355
node.key = replacement.key
356356
node.payload = replacement.payload
357-
delete(replacement)
358-
} else if let replacement = node.rightChild?.minimum() where replacement !== node {
357+
delete(node: replacement)
358+
} else if let replacement = node.rightChild?.minimum() , replacement !== node {
359359
node.key = replacement.key
360360
node.payload = replacement.payload
361-
delete(replacement)
361+
delete(node: replacement)
362362
}
363363
}
364364
}

‎AVL Tree/AVLTree.playground/timeline.xctimeline

Lines changed: 0 additions & 6 deletions
This file was deleted.

0 commit comments

Comments
 (0)
0