Splay Tree (2) - find, insert, delete, 최솟값 최댓값 찾기

안녕하세요.

Splay Tree 연산 중 find, insert, delete, 그리고 최솟값 최댓값 찾기를 알아보겠습니다.

---

Binary Tree

이진 트리라서 아래 연산이 가능합니다.

• find
• insert
• delete
• 최솟값, 최댓값 찾기

---

Find

key 값이 Tree에 있는지 없는지를 확인합니다.

 

BST의 특징을 이용해 값을 찾아 나가면 됩니다.

• node x의 value == key -> 탐색 종료
• node x의 value < key -> right child of node x 로 이동
• node x의 value > key -> left child of node x 로 이동

탐색이 종료됐으면, 마지막으로 access한 노드를 루트로 올려줍니다.

 

아래 두 그림은 각각 7과 2를 find 한 뒤의 Splay Tree의 모습입니다.

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

struct SplayTree {
	Node* root;

	void splay(Node* x) {
		...
	}

	bool find(ll key) {
		Node* x = root;
		if (!x) return false;

		while (x) {
			if (x->key == key) break;

			Node* next = (x->key < key ? x->right : x->left);
			if (!next) break;
			x = next;
		}

		splay(x);
		return x->key == key;
	}

	void insert(ll key) {
		...
	}

	void del(ll key) {
		...
	}
};

---

Insert

Tree에 특정 key 값을 넣는 연산 입니다.

마지막으로, 삽입된 노드를 루트로 올려줍니다.

 

9를 insert 한 뒤의 Splay Tree의 모습입니다.

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

struct SplayTree {
	Node* root;

	void splay(Node* x) {
		...
	}

	bool find(ll key) {
		...
	}

	void insert(ll key) {
		Node* newNode = new Node(key);
		Node* x = root;

		while (x) {
			if (x->key < key) {
				if (!x->right) {
					x->right = newNode;
					break;
				}

				x = x->right;
			}
			else {
				if (!x->left) {
					x->left = newNode;
					break;
				}

				x = x->left;
			}
		}

		newNode->parent = x;
		splay(newNode);
	}

	void del(ll key) {
		...
	}
};

---

Delete

Tree에서 key에 해당하는 노드를 삭제하는 연산입니다.

 

먼저, 삭제할 노드를 루트로 올려줍니다.

루트를 지운 뒤, 아래 case에 맞게 제거해줍니다.

• 자식이 0개
  • 트리가 비었다는 의미
  • 아무것도 안해도 됨
• 자식이 1개
  • 유일한 자식을 루트 자리로 올려주면 됨
• 자식이 2개
  • 두 서브트리를 이어붙여야 함
  • 왼쪽 서브트리를 루트 자리로 올려줌
  • 왼쪽 서브트리의 제일 값이 큰 노드의 right child를 오른쪽 서브트리로 이어줌

 

8을 delete 한 뒤의 Splay Tree의 모습입니다.

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

struct SplayTree {
	Node* root;

	void splay(Node* x) {
		...
	}

	bool find(ll key) {
		...
	}

	void insert(ll key) {
		...
	}

	void del(ll key) {
		if (!find(key)) return;
		Node* x = root;

		if (x->left && x->right) {
			root = x->left;
			x->left->parent = NULL;

			Node* r = root;
			while (r->right) r = r->right;

			r->right = x->right;
			x->right->parent = r;
		}
		else if (x->left) {
			root = x->left;
			x->left->parent = NULL;
		}
		else if (x->right) {
			root = x->right;
			x->right->parent = NULL;
		}

		delete x;
	}
}ST;

---

최솟값, 최댓값 찾기

BST의 특성에 따라

• 제일 왼쪽 노드를 가면 제일 작은 값,
• 제일 오른쪽 노드를 가면 제일 큰 값이 나옴

---

문제

https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

---

참고 자료

https://justicehui.github.io/hard-algorithm/2018/11/13/SplayTree2/

Splay Tree - 2