Python の二分探索ツリーの詳細な紹介 (コード例)

この記事では、Python の二分探索木について詳しく紹介 (コード例) しています。一定の参考価値があります。困っている友人は参考にしてください。お役に立てれば幸いです。

1. 二分探索ツリー

**二分探索ツリー (BST 二分探索) Tree)** は特殊なバイナリ ツリーです。任意のノードの値は、左の子の値より大きく、右の子の値以下です。BST (バイナリ) が順番に走査されます。 Search Tree) はソートされた要素のセットを取得でき、挿入と削除の消費時間も比較的妥当ですが、メモリのオーバーヘッドが少し大きいことが欠点です。

二分探索ツリーのプロパティ

1. 任意のノード x について、その左側のサブツリーのキーは x.key より大きくなく、右側のサブツリーのキーは x より小さくありません。 。鍵。 ＃＃＃２、異なる二分探索ツリーが同じ値のセットを表すことができます。
3. 二分探索木の基本演算は木の高さに比例するため、完全な二分木であれば最悪の実行時間は Θ(lgn) ですが、次の線形木であればn ノードの場合、最悪の実行時間は Θ(n) になります。 ＃＃＃４、ルートノードは、親ポインタがＮＩＬノードを指す唯一のノードである。
5. 各ノードには少なくとも 4 つの属性 (キー、左、右、親) が含まれています。二分探索木を構築するときは、キーの比較アルゴリズムが必要です。

2. 二分探索ツリーの実装

1.

ツリーのノードを定義します:

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

2. 挿入

BinarySearchTree シェルと TreeNode を用意したので、バイナリ検索ツリーを構築できる put メソッドを作成します。 putメソッドはBinarySearchTreeクラスのメソッドです。このメソッドは、ツリーにすでにルートがあるかどうかを確認します。ルートがない場合、put は新しい TreeNode を作成し、それをツリーのルートにします。ルート ノードがすでに配置されている場合、put はプライベート再帰ヘルパー関数 _put を呼び出し、次のアルゴリズムに従ってツリーを検索します。

ツリーのルートから開始してバイナリ ツリーを検索します。を検索し、新しいキーを現在のノード キーと照合して比較します。新しいキーが現在のノードより小さい場合は、左側のサブツリーが検索されます。新しいキーが現在のノードより大きい場合は、右側のサブツリーが検索されます。
検索する左 (または右) の子がない場合は、新しいノードを確立する必要があるツリー内の位置を見つけます。
ノードをツリーに追加するには、新しい TreeNode オブジェクトを作成し、そのオブジェクトを前の手順で検出したノードに挿入します。

• 挿入する場合、常にリーフ ノードとしてツリーに挿入されます。
  二分探索木を順番に構築するシーケンスが与えられると、二分探索木は一意になります。このツリーのすべてのキーが一致する場合、二分探索木は一意になります。シーケンスが使用される 単語は、一般に一意ではない、可能なバイナリ ツリー (任意の順序で配置) を構築するために使用されます。
  

  def put(self,key,val):
      if self.root:
          self._put(key,val,self.root)
      else:
          self.root = TreeNode(key,val)
      self.size = self.size + 1
  
  def _put(self,key,val,currentNode):
      if key < currentNode.key:
          if currentNode.hasLeftChild():
                 self._put(key,val,currentNode.leftChild)
          else:
                 currentNode.leftChild = TreeNode(key,val,parent=currentNode)
      else:
          if currentNode.hasRightChild():
                 self._put(key,val,currentNode.rightChild)
          else:
                 currentNode.rightChild = TreeNode(key,val,parent=currentNode)

上記は、ツリーに新しいノードを挿入する Python コードを示しています。 _put 関数は、上記の手順に従って再帰的に記述されます。新しい子ノードがツリーに挿入されると、currentNode が親ノードとして新しいツリー ノードに渡されることに注意してください。

挿入の実装における重要な問題は、重複キーを正しく処理できないことです。ツリーが実装されると、重複キーにより、元のキーを持つノードの右側のサブツリーに同じキー値を持つ新しいノードが作成されます。この結果、新しいキーを持つノードは検索中に見つかりません。重複キーの挿入を処理するより良い方法は、古い値を新しいキーに関連付けられた値に置き換えることです。

