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/rbtree.go | |
parent | 27401b6ea459921a6152ab1744da1618358465f4 (diff) |
Add license and copyright info
Diffstat (limited to 'lib/rbtree/rbtree.go')
-rw-r--r-- | lib/rbtree/rbtree.go | 10 |
1 files changed, 10 insertions, 0 deletions
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 |