Binärt sökträd (BST)

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Definition

Vänster delträd för en nod:
- värden mindre än noden själv
Höger delträd för en nod:
- värden större än noden själv
Vänster och höger delträd måste vara binära sökträd

Schematisk representation av ett binärt sökträd.

Implementation

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

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd.

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd där rotnoden är färgad i gult.

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd där rotnoden och rotnodens vänstra delträd är grå. Den första noden i det högra delträdet är färgad i gult.

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd. Det vänstra delträdet för den senaste rotnoden och rotnoden är också grå. Den nya rotnoden är färgad i gult.

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd där den nya rotnoden är färgad i gult och övriga noder är grå.

Sökning

Sök efter 72

Schematisk representation av ett binärt sökträd där den nya rotnoden är färgad i gult och övriga noder är grå. Den färgade noden har värdet 72 och är markerad.

Sökning

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

Infogning

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Grafisk representation av en ny nod.

Infogning

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

Grafisk representation av den nya nod som har blivit rotnod.

Infogning

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

Grafisk representation av en ny nod och en rotnod med ett höger barn.

Infogning

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:

Grafisk representation av en ny nod och en rotnod med ett höger barn. Rotnoden är current_node.

Infogning

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

Grafisk representation av en rotnod med ett höger och ett vänster barn. Rotnoden är current_node. Den nya noden är det vänstra barnet.

Infogning

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:

Grafisk representation av en ny nod och ett binärt sökträd med några element. Rotnoden är current_node.

Infogning

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

Grafisk representation av en ny nod och ett binärt sökträd med några element. current_node är rotnodens vänstra barn.

Infogning

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:

Grafisk representation av en ny nod och ett binärt sökträd med ett vänster delträd.

Infogning

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

Grafisk representation av ett binärt sökträd med ett vänster delträd. Den nya noden är nu rotnodens högra barn.

Infogning

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:

Grafisk representation av en ny nod och ett binärt sökträd med några element.

Infogning

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

Grafisk representation av en ny nod och ett binärt sökträd med några element. current_node är rotnodens högra barn.

Infogning

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

Grafisk representation av en ny nod och ett binärt sökträd med några element. current_node är rotnodens högra barn. Den nya noden är current_nodes vänstra barn.

Borttagning

Inga barn

Grafisk representation av ett binärt sökträd med några element. En av noderna är färgad i rött eftersom den ska tas bort. Denna nod har inga barn.

Borttagning

Inga barn
- ta bort den

Grafisk representation av ett binärt sökträd med några element. Den nod som skulle tas bort har försvunnit från trädet.

Borttagning

Ett barn

Grafisk representation av ett binärt sökträd med några element. En av noderna är färgad i rött eftersom den ska tas bort. Denna nod har ett höger barn.

Borttagning

Ett barn
- ta bort den
- koppla barnet till nodens förälder

Grafisk representation av ett binärt sökträd med några element. Den nod som skulle tas bort har försvunnit och rotnoden pekar nu på den borttagna nodens högra barn.

Borttagning

Ett barn
- ta bort den
- koppla barnet till nodens förälder

Grafisk representation av ett binärt sökträd.

Borttagning

Två barn

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött. Rotnodens högra barn är färgat i gult.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött. En annan nod är färgad i gult för att hitta efterföljaren.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött. En annan nod är färgad i gult för att hitta efterföljaren.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet

Grafisk representation av ett binärt sökträd där rotnoden ska tas bort och är färgad i rött. En annan nod är färgad i gult för att hitta efterföljaren. Efterföljaren har hittats och är talet 13.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet

Grafisk representation av ett binärt sökträd. Rotnoden har ersatts med efterföljaren.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet
  - om efterföljaren har ett höger barn:

Grafisk representation av ett binärt sökträd där efterföljarnoden har ett höger barn.

Borttagning

Två barn
- ersätt den med sin efterföljare
  - noden med det minsta värdet som är större än nodens värde
- hitta efterföljaren:
  - besök det högra barnet
  - fortsätt besöka vänstra noder till slutet
  - om efterföljaren har ett höger barn:
    - barnet blir det vänstra barnet till efterföljarens förälder.

Grafisk representation av ett binärt sökträd där efterföljarnoden hade ett höger barn. Efterföljarens barn har blivit det vänstra barnet till efterföljarens förälder och rotnoden har ersatts med efterföljarnoden.

Användningsområden

Sorterar listor effektivt
Mycket snabbare på sökning än arrayer och länkade listor
Mycket snabbare på infogning och borttagning än arrayer
Används för att implementera mer avancerade datastrukturer:
- dynamiska mängder
- uppslagstabeller
- prioritetsköer

Nu kör vi en övning!

Datastrukturer och algoritmer i Python