3. Find

ツリーが構築されたら、次のタスクは、指定されたキーの値の取得を実装することです。 get メソッドは、一致しないリーフ ノードに到達するか、一致するキーが見つかるまでツリーを再帰的に検索するだけなので、put メソッドよりも簡単です。一致するキーが見つかると、ノードのペイロードに格納されている値が返されます。

二分探索木が空でない場合:

まず与えられた値とルートノードのキーワードを比較し、等しければ検索成功
ルート ノードのキー値より小さい場合は、左のサブツリーを再帰的に検索します。
#ルート ノードのキー値より大きい場合は、左のサブツリーを再帰的に検索します。ルート ノードで、正しいサブツリー サブツリー

• #サブツリーが空の場合、検索は失敗します

• def get(self,key):
      if self.root:
          res = self._get(key,self.root)
          if res:
                 return res.payload
          else:
                 return None
      else:
          return None
  
  def _get(self,key,currentNode):
      if not currentNode:
          return None
      elif currentNode.key == key:
          return currentNode
      elif key < currentNode.key:
          return self._get(key,currentNode.leftChild)
      else:
          return self._get(key,currentNode.rightChild)
  
  def __getitem__(self,key):
      return self.get(key)

  4。削除

最初のタスクは、ツリーを検索して削除するノードを見つけることです。ツリーに複数のノードがある場合は、_get メソッドを使用して検索し、削除する必要がある TreeNode を見つけます。ツリーにノードが 1 つしかない場合、これはツリーのルートを削除することを意味しますが、ルートのキーが削除するキーと一致することを確認する必要があります。どちらの場合も、キーが見つからない場合、del 演算子はエラーを発生させます。

def delete(self,key):
   if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError('Error, key not in tree')
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError('Error, key not in tree')

def __delitem__(self,key):
    self.delete(key)

削除するキーのノードを見つけたら、次の 3 つの状況を考慮する必要があります。

削除するノードには子ノードがありません。

• #削除するノードには子ノードが 1 つだけあります。

• #削除対象のノードには 2 つの子ノードがあります。

第一种情况：
如果当前节点没有子节点，我们需要做的是删除节点并删除对父节点中该节点的引用。
第二种情况：
如果一个节点只有一个孩子，那么我们可以简单地促进孩子取代其父。此案例的代码展示在下一个列表中。当你看这个代码，你会看到有六种情况要考虑。由于这些情况相对于左孩子或右孩子对称，我们将仅讨论当前节点具有左孩子的情况。决策如下：

• 如果当前节点是左子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的左子节点引用以指向当前节点的左子节点。

• 如果当前节点是右子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的右子节点引用以指向当前节点的左子节点。

• 如果当前节点没有父级，则它是根。在这种情况下，我们将通过在根上调用replaceNodeData 方法来替换 key，payload，leftChild 和 rightChild 数据。
  第三种情况：
  最难处理的情况。 如果一个节点有两个孩子，那么我们不太可能简单地提升其中一个节点来占据节点的位置。 然而，我们可以在树中搜索可用于替换被调度删除的节点的节点。 我们需要的是一个节点，它将保留现有的左和右子树的二叉搜索树关系。 执行此操作的节点是树中具有次最大键的节点。 我们将这个节点称为后继节点，我们将看一种方法来很快找到后继节点。 继承节点保证没有多于一个孩子，所以我们知道使用已经实现的两种情况删除它。 一旦删除了后继，我们只需将它放在树中，代替要删除的节点。
  找到后继的代码如下所示，是 TreeNode 类的一个方法。此代码利用二叉搜索树的相同属性，采用中序遍历从最小到最大打印树中的节点。在寻找接班人时，有三种情况需要考虑：

• 如果节点有右子节点，则后继节点是右子树中的最小的键。

• 如果节点没有右子节点并且是父节点的左子节点，则父节点是后继节点。

• 如果节点是其父节点的右子节点，并且它本身没有右子节点，则此节点的后继节点是其父节点的后继节点，不包括此节点。

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.leftChild
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
               self.parent.leftChild = None
        else:
               self.parent.rightChild = None
    elif self.hasAnyChildren():
        if self.hasLeftChild():
               if self.isLeftChild():
                  self.parent.leftChild = self.leftChild
               else:
                  self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent
        else:
               if self.isLeftChild():
                  self.parent.leftChild = self.rightChild
               else:
                  self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

