बाइनरी सर्च ट्री (BST)

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

परिभाषा

किसी नोड का लेफ्ट सबट्री:
- नोड के मान से कम मान
किसी नोड का राइट सबट्री:
- नोड के मान से ज़्यादा मान
लेफ्ट और राइट दोनों सबट्री भी बाइनरी सर्च ट्री होने चाहिए

बाइनरी सर्च ट्री का योजनात्मक चित्र.

इम्प्लीमेंटेशन

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

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

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र.

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र, जहाँ रूट नोड पीले रंग में है.

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र, जहाँ रूट और उसका लेफ्ट सबट्री ग्रे है. राइट सबट्री का पहला नोड पीला है.

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र. अंतिम रूट और उसका लेफ्ट सबट्री ग्रे है. नया रूट पीला है.

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र, नया रूट पीला है और बाकी नोड ग्रे हैं.

खोज (Searching)

72 की खोज करें

बाइनरी सर्च ट्री का योजनात्मक चित्र, नया रूट पीला है और बाकी नोड ग्रे. रंगा हुआ नोड 72 है और हाइलाइटेड है.

खोज (Searching)

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

इन्सर्ट करना

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

नए नोड का ग्राफिकल चित्रण.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

नया नोड जो रूट नोड बन गया है, उसका ग्राफिकल चित्रण.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

नए नोड और एक रूट नोड (जिसका राइट चाइल्ड है) का ग्राफिकल चित्रण.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

नए नोड और एक रूट नोड (राइट चाइल्ड के साथ) का ग्राफिकल चित्रण. रूट नोड current_node है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

रूट नोड (राइट और लेफ्ट चाइल्ड के साथ) का ग्राफिकल चित्रण. रूट current_node है. नया नोड लेफ्ट चाइल्ड है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

नए नोड और कुछ एलिमेंट वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण. रूट current_node है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

नए नोड और कुछ एलिमेंट वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण. current_node रूट का लेफ्ट चाइल्ड है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

नए नोड और लेफ्ट सबट्री वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

लेफ्ट सबट्री वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण. नया नोड अब रूट का राइट चाइल्ड है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

नए नोड और कुछ एलिमेंट वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

नए नोड और कुछ एलिमेंट वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण. current_node रूट का राइट चाइल्ड है.

इन्सर्ट करना

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

नए नोड और कुछ एलिमेंट वाले बाइनरी सर्च ट्री का ग्राफिकल चित्रण. current_node रूट का राइट चाइल्ड है. नया नोड current_node का लेफ्ट चाइल्ड है.

डिलीट करना

कोई चाइल्ड नहीं

कुछ एलिमेंट वाला बाइनरी सर्च ट्री. एक नोड लाल है क्योंकि उसे हटाया जाएगा. इस नोड का कोई चाइल्ड नहीं है.

डिलीट करना

कोई चाइल्ड नहीं
- उसे डिलीट करें

कुछ एलिमेंट वाला बाइनरी सर्च ट्री. हटाया जाने वाला नोड ट्री से गायब है.

डिलीट करना

एक चाइल्ड

कुछ एलिमेंट वाला बाइनरी सर्च ट्री. एक नोड लाल है क्योंकि उसे हटाया जाएगा. इस नोड का राइट चाइल्ड है.

डिलीट करना

एक चाइल्ड
- उसे डिलीट करें
- चाइल्ड को नोड के पैरेंट से जोड़ें

कुछ एलिमेंट वाला बाइनरी सर्च ट्री. हटाया गया नोड गायब है और रूट अब हटाए गए नोड के राइट चाइल्ड की ओर पॉइंट करता है.

डिलीट करना

एक चाइल्ड
- उसे डिलीट करें
- चाइल्ड को नोड के पैरेंट से जोड़ें

बाइनरी सर्च ट्री का ग्राफिकल चित्रण.

डिलीट करना

दो चाइल्ड

बाइनरी सर्च ट्री का ग्राफिकल चित्रण, जहाँ रूट नोड डिलीट होगा और लाल रंग में है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ

बाइनरी सर्च ट्री का ग्राफिकल चित्रण, जहाँ रूट नोड डिलीट होगा और लाल है. रूट का राइट चाइल्ड पीला है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें

बाइनरी सर्च ट्री का ग्राफिकल चित्रण, जहाँ रूट नोड डिलीट होगा और लाल है. successor ढूँढने के लिए एक और नोड पीला है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें

बाइनरी सर्च ट्री का ग्राफिकल चित्रण, जहाँ रूट नोड डिलीट होगा और लाल है. successor (13) मिल गया है और पीला है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें

बाइनरी सर्च ट्री का ग्राफिकल चित्रण. रूट नोड को successor से रिप्लेस कर दिया गया है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें
  - अगर successor का कोई राइट चाइल्ड हो:

बाइनरी सर्च ट्री का ग्राफिकल चित्रण जहाँ successor नोड का राइट चाइल्ड है.

डिलीट करना

दो चाइल्ड
- इसे इसके successor से रिप्लेस करें
  - वह नोड जिसका मान, नोड के मान से बड़ा होने पर, सबसे छोटा हो
- successor ढूँढें:
  - राइट चाइल्ड पर जाएँ
  - लेफ्ट नोड्स पर अंत तक जाते रहें
  - अगर successor का राइट चाइल्ड हो:
    - वह चाइल्ड, successor के पैरेंट का लेफ्ट चाइल्ड बन जाए.

बाइनरी सर्च ट्री का ग्राफिकल चित्रण जहाँ successor नोड का राइट चाइल्ड था. वह चाइल्ड अब successor के पैरेंट का लेफ्ट चाइल्ड है और रूट को successor से बदला गया है.

उपयोग

सूचियों को कुशलता से ऑर्डर करें
arrays और linked lists से खोज में कहीं तेज
arrays से इन्सर्ट और डिलीट में कहीं तेज
उन्नत डेटा स्ट्रक्चर्स को इम्प्लीमेंट करने में उपयोग:
- dynamic sets
- lookup tables
- priority queues

अभ्यास करते हैं!

Python में Data Structures और Algorithms