From 78a6a912cff60f03dea4b285a439056089f7c102 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 10 Jul 2022 13:11:55 -0600 Subject: Add license and copyright info --- lib/rbtree/print_test.go | 4 ++++ lib/rbtree/rbtree.go | 10 ++++++++++ lib/rbtree/rbtree_test.go | 4 ++++ lib/rbtree/rbtree_util.go | 4 ++++ 4 files changed, 22 insertions(+) (limited to 'lib/rbtree') diff --git a/lib/rbtree/print_test.go b/lib/rbtree/print_test.go index 3e37cf2..fe2d2bd 100644 --- a/lib/rbtree/print_test.go +++ b/lib/rbtree/print_test.go @@ -1,3 +1,7 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + package rbtree import ( diff --git a/lib/rbtree/rbtree.go b/lib/rbtree/rbtree.go index 7927307..0353e75 100644 --- a/lib/rbtree/rbtree.go +++ b/lib/rbtree/rbtree.go @@ -1,3 +1,7 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + package rbtree import ( @@ -285,6 +289,9 @@ func (t *Tree[K, V]) Insert(val V) { } // Re-balance + // + // This is closely based on the algorithm presented in CLRS + // 3e. for node.Parent.getColor() == Red { if node.Parent == node.Parent.Parent.Left { @@ -337,6 +344,9 @@ func (t *Tree[K, V]) Delete(key K) { return } + // This is closely based on the algorithm presented in CLRS + // 3e. + var nodeToRebalance *Node[V] var nodeToRebalanceParent *Node[V] // in case 'nodeToRebalance' is nil, which it can be needsRebalance := nodeToDelete.Color == Black diff --git a/lib/rbtree/rbtree_test.go b/lib/rbtree/rbtree_test.go index 9b8e02c..9e9a734 100644 --- a/lib/rbtree/rbtree_test.go +++ b/lib/rbtree/rbtree_test.go @@ -1,3 +1,7 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + package rbtree import ( diff --git a/lib/rbtree/rbtree_util.go b/lib/rbtree/rbtree_util.go index 252d8fe..cee5508 100644 --- a/lib/rbtree/rbtree_util.go +++ b/lib/rbtree/rbtree_util.go @@ -1,3 +1,7 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + package rbtree import ( -- cgit v1.2.3-2-g168b