三、平衡二叉搜索树（AVL树）

1. 概念

二叉搜索树的深度越小，那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树，搜索算法的时间复杂度也是log(n)。然而，我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，4，3，2，1的顺序插入节点，那么就是一个深度为n的二叉树。那么，搜索算法的时间复杂度为n。
在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。
如何减少树的深度呢？
一种想法是先填满一层，再去填充下一层，这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。另一种比较容易实现的树状数据结构——AVL树，其搜索算法复杂度为log(n)。
在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。

AVL ツリーの実装 Map 抽象データ型は通常の二分探索ツリーとまったく同じで、唯一の違いはツリーの実行方法です。 AVL ツリーを実装するには、ツリー内の各ノードの バランス係数 を追跡する必要があります。これは、各ノードの左右のサブツリーの高さを調べることによって行われます。より正式には、ノードのバランス係数を、左側のサブツリーの高さと右側のサブツリーの高さの差 として定義します。
balanceFacto#r##=##height(leftSubTree)##−height(rightSub# ＃＃木＃＃＃＃＃＃）＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃ ＃＃＃上記のバランス係数の定義を使用すると、バランス係数がゼロより大きい場合、サブツリーは左に重いと言えます。バランス係数がゼロより小さい場合、サブツリーは右重みになります。バランス係数がゼロの場合、ツリーは完全にバランスが取れています。 AVL ツリーを実装し、バランスの取れたツリーの利点を得るには、バランス係数が -1、0、または 1 の場合にツリーのバランスを定義します。ツリー内のノードのバランス係数がこの範囲外になると、ツリーのバランスを戻す手順が必要になります。 高さ h の木のノード数 (Nh) は次のとおりです: Nh=1 Nh−1 Nh−2 この式はフィボナッチ数列に非常に似ています。この式を使用して、ツリー内のノードの数から AVL ツリーの高さを推定できます。フィボナッチ数列の数がどんどん大きくなるにつれて、Fi / Fi−1 は黄金比 Φ にどんどん近づきます。いつでも、AVL ツリーの高さは、AVL ツリーの高さの対数である定数に等しくなります。ツリー内のノード数 (1.44) 倍。検索が O(logN) に制限されるため、これは AVL ツリーの検索にとって朗報です。 2. 実装新しいノードを追加すると二分木のバランスが崩れるため、回転により修正する必要があります。 単一回転正しい右回転を実行するには、次のことを行う必要があります: 左ノードを作成します。サブツリーのルートになります。

古いルートを新しいルートの右のノードに移動します。

新しいルートに元々右ノードがあった場合は、それを新しいルートの右ノードの左ノードにします。

注: 新しいルートは古いルートの左ノードであるため、移動後の古いルートの左ノードは空でなければなりません。この時点で、移動した古いルートに左側のノードを直接追加できます。

同様に、左回転を実行するには、次のことを行う必要があります:

• 右のノード (B) をサブツリーのルートにします。

• 古いルート ノード (A) を新しいルートの左側のノードに移動します。

• 新しいルート (B) にもともと左ノードがある場合、元の B の左ノードを新しいルートの左ノード (A) の右ノードにします。

二重回転

図に示すように、子ノードが 2 ではなく 4 の場合、単一回転を試してみると、問題が解決できないことがわかります。
この問題を解決するには、次のルールを使用する必要があります:

• バランスをとるためにサブツリーを左に回転する必要がある場合は、まず右側のノードのバランス係数を確認します。右のノードが左に多い場合、右のノードが右に回転されてから、元のノードが左に回転されます。

• サブツリーのバランスをとるためにサブツリーを右に回転する必要がある場合は、まず左側のノードのバランス係数を確認します。左側のノードが右寄りの場合、左側のノードが左に回転されてから、元のノードが右に回転されます。

現時点での解決策は二重回転です。

二重回転は実際には 2 回の単一回転です。ルート ノード 4 を持つサブツリーは最初に左への 1 回転を実行し、次にルート ノード 5 を持つサブツリーは右方向への 1 回転を実行します。これにより、ツリーの ACL プロパティが復元されます。

