[์ž๋ฃŒ๊ตฌ์กฐ] Tree ๊ตฌ์กฐ(2)

2021. 8. 29. 08:00ใ†์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ์ค€๋น„/์ž๋ฃŒ๊ตฌ์กฐ

728x90
๋ฐ˜์‘ํ˜•

์•ˆ๋…•ํ•˜์„ธ์š”? ์ฃผ๋‹ˆํ•˜๋ž‘ ์ž…๋‹ˆ๋‹ค.

์˜ค๋Š˜์€ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ Tree ๊ตฌ์กฐ ๋‘๋ฒˆ์งธ ๊ณต๋ถ€๋ฅผ ์‹œ์ž‘ ํ•ด ๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค!

์†Œ์Šค ์ฝ”๋“œ์— ๋Œ€ํ•ด์„œ ํ™•์ธ ํ•˜๊ณ  ์‹ถ์œผ์‹  ๋ถ„๋“ค๊ป˜์„œ๋Š” ์ฃผ๋‹ˆํ•˜๋ž‘์˜ Git hub์— ๊ด€์‹ฌ์„ ์ฃผ์„ธ์š”!

๋ณธ ํ”ผ๋“œ๋Š” [์ž๋ฃŒ๊ตฌ์กฐ] Tree ๊ตฌ์กฐ(1)์˜ ์—ฐ์žฅ์ด๋ฉฐ, ํ•ด๋‹น ํ”ผ๋“œ๋ฅผ ๋จผ์ € ํ™•์ธํ•˜์‹œ๊ณ , ์ด ํ”ผ๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋Š” ๊ฑธ ์ถ”์ฒœ ๋“œ๋ฆด๊ฒŒ์š”!





 

 

