python binary search tree
Data Structure python

【Python】Binary Search Tree (二元搜尋樹) 資料結構實作(1)

clickup

前言

上次寫完 【Python】Stack(堆疊) 資料結構實作 得到了不錯的迴響

這是要來寫寫有關 Binary Search Tree (二元搜尋樹)

希望大家不要聽到有關「Tree」的資料結構就望而生畏

且聽我在此娓娓道來

本篇文章會帶到以下幾點有關Binary Search Tree該知道的事:

  1. BST 的 基本概念
  2. BST 的 Big-O
  3. Python 實作 BST (加入 node & 印出 tree

你可能會喜歡:【2020】我的Python學習心路歷程

二元樹基本概念

二元樹就是由多個node組成

而BST就是以 node-based 為基礎的資料結構,當中要注意到BST有以下幾點特性:

  1. node左子樹只會包含比本身還要小得值
  2. node的右子樹只會包含比自己大的node
  3. 每個左右子樹都要是二元搜尋樹
  4. 不可以有值重複的 node

BST Big-O

AverageWorst Case
Space 空間O(n)O(n)
Access 存取O(log n)O(n)
Search 搜尋O(log n)O(n)
Insertion 加入資料O(log n)O(n)
Deletion 刪除資料O(log n)O(n)
圖1. 就是一個標準的BST
圖2. leaf node: 沒有 child node 的 node,根據上面這張圖共有四個leaf nodes
圖3. Height: 用Height可以計算出一個binary tree最多有幾個node,從root最上層為level 1,往下為level 2,以此類推

ex: Level 4 的Binary tree 最多可以有 2^4 – 1 = 15 個 node

以上的二元搜尋樹提供了node之間的順序,因此可以快速完成搜索,最小,最大等操作。如果沒有排序,我們就必需比較所有的鍵(key)來搜尋給定的鍵

Full Binary Tree

圖4
  • 所有node都有兩個subtree 子樹 (也就是兩個child pointer);
  • 所有leaf node具有相同的level(或相同的height)
  • 計算結點數公式為:2^n – 1

ex: Level 4 的 Full Binary tree 一定有 2^4 – 1 = 15 個 node

Complete Binary Tree

一棵樹的node按照Full Binary Tree的次序排列(由上至下,由左至右),則稱此樹為Complete Binary Tree

圖5

圖6 Node(M)應該要移到 Node(F)的右子樹,因此下圖並沒有滿足Complete Binary Tree的特性

圖6

搜尋二元樹

數一定是從root開始找起,不論是刪除,新增等等

圖7

我們將從一個’n’個節點的搜尋Space開始,當我們丟棄(discard)一個子樹時,我們將丟棄’n / 2’個節點,因此我們的搜索Space將減少為’n / 2’個,然後在下一個步驟我們將搜索空間減少到’n / 4’,然後繼續像這樣減少直到找到元素(element) 或直到我們的搜尋減少到一個節點(node)為止

新增node

圖8

由圖8可知 Node 會先比較 目前的node 如Node(21)

當Node(28) 大於 Node(21) 且 Node(21) 沒有右子樹時 Node(21) 的 右子樹 就會指向 Node(28) 以此類推

你可能會喜歡:【Python】Stack(堆疊) 資料結構實作

Python 實作 BST 二元搜尋樹

首先我們要先建立2個class來讓二搜尋樹動起來

我們要先建立一個 Class Node

將 instructor初始化

一個 node 可以儲存 value ,還有指向 left_childright_child 初始化都指向 None (因為都還沒有資料)

class Node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None #smaller
        self.right_child = None #greater

接著要來正式建立 二搜樹的Class了

二搜樹的Class 就好像是 Node 的 wrapper

負責控制 Node 的資料&該指向哪裡

而這個概念同 Linked List Class Node 跟 Class LinkedList 的關係

建立Class binary_search_tree

同理,一開始二搜樹內是沒有資料的所以將 instructor 初始化為 self.root = None

class binary_search_tree(self):
    def __init__(self):
        self.root = None

接著我們創建一個 insert() 的function
顧名思義就是讓我們加入資料
插入資料前我們要先檢查樹是否為空 if self.root == None
如果 root == None 代表樹是空的
因此 value 就等於 self.root

如果 root != None 的話
我們就呼叫 private function _insert()
⚠️實際上Python沒有所謂「真正的」private function,所以如果我們看到 _<function_name> 的時候,我們要避免在 Class 外呼叫private_function

接著在這個 _insert() 內要傳入 valueroot (我們正在查看的current Node)

為什麼要將一個function分成2個的原因是 _insert() 是 「遞迴的」用「一個function 來處理遞迴的事情」 會比 「讓所有邏輯處理都塞在 insert() 」裡來的好

class Binary_search_tree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        #判斷tree是否為空
        if self.root == None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

接著我們開使寫 _insert() 的 function
就像剛剛說的,在 _insert() 裡傳入 valuecur_node
而上面 self._insert(value, self.root) 傳入 root的原因是因為所有要新增的Node一定要經過 root

接下來我們就能開始比較「傳入的value 是否 大於 cur_node」了
再來,我們要分成兩個狀況
value < cur_node (value小於目前的node)
如果 cur_node.left_child == None 也就是目前的node「沒有」指向 left_child 的 pointer
理所當然 cur_node.left_child = Node(value)
如果 cur_node.left_child != None 也就是目前的node「有」指向 left_child 的 pointer
我們會把 left_child 當成 cur_node 並重新呼叫 _insert()

right_child 同理

最後 else 要處裡 value 與 cur_node 的 value相同的問題前面有提到,二搜樹的value是不能重複的

   def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = Node(value)
            else:
                self._insert(value, cur_node.left_child)
    
        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = Node(value)
            else:
               self._insert(value, cur_node.right_child)
                    
        # value == cur_node.value
        else:
            print("This value has existed")

你可能會喜歡:【2020】我的Python學習心路歷程

終於要把樹印出來了(茶
我們先檢查 self.root 是不是 Node
如果 self.root != None (也就是 self.root 有值
我們呼叫 _print_tree(self.root)
同理一樣是用「遞迴」的方式處理,所以將它寫成private function

def print_tree(self):
        if self.root != None:
            self._print_tree(self.root)

同樣印出一棵樹也是從root開始查找
所以cur_node設為self.root
所以 _print_tree(self, cur_node)

  def _print_tree(self, cur_node):
      if cur_node != None:
          self._print_tree(cur_node.left_child)
          print(str(cur_node.value))
          self._print_tree(cur_node.right_child)

最後在class外建立一個 function來幫我們自動建立一個二搜樹

def fill_tree(tree, num_elems=10, max_int=50):
    from random import randint
    for _ in range(num_elems): #10個 value
        cur_elem = randint(0, max_int) #隨機0~50(不含50)的值
        tree.insert(cur_elem)
    return tree

tree = Binary_search_tree()
tree = fill_tree(tree)

tree.print_tree()

執行結果

Python BST 完整程式碼

GitHub: https://github.com/LichtLiu/PG_Data_Structure/blob/main/Binary%20Search%20Tree/BinarySearchTree.py

class Node:
    def __init__(self, value=None):
        self.value = value
        self.left_child = None #smaller
        self.right_child = None #greater

class Binary_search_tree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        #判斷tree是否為空
        if self.root == None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, cur_node):
        if value < cur_node.value:
            if cur_node.left_child == None:
                cur_node.left_child = Node(value)
            else:
                self._insert(value, cur_node.left_child)

        elif value > cur_node.value:
            if cur_node.right_child == None:
                cur_node.right_child = Node(value)
            else:
                self._insert(value, cur_node.right_child)

        # value == cur_node.value
        else:
            print("This value has existed")

    def print_tree(self):
        if self.root!=None:
        	self._print_tree(self.root)

    def _print_tree(self,cur_node):
    	if cur_node!=None:
        	self._print_tree(cur_node.left_child)
        	print(str(cur_node.value))
        	self._print_tree(cur_node.right_child)


def fill_tree(tree, num_elems=10, max_int=50):
    from random import randint
    for _ in range(num_elems): #10個 value
        cur_elem = randint(0, max_int) #隨機0~50(不含50)的值
        tree.insert(cur_elem)
    return tree

tree = Binary_search_tree()
tree = fill_tree(tree)

tree.print_tree()

結語

二元樹一直以來是大公司非常注重的觀念之一
想必他在資料結構上有舉足輕重的地位
一定要花時間好好學習
想必在此之後對程式撰寫邏輯上會有莫大的幫助

本篇只有探討到 新增資料 與 印出資料
日後會再補上 刪除與搜尋function
敬請期待

如果對文章內容有任何問題,歡迎在底下留言讓我知道。 
如果你喜歡我的文章,可以分享我的文章,讓更多的人看見我的文章。 
追蹤我的Instagram,看我分享 #咖啡 #Python
如果這篇文章對你有幫助,
可以幫我在下方按 5 個Like 讓我得到一些回饋,
支持我繼續寫出更多好文章!

clickup

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。