DataStructure: Tree

new-powยท2022๋…„ 11์›” 8์ผ
0

ํŠธ๋ฆฌ Tree

  • ๋ถ€๋ชจ ์ž์‹์ด ์žˆ๋Š” ๊ตฌ์กฐ
  • ๊ณ„์ธต์ด ์žˆ๊ณ , ๊ทธ๋ฃน์ด ์žˆ๋‹ค.
  • ๋”์ด์ƒ ์ž์‹์ด ์—†๋Š” ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ๋ฅผ leaf๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

๐ŸŒณ ํŠธ๋ฆฌ์˜ ์ข…๋ฅ˜

โญ๏ธ ์ด์ง„ํŠธ๋ฆฌ Binary Tree

  • ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ 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

  • 2์ง„ ํŠธ๋ฆฌ ๋…ธ๋“œ
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);

๐Ÿ‘ฟ ๊ด€๋ จ ๋ฌธ์ œ


๐Ÿ–‡๏ธ ์ฐธ๊ณ 

profile
์ €๋Š” ๋ธ”๋กœ๊ทธ ์ด์‚ฌ๋ฅผ ๊ฐ”์Šต๋‹ˆ๋‹ค

0๊ฐœ์˜ ๋Œ“๊ธ€