๐Ÿ“Œ Binary Search Tree Node Delete (์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ ๋…ธ๋“œ ์‚ญ์ œ)


 

    ๐Ÿ“ Case 3-1 

           ๐Ÿ‘‰์‚ญ์ œํ•  Node๊ฐ€ Child Node๋ฅผ ๋‘ ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ์„ ๊ฒฝ์šฐ (์‚ญ์ œํ•  Node๊ฐ€ Parent Node ์™ผ์ชฝ์— ์žˆ์„ ๋•Œ)

  • ๊ธฐ๋ณธ ์‚ฌ์šฉ ์ „๋žต
    1. ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์‚ญ์ œํ•  Node์˜ Parent Node๊ฐ€ ๊ฐ€๋ฅดํ‚ค๋„๋ก ํ•œ๋‹ค.
    2. ์‚ญ์ œํ•  Node์˜ ์™ผ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ์‚ญ์ œํ•  Node์˜ Parent Node๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋„๋ก ํ•œ๋‹ค.
  • ๊ธฐ๋ณธ ์‚ฌ์šฉ ๊ฐ€๋Šฅ ์ „๋žต ์ค‘, 1๋ฒˆ ์ „๋žต์„ ๊ฐ€์ง€๊ณ  Code ๊ตฌํ˜„
    • ๊ทธ ์•ˆ์— ๋˜ ๋‹ค๋ฅธ ๊ฒฝ์šฐ์˜ ์ˆ˜
      • Case 3-1-1 : ์‚ญ์ œํ•  Node๊ฐ€ Parent Node์˜ ์™ผ์ชฝ์— ์žˆ๊ณ , ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ Child Node๊ฐ€ ์—†์„ ๋•Œ
      • Case 3-1-2: ์‚ญ์ œํ•  Node๊ฐ€ Parent Node์˜ ์™ผ์ชฝ์— ์žˆ๊ณ , ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ ์˜ค๋ฅธ์ชฝ์— Child Node๊ฐ€ ์žˆ์„ ๋•Œ
        • ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ Child Node๊ฐ€ ์™ผ์ชฝ์— ์žˆ์„ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค ์™œ๋ƒํ•˜๋ฉด ์™ผ์ชฝ Node๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ํ•ด๋‹น Node๋ณด๋‹ค ๋” ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ

 

 

 

 

 

        if self.current_node.lefe != None and self.current_node.right = None:   # Case 3์— ๋Œ€ํ•œ ๋‚ด์šฉ
            if value < self.parent.value:                                       # Case 3-1์— ๋Œ€ํ•œ ๋‚ด์šฉ
                self.change_node = self.current_node.right
                self.change_node_parent = self.change_node.right

                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left

                if self.change_node.right != None:                               # Case 3-1-1์— ๋Œ€ํ•œ ๋‚ด์šฉ
                    self.change_node_parent.left = self.change_node.right

                else:
                    self.change_node_parent.left = None

                self.parent.left = self.current_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left

 

 

 

    ๐Ÿ“ Case 3-2

           ๐Ÿ‘‰์‚ญ์ œํ•  Node๊ฐ€ Child Node๋ฅผ ๋‘ ๊ฐœ ๊ฐ€์ง€๊ณ  ์žˆ์„ ๊ฒฝ์šฐ (์‚ญ์ œํ•  Node๊ฐ€ Parent Node ์˜ค๋ฅธ์ชฝ์— ์žˆ์„ ๋•Œ)

 

  • ๊ธฐ๋ณธ ์‚ฌ์šฉ ์ „๋žต
    1. ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์‚ญ์ œํ•  Node์˜ Parent Node๊ฐ€ ๊ฐ€๋ฅดํ‚ค๋„๋ก ํ•œ๋‹ค.
    2. ์‚ญ์ œํ•  Node์˜ ์™ผ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ์‚ญ์ œํ•  Node์˜ Parent Node๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋„๋ก ํ•œ๋‹ค.
  • ๊ธฐ๋ณธ ์‚ฌ์šฉ ๊ฐ€๋Šฅ ์ „๋žต ์ค‘, 1๋ฒˆ ์ „๋žต์„ ๊ฐ€์ง€๊ณ  Code ๊ตฌํ˜„
    • ๊ทธ ์•ˆ์— ๋˜ ๋‹ค๋ฅธ ๊ฒฝ์šฐ์˜ ์ˆ˜
      • Case 3-2-1 : ์‚ญ์ œํ•  Node๊ฐ€ Parent Node์˜ ์˜ค๋ฅธ์ชฝ์— ์žˆ๊ณ , ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ Child Node๊ฐ€ ์—†์„ ๋•Œ
      • Case 3-2-2: ์‚ญ์ œํ•  Node๊ฐ€ Parent Node์˜ ์˜ค๋ฅธ์ชฝ์— ์žˆ๊ณ , ์‚ญ์ œํ•  Node์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ์ค‘, ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ ์˜ค๋ฅธ์ชฝ์— Child Node๊ฐ€ ์žˆ์„ ๋•Œ
        • ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node์˜ Child Node๊ฐ€ ์™ผ์ชฝ์— ์žˆ์„ ๊ฒฝ์šฐ๋Š” ์—†๋‹ค ์™œ๋ƒํ•˜๋ฉด ์™ผ์ชฝ Node๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ํ•ด๋‹น Node๋ณด๋‹ค ๋” ์ž‘์€ ๊ฐ’์„ ๊ฐ€์ง„ Node๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ

 

 

 

 

            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right

                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left

                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right

                else:
                    self.change_node_parent.left = None

                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

 

 

๐Ÿ™‹๐Ÿป‍โ™‚๏ธ ์ „์ฒด ์ฝ”๋“œ๋Š” ์ฃผ๋‹ˆํ•˜๋ž‘ Git hub์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

์ฐธ๊ณ ํ•˜๋ฉด ์ข‹์€ ๊ณณ : http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html

 

Eunji Kim @ CAU - ํŒŒ์ด์ฌ์„ ์‚ฌ์šฉํ•œ ์ด์ง„ ํŠธ๋ฆฌ์™€ ์ˆœํšŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„ (1)