AVL ツリーの場合、新しいノードが追加されると、AVL ツリーのプロパティは 1 回の回転を通じて常に復元できることが証明できます。

回転ルール

新しいノードを挿入すると、どこが回転するのでしょうか?単一回転または二重回転を使用する必要がありますか?

次の基本手順に従います。

1. 二分探索ツリー法に従ってノードを追加し、新しいノード名はリーフノードです。

2. 新しいノードから開始して、最初の不平衡ノード (5) まで遡ります。
   (ルート ノードまで遡って不均衡なノードが存在しない場合は、ツリーがすでに AVL プロパティに準拠していることを意味します。)

3. ##壊れたエッジを見つけます (5- >3)、切れた文字列の方向(5の左側)を決定します

4. 切れたエッジ(3)の下端をルートノードとして、どちらを決定しますか2 つのサブツリーのうち、深さが大きい方 (左側のサブツリーまたは右側のサブツリー) があります。

   (2 つのサブツリーの深さを等しくすることはできません。深さが深いサブツリーには新しいノードが含まれます。)
   

5. 手順 2 と 3 の方向が同じ場合 (両方左または両方右) では、アンバランス ノードをルート ノードとしてサブツリーを 1 回回転する必要があります。

6. それ以外の場合は、不均衡ノードをルートとするサブツリーを二重回転します。

4. 赤黒ツリー

赤黒ツリーは一般的に使用される平衡二分探索ツリーであり、複雑ではありますが、その演算により良好な最適化結果が得られます。悪い場合の実行時間、つまり操作の複雑さは悪化せず、実際には効率的です。1 回の検索、挿入、削除を O(logn) 時間で実行できます (n はツリー内の要素の数です)。番号。

赤黒ツリーは、非常に興味深いバランスの取れた検索ツリーです。赤黒ツリーはバランス二分木 (AVL-tree) よりも統計的なパフォーマンスが優れているため、多くの場所で使用されます。 C STL では、多くの部分 (現在
set、multiset、map、multimap を含む) で赤黒ツリーのバリエーションが適用されます (SGI STL の赤黒ツリーにはいくつかの変更があり、これらの変更により、パフォーマンスが向上するだけでなく、セット操作もサポートされます)。 赤黒ツリーの主なルール:
赤黒ツリーの主なルールは次のとおりです:

1. ノードは赤または黒です。

#根元は黒いです。
すべての葉は黒です (葉は NIL ノードです)。

3. #各赤いノードには 2 つの黒い子ノードが必要です。 (各リーフからルートまでのパス上に 2 つの連続する赤いノードは存在できません。)

4. 任意のノードから各リーフまでのすべての単純なパスには、同じ番号の黒いノードが含まれます。

赤黒ツリーに挿入されたノードはすべて赤です。赤いノードを挿入する方が黒のノードを挿入するよりも赤黒ルールに違反する可能性が低いため、これは偶然ではありません。その理由は、黒のノードを挿入すると常に黒の高さが変更される (ルール 4 に違反) が、赤のノードを挿入するとルール 3 に違反する可能性は半分しかないためです。さらに、ルール 3 の違反は、ルール 4 の違反よりも修正が簡単です。
新規ノードを挿入するとこのバランスが崩れる場合がありますが、赤黒ツリーでは主にノードの色の変更、左回転、右回転の3つの方法でバランスを修正します。 (具体的なルールは省略)
各赤黒ツリーも特殊な二分探索木であるため、赤黒ツリーに対する読み取り専用操作は通常の二分探索木に対する読み取り専用操作と同じです。ただし、赤黒ツリーに対する挿入および削除操作は、赤黒ツリーのプロパティに準拠しなくなります。赤黒ツリーのプロパティを復元するには、わずかな (O(logn)) 色の変更 (実際には非常に高速) と 3 回以内のツリー回転 (挿入操作の場合は 2 回) が必要です。挿入と削除は複雑ですが、操作時間は O(logn) 回に抑えることができます。
n 個の内部ノードを持つ赤黒ツリーの高さは、最大 2lg(n 1) です。

以上がPython の二分探索ツリーの詳細な紹介 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。