Repository: yorkie-team/yorkie
Pull request #162 (2021-03-19 14:47:06)

Fix invalid states of SplayTree when deleting a node
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

Fix invalid states of SplayTree when deleting a node.

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Fixes #

**Special notes for your reviewer**:

This PR is that reflects [the bug fix](https://github.com/yorkie-team/yorkie-js-sdk/pull/153) resolved in JS SDK.

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note

```

**Additional documentation**:

<!--
This section can be blank if this pull request does not require a release note.

Please use the following format for linking documentation:
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```

**Checklist**:
- [x] Added relevant tests or not required
- [x] Didn't break anything


codecov[bot]: # [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=h1) Report
> Merging [#162](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=desc) (4940273) into [main](https://codecov.io/gh/yorkie-team/yorkie/commit/6b1c9bcb32c0f853e19c343afffe2bdf79fdbba9?el=desc) (6b1c9bc) will **increase** coverage by `0.59%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/yorkie-team/yorkie/pull/162/graphs/tree.svg?width=650&height=150&src=pr&token=P6COB1ZNIC)](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##             main     #162      +/-   ##
==========================================
+ Coverage   58.75%   59.34%   +0.59%     
==========================================
  Files          37       37              
  Lines        3280     3289       +9     
==========================================
+ Hits         1927     1952      +25     
+ Misses       1166     1151      -15     
+ Partials      187      186       -1     
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pkg/splay/splay.go](https://codecov.io/gh/yorkie-team/yorkie/pull/162/diff?src=pr&el=tree#diff-cGtnL3NwbGF5L3NwbGF5Lmdv) | `63.35% <100.00%> (+12.69%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=footer). Last update [6b1c9bc...4940273](https://codecov.io/gh/yorkie-team/yorkie/pull/162?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index 1103312b..116d5f8b 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -75,6 +75,16 @@ func (n *Node) increaseWeight(weight int) {
 	n.weight += weight
 }
 
+func (n *Node) unlink() {
+	n.parent = nil
+	n.right = nil
+	n.left = nil
+}
+
+func (n *Node) hasLinks() bool {
+	return n.parent != nil || n.left != nil || n.right != nil
+}
+
 // Tree is weighted binary search tree which is based on Splay tree.
 // original paper on Splay Trees:
 //  - https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
@@ -154,7 +164,7 @@ func (t *Tree) Splay(node *Node) {
 
 // IndexOf Find the index of the given node.
 func (t *Tree) IndexOf(node *Node) int {
-	if node == nil {
+	if node == nil || !node.hasLinks() {
 		return -1
 	}
 
@@ -253,10 +263,18 @@ func (t *Tree) Delete(node *Node) {
 		maxNode := leftTree.maximum()
 		leftTree.Splay(maxNode)
 		leftTree.root.right = rightTree.root
+		if rightTree.root != nil {
+			rightTree.root.parent = leftTree.root
+		}
 		t.root = leftTree.root
 	} else {
 		t.root = rightTree.root
 	}
+
+	node.unlink()
+	if t.root != nil {
+		t.UpdateSubtree(t.root)
+	}
 }
 
 func (t *Tree) rotateLeft(pivot *Node) {


Test patch:
diff --git a/pkg/splay/splay_test.go b/pkg/splay/splay_test.go
index 8e517bf3..1c03f4a9 100644
--- a/pkg/splay/splay_test.go
+++ b/pkg/splay/splay_test.go
@@ -75,4 +75,25 @@ func TestSplayTree(t *testing.T) {
 		assert.Equal(t, nodeD, node)
 		assert.Equal(t, 2, offset)
 	})
+
+	t.Run("deletion test", func(t *testing.T) {
+		tree := splay.NewTree(nil)
+
+		nodeH := tree.Insert(newSplayNode("H"))
+		assert.Equal(t, "[1,1]H", tree.AnnotatedString())
+		nodeE := tree.Insert(newSplayNode("E"))
+		assert.Equal(t, "[1,1]H[2,1]E", tree.AnnotatedString())
+		nodeL := tree.Insert(newSplayNode("LL"))
+		assert.Equal(t, "[1,1]H[2,1]E[4,2]LL", tree.AnnotatedString())
+		nodeO := tree.Insert(newSplayNode("O"))
+		assert.Equal(t, "[1,1]H[2,1]E[4,2]LL[5,1]O", tree.AnnotatedString())
+
+		tree.Delete(nodeE)
+		assert.Equal(t, "[4,1]H[3,2]LL[1,1]O", tree.AnnotatedString())
+
+		assert.Equal(t, tree.IndexOf(nodeH), 0)
+		assert.Equal(t, tree.IndexOf(nodeE), -1)
+		assert.Equal(t, tree.IndexOf(nodeL), 1)
+		assert.Equal(t, tree.IndexOf(nodeO), 3)
+	})
 }