使用指针更新二叉树
Updating a binary tree using a pointer
我正在尝试更新自平衡二叉树。通常，您可以通过以下方式更新它：1) 搜索节点，2) 删除它，3) 并插入带有新节点的树。但是，我想看看是否可以通过保留第一步中指向节点的指针并更新它来绕过删除和插入并提高时间复杂度，尤其是当涉及到大量节点时.
树本身就是标准的二叉搜索树。
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
}
我的想法是通过递归搜索树，当找到一个节点时，将其作为参数传递给闭包函数，最终将调用它来更新节点。此外，找到的节点将通过引用传递。
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)
问题是更新没有发生。如果我在树中搜索新更新的节点，它不存在。
更新
以上代码是Red-Black tree的修改版，具体修改了搜索方法，改为使用指针。
我在下面的二叉搜索树的简化版本上尝试了我的想法，它似乎正在更新指定节点的值。
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)
}
}
}
在这里测试。
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
}
但似乎无法弄清楚为什么原始代码不通过指针更新节点。
对我来说，我在评论中提到的主要问题是这些代码行
fileprivate(set) var root: Node
fileprivate let nullLeaf = Node()
public init() {
root = nullLeaf
}
Root 当前指向 nullLeaf，它具有以下属性：
key = nil
leftChild = nil
self.rightChild = nil
self.parent = nil
我不确定你的插入函数是如何实现的，但是当我使用我的插入实现时，这将根的属性更新为以下内容：
key = nil
leftChild = node
self.rightChild = nil
self.parent = nil
现在，当您 运行 您的 search 函数从根开始时：
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 { 是错误的，因此它会进入执行逻辑和完成处理程序的块。
更改和实施
因为你要回答的主要问题是
But can't seem to figure out why the original code isn't updating a
node by pointer.
我正在使用我的二叉搜索树的插入实现，尽管你提到二叉树的主要目的是显示指针工作。
这是我对您的代码更新的内容：
TreeNode - 没有更改您的代码
// 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
}
}
树 - 小改动和一些补充，我添加了评论
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)
}
}
}
}
}
测试 class - 没有太大变化
// 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()
}
}
最后是主要内容
测试 1 - 简单，有 1 个节点
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()
输出
Test 1
Inserting 10
Updating 10 with 8
** PRINTING BST IN LEVEL ORDER (BFS) **
8
如您所见，值交换已成功与指针发生
测试 2 - 具有许多节点的更复杂的树
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()
这应该给我们一个像这样的二叉搜索树：
打印 BFS 遍历向我们展示了这一点：
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
现在让我们尝试将 7 的值更改为 16，这是通过指针完成的
print("Updating 7 with 16")
test.update(for: 7, with: 16)
print("Current tree after update")
test.display()
输出符合预期，值为 7 并与 16 交换
Updating 7 with 16
Current tree after update
** PRINTING BST IN LEVEL ORDER (BFS) **
5
4
11
16
17
当然，在这次交换之后，树不再是二叉搜索树，但我认为您可以看到指针在上述调整后运行良好。
我正在尝试更新自平衡二叉树。通常，您可以通过以下方式更新它：1) 搜索节点，2) 删除它，3) 并插入带有新节点的树。但是，我想看看是否可以通过保留第一步中指向节点的指针并更新它来绕过删除和插入并提高时间复杂度，尤其是当涉及到大量节点时.
树本身就是标准的二叉搜索树。
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
}
我的想法是通过递归搜索树，当找到一个节点时，将其作为参数传递给闭包函数，最终将调用它来更新节点。此外，找到的节点将通过引用传递。
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)
问题是更新没有发生。如果我在树中搜索新更新的节点，它不存在。
更新
以上代码是Red-Black tree的修改版，具体修改了搜索方法，改为使用指针。
我在下面的二叉搜索树的简化版本上尝试了我的想法，它似乎正在更新指定节点的值。
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)
}
}
}
在这里测试。
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
}
但似乎无法弄清楚为什么原始代码不通过指针更新节点。
对我来说，我在评论中提到的主要问题是这些代码行
fileprivate(set) var root: Node
fileprivate let nullLeaf = Node()
public init() {
root = nullLeaf
}
Root 当前指向 nullLeaf，它具有以下属性：
key = nil
leftChild = nil
self.rightChild = nil
self.parent = nil
我不确定你的插入函数是如何实现的，但是当我使用我的插入实现时，这将根的属性更新为以下内容：
key = nil
leftChild = node
self.rightChild = nil
self.parent = nil
现在，当您 运行 您的 search 函数从根开始时：
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 { 是错误的，因此它会进入执行逻辑和完成处理程序的块。
更改和实施
因为你要回答的主要问题是
But can't seem to figure out why the original code isn't updating a node by pointer.
我正在使用我的二叉搜索树的插入实现，尽管你提到二叉树的主要目的是显示指针工作。
这是我对您的代码更新的内容：
TreeNode - 没有更改您的代码
// 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
}
}
树 - 小改动和一些补充，我添加了评论
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)
}
}
}
}
}
测试 class - 没有太大变化
// 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()
}
}
最后是主要内容
测试 1 - 简单，有 1 个节点
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()
输出
Test 1
Inserting 10
Updating 10 with 8
** PRINTING BST IN LEVEL ORDER (BFS) **
8
如您所见，值交换已成功与指针发生
测试 2 - 具有许多节点的更复杂的树
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()
这应该给我们一个像这样的二叉搜索树：
打印 BFS 遍历向我们展示了这一点：
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
现在让我们尝试将 7 的值更改为 16，这是通过指针完成的
print("Updating 7 with 16")
test.update(for: 7, with: 16)
print("Current tree after update")
test.display()
输出符合预期，值为 7 并与 16 交换
Updating 7 with 16
Current tree after update
** PRINTING BST IN LEVEL ORDER (BFS) **
5
4
11
16
17
当然，在这次交换之后，树不再是二叉搜索树，但我认为您可以看到指针在上述调整后运行良好。