Updating a binary tree using a pointer
I'm trying to update a self-balancing binary tree. Normally, you can update it by 1) searching a node, 2) deleting it, 3) and inserting the tree with a new node. But, I want to see if this is possible simply by retaining a pointer to a node from the first step and updating it so that I can bypass the deletion and insertion and improve the time complexity, especially when it comes to a large number of nodes.
The tree itself is standard binary search tree.
public class TreeNode<T: Comparable>: Equatable {
public typealias Node = TreeNode<T>
var key: T?
var leftChild: Node?
var rightChild: Node?
fileprivate weak var parent: Node?
var isNullLeaf: Bool {
return key == nil && isLeaf
}
var isLeaf: Bool {
return rightChild == nil && leftChild == nil
}
public init(key: T?, leftChild: Node?, rightChild: Node?, parent: Node?) {
self.key = key
self.leftChild = leftChild
self.rightChild = rightChild
self.parent = parent
self.leftChild?.parent = self
self.rightChild?.parent = self
}
/// Null leaf
public convenience init() {
self.init(key: nil, leftChild: nil, rightChild: nil, parent: nil)
}
static public func == <T>(lhs: TreeNode<T>, rhs: TreeNode<T>) -> Bool {
return lhs.key == rhs.key
}
}
public final class Tree<T: Comparable> {
public typealias Node = TreeNode<T>
fileprivate(set) var root: Node
fileprivate let nullLeaf = Node()
public init() {
root = nullLeaf
}
func search(key: T, f: (inout Node) -> Void) {
search(key: key, node: &root, f: f)
}
fileprivate func search(key: T, node: inout Node, f: (inout Node) -> Void) {
if !node.isNullLeaf {
if let nodeKey = node.key {
/// When a node is found, pass by reference as an argument to a closure so that it retains the connection to the node when it's being update.
if key == nodeKey {
f(&node)
} else if key < nodeKey {
guard node.leftChild != nil else {
return
}
search(key: key, node: &node.leftChild!, f: f)
} else {
guard node.rightChild != nil else {
return
}
search(key: key, node: &node.rightChild!, f: f)
}
}
}
}
public func insert(key: T) {
/// insertion logic
}
/// Other operations
}
My idea was to search the tree through recursion and when a node is found, pass it as an argument to a closure function, which will ultimately be called to update the node. Also, the found node would be pass by reference.
class Test<T: Comparable> {
private(set) var tree = Tree<T>()
func insert(key: T) {
tree.insert(key: key)
}
func update(for node: T, with newNode: T) {
tree.search(key: node) { foundNode in
foundNode.key = newNode
}
}
}
let test = Test<MyNode>()
let node = MyNode()
let anotherNode = MyNode()
test.insert(key: node)
test.update(for: node, with: anotherNode)
The problem is the update doesn't happen. If I search for newly updated node in the tree, it doesn't exist.
Update
Above code is a modified version of a Red-Black tree, specifically modifying the search method to use a pointer instead.
I've tried my idea on a simplified version of a binary search tree below and it seems to be updating the value of a specified node.
public final class BinaryTree<T: Comparable> {
public final class Node<T> {
public var value: T
public var leftChild: Node<T>?
public var rightChild: Node<T>?
public init(value: T, leftChild: Node<T>? = nil, rightChild: Node<T>? = nil) {
self.value = value
self.leftChild = leftChild
self.rightChild = rightChild
}
}
public var rootNode: Node<T>
public init(rootNode: Node<T>) {
self.rootNode = rootNode
}
public func addNodes(to parent: Node<T>, leftChild: Node<T>?, rightChild: Node<T>?) {
parent.leftChild = leftChild
parent.rightChild = rightChild
}
public func searchTree(_ value: T, node: inout Node<T>?, f: (inout Node<T>?) -> Void) {
if node == nil || value == node?.value {
f(&node)
} else if value < node!.value {
searchTree(value, node: &node!.leftChild, f: f)
} else {
searchTree(value, node: &node!.rightChild, f: f)
}
}
}
Tested here.
var rootNode: BinaryTree<Int>.Node<Int>? = BinaryTree<Int>.Node(value: 100, leftChild: nil, rightChild: nil)
let tree = BinaryTree(rootNode: rootNode!)
/// add new nodes. This is not a self-balancing tree so the left child's value has to be smaller than the parent and the right child's value greater than the parent.
let leftChild = BinaryTree<Int>.Node(value: 0, leftChild: nil, rightChild: nil)
let rightChild = BinaryTree<Int>.Node(value: 200, leftChild: nil, rightChild: nil)
tree.addNodes(to: rootNode!, leftChild: leftChild, rightChild: rightChild)
/// the node argument is the starting point of the search so let's start from the root node.
/// the found node will be updated with a new node with a value 50
tree.searchTree(0, node: &rootNode) { foundNode in
let newNode = BinaryTree<Int>.Node(value: 50, leftChild: nil, rightChild: nil)
foundNode = newNode
}
/// The node with a value as 0 is now gone.
tree.searchTree(0, node: &rootNode) { foundNode in
print(foundNode) /// nil
}
/// The node has bee properly updated.
tree.searchTree(50, node: &rootNode) { foundNode in
print(foundNode) /// node with 50 as the value found
}
But can't seem to figure out why the original code isn't updating a node by pointer.
For me the main issue as I mentioned in the comments was with these line of code
fileprivate(set) var root: Node
fileprivate let nullLeaf = Node()
public init() {
root = nullLeaf
}
Root is currently pointing to a nullLeaf which has the following properties:
key = nil
leftChild = nil
self.rightChild = nil
self.parent = nil
I wasn't sure how your insert function was implemented but when I used my insert implementation, this updated the root's properties to the following:
key = nil
leftChild = node
self.rightChild = nil
self.parent = nil
Now when you run your search function which starts at the root:
func search(key: T, f: (inout Node) -> Void) {
search(key: key, node: &root, f: f)
}
fileprivate func search(key: T, node: inout Node, f: (inout Node) -> Void) {
if !node.isNullLeaf {
if let nodeKey = node.key {
/// When a node is found, pass by reference as an
/// argument to a closure so that it retains the
/// connection to the node when it's being update.
if key == nodeKey {
f(&node)
} else if key < nodeKey {
guard node.leftChild != nil else {
return
}
search(key: key, node: &node.leftChild!, f: f)
} else {
guard node.rightChild != nil else {
return
}
search(key: key, node: &node.rightChild!, f: f)
}
}
}
}
if let nodeKey = node.key { is false based on the above root attributes and so it does go into your block where the logic and completion handler gets executed.
Changes and Implementation
Since your main question to answer is
But can't seem to figure out why the original code isn't updating a node by pointer.
I am using my insertion implementation of a Binary Search Tree even though you mentioned Binary Tree as the main purpose is to show the pointer working.
Here is what I updated to your code:
TreeNode - no changes to your code
// No change to your original code
public class TreeNode<T: Comparable>: Equatable {
public typealias Node = TreeNode<T>
var key: T?
var leftChild: Node?
var rightChild: Node?
fileprivate weak var parent: Node?
var isNullLeaf: Bool {
return key == nil && isLeaf
}
var isLeaf: Bool {
return rightChild == nil && leftChild == nil
}
public init(key: T?, leftChild: Node?, rightChild: Node?, parent: Node?) {
self.key = key
self.leftChild = leftChild
self.rightChild = rightChild
self.parent = parent
self.leftChild?.parent = self
self.rightChild?.parent = self
}
/// Null leaf
public convenience init() {
self.init(key: nil, leftChild: nil, rightChild: nil, parent: nil)
}
static public func == <T>(lhs: TreeNode<T>, rhs: TreeNode<T>) -> Bool {
return lhs.key == rhs.key
}
}
Tree - minor changes and some additions, I have added comments
public final class Tree<T: Comparable> {
public typealias Node = TreeNode<T>
// root starts off as nil
fileprivate(set) var root: Node?
// I don't make use of this
//fileprivate let nullLeaf = Node()
// No initialization of root
public init() {
//root = nullLeaf
}
// No change to your code except to safely evaluate root
func search(key: T, f: (inout Node) -> Void) {
if var root = root {
search(key: key, node: &root, f: f)
}
}
// No change to your code here
fileprivate func search(key: T, node: inout Node, f: (inout Node) -> Void)
{
if !node.isNullLeaf {
if let nodeKey = node.key {
/// When a node is found, pass by reference as an argument
/// to a closure so that it retains the connection to the node
/// when it's being update.
if key == nodeKey {
f(&node)
} else if key < nodeKey {
guard node.leftChild != nil else {
return
}
search(key: key, node: &node.leftChild!, f: f)
} else {
guard node.rightChild != nil else {
return
}
search(key: key, node: &node.rightChild!, f: f)
}
}
}
}
// My insert implementation
public func insert(key: T) {
if let root = insertInternal(key, currentNode: root)
{
self.root = root
}
}
// My insert recursion implementation
private func insertInternal(_ data: T, currentNode: Node?) -> Node?
{
if currentNode == nil
{
let newNode = Node()
newNode.key = data
return newNode
}
if let currentData = currentNode?.key, data > currentData
{
currentNode?.rightChild
= insertInternal(data, currentNode: currentNode?.rightChild)
return currentNode
}
currentNode?.leftChild
= insertInternal(data, currentNode: currentNode?.leftChild)
return currentNode
}
// My implementation ofLevel order / Breadth first traversal
// to display values
func printLevelOrder()
{
print("\n** PRINTING BST IN LEVEL ORDER (BFS) ** ")
var queue: [Node] = []
if let root = root
{
queue.append(root)
}
while !queue.isEmpty
{
let currentNode = queue.removeFirst()
if let currentData = currentNode.key
{
print(currentData)
if let left = currentNode.leftChild
{
queue.append(left)
}
if let right = currentNode.rightChild
{
queue.append(right)
}
}
}
}
}
Test class - no much changes
// No change to your code here except display function
class Test<T: Comparable> {
private(set) var tree = Tree<T>()
func insert(key: T) {
tree.insert(key: key)
}
func update(for node: T, with newNode: T) {
tree.search(key: node) { foundNode in
foundNode.key = newNode
}
}
// Just added a display
func display() {
tree.printLevelOrder()
}
}
Finally here is the main
Test 1 - simple with 1 node
print("Test 1")
var test = Test<Int>()
print("Inserting 10")
test.insert(key: 10)
print("Updating 10 with 8")
test.update(for: 10, with: 8)
test.display()
Output
Test 1
Inserting 10
Updating 10 with 8
** PRINTING BST IN LEVEL ORDER (BFS) **
8
As you can see the exchange of values has happened successfully with the pointer
Test 2 - a little more complex tree with many nodes
print("\n\nTest 2")
test = Test<Int>()
print("Inserting 5")
test.insert(key: 5)
print("Inserting 11")
test.insert(key: 11)
print("Inserting 4")
test.insert(key: 4)
print("Inserting 7")
test.insert(key: 7)
print("Inserting 17")
test.insert(key: 17)
print("Current tree before update")
test.display()
This should give us a binary search tree like this:
And printing the BFS traversal shows us this:
Test 2
Inserting 5
Inserting 11
Inserting 4
Inserting 7
Inserting 17
Current tree before update
** PRINTING BST IN LEVEL ORDER (BFS) **
5
4
11
7
17
Now Let's try to change the value of 7 with 16 which is done with the pointer
print("Updating 7 with 16")
test.update(for: 7, with: 16)
print("Current tree after update")
test.display()
The output is as expected with the value of 7 and swapped with 16
Updating 7 with 16
Current tree after update
** PRINTING BST IN LEVEL ORDER (BFS) **
5
4
11
16
17
Ofcourse, after this swap, the tree is no longer a Binary Search Tree but I think you can see the pointer working well with the above tweaks.
- Math.Sin() gives incorrect value
- How to run my python script when the sunOS is start booting
- Express-session: not resetting cookie expiration on each request
- Getting a stack overflow exception when normalizing a vector
- Edit default summary function in R gives error for multiple variables
- What was a For loop? Why isn't it needed in R?
- How to use download button in shiny and save results in various formats (csv, texte, pdf, spss...)?
- Why are there two assignment operators, `<-` and `->` in R?
- lm()$assign: what is it?
- How to get the value of list(...) in R and S functions
- Design matrix for MLM from library(lme4) with fixed and random effects
- how to generate elements not included in my sample
- Create a matrix with gradually changing values without a for loop
- Emacs ESS and S-plus ( S+ ) 8.1 compatability
- How to lag date-index in a time-series in R?
- Nonlinear regression in R / S
- Calling R from S-Plus?