Python의 이진 검색 트리에 대한 자세한 소개(코드 예)

이 기사는 Python의 이진 검색 트리에 대한 자세한 소개(코드 예제)를 제공합니다. 이는 특정 참조 값을 가지고 있으므로 도움이 될 수 있습니다.

1. 이진 검색 트리

** 이진 검색 트리(BST 이진 검색 tree)**는 특별한 이진 트리입니다. 모든 노드의 값은 왼쪽 자식의 값보다 크고 오른쪽 자식의 값보다 작거나 같습니다. Search Tree)를 사용하면 정렬된 요소 집합을 얻을 수 있고, 삽입 및 삭제에 소요되는 시간도 비교적 합리적이지만 한 가지 단점은 메모리 오버헤드가 약간 크다는 것입니다.

이진 검색 트리의 속성

1, 임의의 노드 x에 대해 왼쪽 하위 트리의 키는 x.key보다 크지 않고 오른쪽 하위 트리의 키는 다음과 같습니다. x.key 이상입니다.
2, 서로 다른 이진 검색 트리는 동일한 값 집합을 나타낼 수 있습니다.
3 이진 탐색 트리의 기본 동작은 트리의 높이에 비례하므로 완전 이진 트리라면 최악의 실행 시간은 Θ(lgn)이지만 연결된 선형 트리라면 n 노드만큼, 최악의 실행 시간은 Θ(n)입니다.
4, 루트 노드는 부모 포인터가 NIL 노드를 가리키는 유일한 노드입니다.
5. 각 노드에는 키, 왼쪽, 오른쪽, 상위의 네 가지 속성이 포함됩니다. 이진 검색 트리를 구축할 때 키에 대한 비교 알고리즘이 있어야 합니다.

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. Insert

이제 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.

찾기 트리가 생성되면 다음 작업은 주어진 키에 대한 값 검색을 구현하는 것입니다. 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.Delete

첫 번째 작업은 트리를 검색하여 삭제할 노드를 찾는 것입니다. 트리에 여러 개의 노드가 있는 경우 _get 메서드를 사용하여 검색하여 삭제해야 하는 TreeNode를 찾습니다. 트리에 노드가 하나만 있는 경우 이는 트리의 루트를 삭제하지만 루트의 키가 삭제하려는 키와 일치하는지 확인해야 함을 의미합니다. 두 경우 모두 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)

  삭제하려는 키가 있는 노드를 찾으면 세 가지 상황을 고려해야 합니다.

삭제할 노드 하위 노드가 없습니다.

삭제할 노드에는 하위 노드가 하나만 있습니다.

