diff options
| author | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-10 13:11:55 -0600 |
|---|---|---|
| committer | Luke Shumaker <lukeshu@lukeshu.com> | 2022-07-10 14:25:45 -0600 |
| commit | 78a6a912cff60f03dea4b285a439056089f7c102 (patch) | |
| tree | 8e08a1bc532d5fe06d3336763795219c36e9a20d /lib/rbtree | |
| parent | 27401b6ea459921a6152ab1744da1618358465f4 (diff) | |
Add license and copyright info
Diffstat (limited to 'lib/rbtree')
| -rw-r--r-- | lib/rbtree/print_test.go | 4 | ||||
| -rw-r--r-- | lib/rbtree/rbtree.go | 10 | ||||
| -rw-r--r-- | lib/rbtree/rbtree_test.go | 4 | ||||
| -rw-r--r-- | lib/rbtree/rbtree_util.go | 4 |
4 files changed, 22 insertions, 0 deletions
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 <lukeshu@lukeshu.com> +// +// 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 <lukeshu@lukeshu.com> +// +// 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 <lukeshu@lukeshu.com> +// +// 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 <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + package rbtree import ( |