ํธ๋ฆฌ Tree
- ๋ถ๋ชจ ์์์ด ์๋ ๊ตฌ์กฐ
- ๊ณ์ธต์ด ์๊ณ , ๊ทธ๋ฃน์ด ์๋ค.
- ๋์ด์ ์์์ด ์๋ ๋ง์ง๋ง ๋
ธ๋๋ฅผ
leaf
๋ผ๊ณ ๋ถ๋ฅธ๋ค.
๐ณ ํธ๋ฆฌ์ ์ข
๋ฅ
- ์์ ๋
ธ๋๊ฐ ์ต๋ 2๊ฐ๊น์ง๋ง ๋ถ๋ ํธ๋ฆฌ
- 3๊ฐ์ฉ ๋ถ๋ ํธ๋ฆฌ (Ternary tree), 4๊ฐ์ฉ ๋ถ๋ ํธ๋ฆฌ๋ ์๋ค.
- ๋ค๋ฅธ ๋
ธ๋ ์กฐ๊ฑด์์.
์ด์ง ํ์ ํธ๋ฆฌ Binary Search Tree
- ์ผ์ชฝ ๋
ธ๋์ ๊ทธ ์ดํ ์์ ๋
ธ๋๋ค์ ์ค๋ฅธ์ชฝ ๋
ธ๋๋ณด๋ค ๋ ์์์ผ ํ๋ค.
Balaced / Unbalanced
- ์ผ์ชฝ ์ค๋ฅธ์ชฝ ๋
ธ๋์ ๋ถํฌ๊ฐ ๋๋ฌด ํ์ชฝ์ผ๋ก ์ ๋ฆฌ์ง ์์๋ค๋ฉด, Balaced
- red-black tree
- AVL tree
์์ ์ด์ง ํธ๋ฆฌ Complete Binary Tree
- ๋ชจ๋ ๋
ธ๋๋ค์ด ๋ ๋ฒจ๋ณ๋ก ์ผ์ชฝ๋ถํฐ ์ฑ์์ ธ ์์ผ๋ฉด ์์ ์ด์ง ํธ๋ฆฌ
- ๋ง์ง๋ง ๋ ๋ฒจ์ ์ ์ธํ ๋ชจ๋ ๋ ๋ฒจ์ด ๋ค ์ฑ์์ ธ์๊ณ , ๋ง์ง๋ง ๋ ๋ฒจ์ ์ผ์ชฝ๋ถํฐ ์ฑ์ฐ๊ธฐ
Full Binary Tree
- ๋
ธ๋์ ์์์ด ์๋ค๋ฉด ํ๋์ ์์๋ง ์์ผ๋ฉด ์๋๋ค. ์์์ด ๋ ์ด๊ฑฐ๋ 0์ด๊ฑฐ๋.
Perfect Binary Tree
- ์๋ฒฝํ ํผ๋ผ๋น๋ ํํ์ ์ด์ง ํธ๋ฆฌ
- ๋ ๋ฒจ์ด n์ผ ๋, ๋
ธ๋๊ฐ 2^n-1๊ฐ ์๋ค.
๐ ํธ๋ฆฌ ๋ง๋ค๊ธฐ
๋
ธ๋ Node
class Node {
int data;
Node left;
Node right;
}
ํธ๋ฆฌ Tree
class Tree {
public Node root;
public Node makeNode(Node left, int data, Node right) {
Node node = new Node();
node.data = data;
node.left = left;
node.right = right;
return node;
}
}
๊ทธ๋ํ ๊ทธ๋ฆฌ๊ธฐ
- ๋ฐ์์๋ถํฐ ๊ทธ๋ฆฌ์
Tree t = new Tree();
Node n4 = t.makeNode(null, 4, null);
Node n5 = t.makeNode(null, 5, null);
Node n2 = t.makeNode(n4, 2, n5);
Node n3 = t.makeNode(null, 3, null);
Node n1 = t.makeNode(n2, 1, n3);
t.setRoot(n1);
๐ฟ ๊ด๋ จ ๋ฌธ์
๐๏ธ ์ฐธ๊ณ