์ด์ง„ ํŠธ๋ฆฌ (binary tree)๋Š” ์ตœ๋Œ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ์„œ, ๋‹จ์ˆœํžˆ ๊ฐ’์„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ์šฉ๋„๋กœ ์‚ฌ์šฉ๋˜๊ธฐ ๋ณด๋‹ค๋Š” ํšจ์œจ์ ์ธ ํƒ์ƒ‰ ํ˜น์€ ์ •๋ ฌ์„ ์œ„ํ•ด ์‚ฌ์šฉ๋œ๋‹ค. ์ด์ง„ ํƒ์ƒ‰

ejklike.github.io

 

 

 

๐Ÿ“Œ Python All Code Test


  • Use the random Library
    • random.randint(์ฒซ๋ฒˆ์งธ ์ˆซ์ž, ๋งˆ์ง€๋ง‰ ์ˆซ์ž): ์ฒซ๋ฒˆ์งธ ์ˆซ์ž๋ถ€ํ„ฐ ๋งˆ์ง€๋ง‰ ์ˆซ์ž ์‚ฌ์ด ๊ฐ’๋“ค์„ Randomํ•˜๊ฒŒ ์„ ํƒํ•˜์—ฌ ๋ฐ˜ํ™˜
      • ์˜ˆ: random.randint(0, 99) 0 ~ 99๊นŒ์ง€ ์ˆซ์ž ์ค‘ ํŠน์ • ์ˆซ์ž Random ์„ ํƒ ๋ฐ˜ํ™˜

 

# 0 - 999 ์ˆ˜์ž ์ค‘ ์ž„์˜๋กœ 100๊ฐœ๋ฅผ ์ถ”์ถœํ•˜์—ฌ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ์ž…๋ ฅํ•˜๊ณ , ๊ฒ€์ƒ‰, ์‚ญ์ œ ํ•ด ๋ณด๊ธฐ
bst_nums = set()

while len(bst_nums) != 100:
    bst_nums.add(random.randint(0, 999))  # Randdom Library๋ฅผ ํ™œ์šฉํ•˜์—ฌ 0 ~ 999๊นŒ์ง€ ์ •์ˆ˜ ๋งŒ๋“ค์–ด ์ค‘๋ณต์„ ์ธ์ •ํ•˜์ง€ ์•Š๋Š” set ์ง‘ํ•ฉ์— ๋„ฃ๊ธฐ

# ์„ ํƒ๋œ 100๊ฐœ์˜ ์ˆซ์ž๋ฅผ ์ด์ง„ ํƒ์ƒ‰ Tree์— ์ž…๋ ฅ, ์ž„์˜๋กœ Root Node๋Š” 500์œผ๋กœ ๋„ฃ๊ธฐ๋กœ ํ•œ๋‹ค.
head = Node(500)
binary_search_tree = NodeMgmt(head)
for num in bst_nums:
    binary_search_tree.insert(num)

# ์ž…๋ ฅํ•œ 100๊ฐœ์˜ ์ˆซ์ž ๊ฒ€์ƒ‰ (๊ฒ€์ƒ‰ ๊ธฐ๋Šฅ ํ™•์ธ)
for num in bst_nums:
    if binary_search_tree.search(num) == False:
        print("๊ฒ€์ƒ‰์ด ์‹คํŒจ ํ•˜์˜€์Šต๋‹ˆ๋‹ค!", num)

    else:
        print("๊ฒ€์ƒ‰์— ์„ฑ๊ณต ํ•˜์˜€์Šต๋‹ˆ๋‹ค!", num)

print("=" * 100)

# ์ž…๋ ฅํ•œ 100๊ฐœ์˜ ์ˆซ์ž ์ค‘ 50๊ฐœ์˜ ์ˆซ์ž๋ฅผ Random ์„ ํƒํ•˜์—ฌ ์‚ญ์ œ
delete_nums = set()
bst_nums = list(bst_nums)

while len(delete_nums) != 50:
    delete_nums.add(bst_nums[random.randint(0, 99)])