• 삭제할 노드에 하위 노드가 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 트리 구현 맵 추상 데이터 유형은 일반 이진 검색 트리와 동일하며 유일한 차이점은 트리가 실행되는 방식입니다. AVL 트리를 구현하려면 트리의 각 노드에 대한 균형 인자를 추적해야 합니다. 각 노드의 왼쪽 및 오른쪽 하위 트리의 높이를 확인하여 이를 수행합니다. 보다 공식적으로는 노드의 균형 요소를 왼쪽 하위 트리 높이와 오른쪽 하위 트리 높이의 차이로 정의합니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ c
tor =height(le ftSu bTree)−heig ht( rㅋㅋㅋ 위에 주어진 잔액을 사용하세요. 요인의 정의에서 균형 요인이 0보다 크면 하위 트리가 왼쪽에 무겁다고 말합니다. 균형 요소가 0보다 작으면 하위 트리는 오른쪽 중심입니다. 균형 요소가 0이면 트리는 완벽하게 균형을 이루고 있습니다. AVL 트리를 구현하고 균형 잡힌 트리의 이점을 얻으려면 균형 요소가 -1,0 또는 1인 경우 트리 균형을 정의합니다. 트리에 있는 노드의 균형 요소가 이 범위를 벗어나면 트리의 균형을 다시 맞추는 절차가 필요합니다. 높이가 h인 트리의 노드 수(Nh)는 다음과 같습니다. Nh=1+Nh−1+Nh−2 이 공식은 피보나치 수열과 매우 유사합니다. 이 공식을 사용하여 트리의 노드 수에서 AVL 트리의 높이를 추론할 수 있습니다. 피보나치 수열 번호가 커질수록 Fi/Fi−1은 황금비 Φ에 점점 더 가까워집니다. 언제든지 AVL 트리의 높이는 트리의 노드 수에 대한 로그인 상수와 같습니다. (1.44 ) 번. 이는 검색을 O(logN)으로 제한하므로 AVL 트리 검색에 좋은 소식입니다. 2. 구현새 노드가 추가되면 이진 트리의 균형이 파괴되므로 회전으로 수정해야 합니다. 단일 회전올바른 오른쪽 회전을 수행하려면 다음을 수행해야 합니다. 왼쪽 노드를 하위 트리의 루트로 만듭니다. 이전 루트를 새 루트의 오른쪽 노드로 이동합니다. 새 루트에 원래 오른쪽 노드가 있었다면 새 루트 오른쪽 노드의 왼쪽 노드가 되도록 하세요.

참고: 새 루트는 이전 루트의 왼쪽 노드이므로 이동 후 이전 루트의 왼쪽 노드는 비어 있어야 합니다. 이때 이동된 이전 루트에 왼쪽 노드를 직접 추가할 수 있습니다.

마찬가지로 왼쪽 회전을 수행하려면 다음을 수행해야 합니다.

• 오른쪽 노드(B)를 하위 노드로 만듭니다. 나무의 뿌리.

• 이전 루트 노드(A)를 새 루트의 왼쪽 노드로 이동합니다.

• 새 루트(B)에 원래 왼쪽 노드가 있는 경우 원래 B의 왼쪽 노드가 새 루트 왼쪽 노드(A)의 오른쪽 노드가 되도록 합니다. ).

Double Rotation

그림과 같이 자식 노드가 2가 아닌 4인 경우 단일 회전을 시도하면 문제가 해결될 수 없음을 발견합니다.
이 문제를 해결하려면 다음 규칙을 사용해야 합니다.

• 균형을 맞추기 위해 하위 트리를 왼쪽으로 회전해야 하는 경우 먼저 균형 요소를 확인하세요. 오른쪽 노드의. 오른쪽 노드가 왼쪽에 무거우면 오른쪽 노드가 오른쪽으로 회전한 다음 원래 노드가 왼쪽으로 회전됩니다.

• 균형을 맞추기 위해 하위 트리를 오른쪽으로 회전해야 하는 경우 먼저 왼쪽 노드의 균형 요소를 확인하세요. 왼쪽 노드가 오른쪽에 무거운 경우 왼쪽 노드는 왼쪽으로 회전한 다음 원래 노드는 오른쪽으로 회전합니다.

이때의 해결책은 이중회전입니다.

이중 회전은 실제로 두 개의 단일 회전입니다. 루트 노드 4가 있는 하위 트리는 먼저 왼쪽으로 단일 회전을 수행하고 루트 노드 5가 있는 하위 트리는 왼쪽으로 단일 회전을 수행합니다. . 오른쪽으로 한 번 회전합니다. 그러면 트리의 ACL 속성이 복원됩니다.

AVL 트리의 경우 새로운 노드가 추가되면 AVL 트리의 속성은 항상 한 번의 회전을 통해 복원될 수 있음을 증명할 수 있습니다.

회전 규칙

새 노드를 삽입하면 어디에서 회전하나요? 단일 회전을 사용해야 할까요, 아니면 이중 회전을 사용해야 할까요?

다음 기본 단계를 따릅니다.

1. 이진 검색 트리 방법을 따릅니다. 노드를 추가하면 새 노드를 리프 노드라고 합니다.

2. 새로 추가된 노드에서 시작하여 첫 번째 불균형 노드(5)까지 역추적합니다.
   (루트 노드까지 추적해 보면 불균형 노드가 없다면 트리가 AVL 속성을 충족했다는 뜻입니다.)