# ์„ ํƒํ•œ 50๊ฐœ์˜ ์ˆซ์ž๋ฅผ ์‚ญ์ œ (์‚ญ์ œ ๊ธฐ๋Šฅ ํ™•์ธ)
for del_num in delete_nums:
    if binary_search_tree.delete(del_num) == False:
        print("์‚ญ์ œ ์‹คํŒจํ•˜์˜€์Šต๋‹ˆ๋‹ค!", del_num)

    else:
        print("์‚ญ์ œ ์„ฑ๊ณตํ•˜์˜€์Šต๋‹ˆ๋‹ค!", del_num)

 

 

 

 

 

 

๐Ÿ“Œ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„์™€ ๋‹จ์ 


    ๐Ÿ“ ์‹œ๊ฐ„ ๋ณต์žก๋„(ํƒ์ƒ‰์‹œ)

  • depth(ํŠธ๋ฆฌ์˜ ๊นŠ์ด)๋ฅผ h๋ผ๊ณ  ํ‘œ๊ธฐํ•  ๋•Œ, $O(h)$๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค.
  • n๊ฐœ์˜ Node๋ฅผ ๊ฐ€์ง„๋‹ค๋ฉด, $h = log2n$์— ๊ฐ€๊น๊ธฐ ๋•Œ๋ฌธ์—, ์‹œ๊ฐ„๋ณต์žก๋„๋Š” $O(logn)$
    • ์ฐธ๊ณ  : ๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•์—์„œ $logn$์—์„œ์˜ $log$์˜ ๋ฐ‘์€ 10์ด ์•„๋‹ˆ๊ณ , 2์ด๋‹ค.
      • ํ•œ๋ฒˆ ์‹คํ–‰์‹œ๋งˆ๋‹ค, 50%์˜ ์‹คํ–‰ํ•  ํ–‰์œ„๋ฅผ ์ œ๊ฑฐํ•œ๋‹ค๋Š” ์˜๋ฏธ. ์ฆ‰, 50%์˜ ์‹คํ–‰์‹œ๊ฐ„์„ ๋‹จ์ถ•ํ•  ์ˆ˜ ์žˆ๋‹ค.

 

์ถœ์ฒ˜ : https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

 

 

    ๐Ÿ“ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ ๋‹จ์ 

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ํ‰๊ท  ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $O(logn)$์ด์ง€๋งŒ, ์ด๊ฒƒ์€ ํŠธ๋ฆฌ๊ฐ€ ๊ท ํ˜•์ด ์žกํ˜€ ์žˆ์„ ๋•Œ์˜ ์ด์•ผ๊ธฐ์ธ ๊ฒƒ์ด์—์š”.

์•„๋ž˜์™€ ๊ฐ™์ด ์•„์ฃผ ์˜ˆ์˜๊ฒŒ ์ญ‰ ๋ป—์–ด ๋‚˜๊ฐ„๋‹ค๋ฉด ๊ทธ๊ฒƒ์€ ๋ฐฐ์—ด์ด๋‚˜, ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์™€ ๋‹ค๋ฅผ๋ฐ”๊ฐ€ ์—†์–ด์ง„๋‹ต๋‹ˆ๋‹ค!

 

์ด๋Ÿฐ ๊ฒฝ์šฐ ์ด๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ๋”ฐ๋กœ ์žˆ๋Š” ๊ฒƒ์ด์—์š”!

๋˜ํ•œ ์œ„์™€ ๊ฐ™์ด ๊ตฌ์„ฑ์ด ๋˜๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” $(O(n))$์ด ๋˜์–ด ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์ด์—์š”.

 

 

 


 

 

์ฃผ๋‹ˆํ•˜๋ž‘์˜ ๊ธ€์ด ๋งˆ์Œ์— ๋“œ์…จ๋‚˜์š”? ๊ตฌ๋…๊ณผ ๊ณต๊ฐ! ๊ทธ๋ฆฌ๊ณ , ๋Œ“๊ธ€์€ ์ฃผ๋‹ˆํ•˜๋ž‘์—๊ฒŒ ๋งŽ์€ ํž˜์ด ๋ฉ๋‹ˆ๋‹ค

 

728x90
๋ฐ˜์‘ํ˜•