3. Find the 부러진 가장자리(5->3), 부러진 끈의 방향(5의 왼쪽)을 결정합니다.

4. 부러진 가장자리의 하단을 취합니다( 3) 루트 노드로서 두 하위 트리 중 큰 깊이(왼쪽 하위 트리 또는 오른쪽 하위 트리)를 결정합니다.
   (두 하위 트리의 깊이는 같을 수 없으며, 깊이가 더 큰 하위 트리에는 새 노드가 포함됩니다.)

5. 2번째와 3번째인 경우 방향 단계는 동일하며(왼쪽 또는 오른쪽 모두) 불균형 노드를 루트 노드로 하는 하위 트리의 단일 회전이 필요합니다.

6. 그렇지 않으면 불균형 노드에 루트가 있는 하위 트리를 두 번 회전합니다.

4. 레드-블랙 트리

레드-블랙 트리는 일반적으로 사용되는 균형 이진 검색 트리입니다. n의 연산은 트리의 요소 수입니다.
레드-블랙 트리는 매우 흥미로운 균형 탐색 트리입니다. 균형이진트리(AVL-tree)보다 통계적 성능이 좋기 때문에 레드-블랙 트리가 여러 곳에서 사용된다. C++ STL에서는 많은 부분(현재 set, multiset, map, multimap 포함)이 레드-블랙 트리(SGI STL의 레드-블랙 트리) 변형을 적용합니다. 더 나은 성능을 제공하고 집합 작업을 지원하는 몇 가지 변경 사항이 있습니다.
레드-블랙 트리의 주요 규칙:
레드-블랙 트리의 주요 규칙은 다음과 같습니다.

1. 노드는 빨간색 또는 검정색입니다. .

2. 뿌리는 검은색이다.

3. 모든 잎은 검은색입니다(잎은 NIL 노드입니다).

4. 각 빨간색 노드에는 두 개의 검은색 하위 노드가 있어야 합니다. (각 리프에서 루트까지의 모든 경로에 두 개의 연속된 빨간색 노드가 있을 수 없습니다.)

5. 모든 노드에서 각 리프까지의 모든 단순 경로 둘 다 동일한 내용을 포함합니다. 블랙 노드의 수.

레드-블랙 트리에 삽입된 노드는 모두 레드입니다. 이는 레드 노드를 삽입하는 것이 블랙 노드를 삽입하는 것보다 레드-블랙 규칙을 위반할 가능성이 적기 때문입니다. 그 이유는 검정색 노드를 삽입하면 검정색 높이가 항상 변경되지만(규칙 4 위반), 빨간색 노드를 삽입하면 규칙 3을 위반할 확률이 절반에 불과하기 때문입니다. 또한, 규칙 3의 위반은 규칙 4의 위반보다 시정하기가 더 쉽습니다.
새 노드를 삽입하면 이 균형이 깨질 수 있습니다. 레드-블랙 트리는 주로 노드 색상 변경, 왼쪽 회전, 오른쪽 회전의 세 가지 방법으로 균형을 수정합니다. (특정 규칙 생략)
각 레드-블랙 트리도 특수 이진 검색 트리이기 때문에 레드-블랙 트리의 읽기 전용 작업은 일반 이진 검색 트리의 읽기 전용 작업과 동일합니다. 그러나 레드-블랙 트리에 대한 삽입 및 삭제 작업은 더 이상 레드-블랙 트리의 속성을 따르지 않습니다. 레드-블랙 트리의 속성을 복원하려면 작은(O(logn)) 색상 변경(실제로는 매우 빠름)과 3번 이하의 트리 회전(삽입 작업의 경우 2번)이 필요합니다. 삽입과 삭제가 복잡하더라도 연산 시간은 여전히 ​​O(logn)배로 유지될 수 있다.
n개의 내부 노드가 있는 레드-블랙 트리의 높이는 최대 2lg(n+1)입니다.

위 내용은 Python의 이진 검색 트리에 대한 자세한 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!