python 평형 이 진 트 리 구현 코드 예시

밸 런 스 이 진 트 리:
위의 이 진 트 리 를 바탕 으로 우 리 는 균형 잡 힌 이 진 트 리 를 어떻게 생 성 하 는 지 실현 합 니 다.
밸 런 스 이 진 트 리 란:
내 가 정의 하 는 것 은 모든 노드 의 왼쪽 높이 와 오른쪽 높이 의 차 이 는 절대 값 이 2 보다 작다 는 것 이다.
그림 에서 보 듯 이 이때 a 의 왼쪽 높이 는 3 과 같 고 높이 는 1 과 같 으 며 차 이 는 2 로 불 균형 중의 왼쪽 에 속한다.
　　
이때 의 처리 방법 은:
불 균형 한 원소 의 왼쪽 가지의 가장 오른쪽 노드 를 현재 노드 로 바 꾸 고,
이때 두 가지 상황 으로 나 뉜 다.
1.왼쪽 가지 에 가장 오른쪽 노드 가 있다.
가장 오른쪽 노드 의 왼쪽 가 지 를 아버지 노드 의 오른쪽 가지 에 부여 합 니 다.
2.왼쪽 가 지 는 가장 오른쪽 노드 가 없고,
왼쪽 가지 노드 를 아버지 급 노드 로 하고 아버지 급 노드 를 오른쪽 가지 로 한다.
　　　　　　
그림 에서 보 듯 이 그림 이 좀 더 분명 하 다.
왜 이렇게 바 뀌 었 는 지 의문 이 들 수 있 습 니 다.
a 왼쪽 편향 을 가정 하면 a 보다 작은 최소 값 d(d 의 유일한 하 나 는 a 보다 작 고 a 의 왼쪽 가지 모든 수 보다 큰 값)를 부모 집합 점 으로 해 야 한다.a 는 d 의 오른쪽 가 지 를 만 들 면 맨 위 에 있 는 d 노드 가 균형 을 이룬다.
우 리 는 반증 할 수 있다.
만약 에 d 가 다른 숫자 가 h 라 고 가정 하지 않 으 면 h 는 부모 노드 가 되 고 a 는 부모 노드 의 오른쪽 노드 가 된다.
a 는 h 오른쪽 에 있 기 때문에 a>h
b,e,d,f 는 모두 h 의 왼쪽 가지 이기 때문에 h>d>b>e>f
그래서 a>h>d>b>e>f
그래서 새로운 노드 에 가입 하지 않 으 면 d 일 수 밖 에 없다.
왼쪽 과 오른쪽 이 똑 같 아 요.완전히 미 러 로 오 면 돼 요.
모든 노드 의 왼쪽 과 오른쪽 을 처리 하여 전체 이 진 트 리 를 균형 시 켰 는데 이것 이 바로 이 진 트 리 를 균형 시 키 는 기본 사상 이다.
코드 구현:

# -*- coding:utf-8 -*-
#   ：2018/6/12 8:37
# Author:   

#     
class Node:
  def __init__(self):
    self.left_children = None
    self.left_height = 0
    self.right_children = None
    self.right_height = 0
    self.value = None

#      
class tree:
  def __init__(self):
    self.root = False
    self.front_list = []
    self.middle_list = []
    self.after_list = []
  #      
  def create_tree(self,n=0,l=[]):
    if l == []:
      print("       ")
      return
    if n > len(l)-1:
      print("     ")
      return
    node = Node()
    node.value = l[n]
    if not self.root:
      self.root = node
      self.list = l
    else:
      self.add(self.root,node)
    self.create_tree(n+1,l)
  #     
  def add(self,parent,new_node):
    if new_node.value > parent.value:
      #         ，        
      if parent.right_children == None:
        parent.right_children = new_node
        #                1，       0+1
        parent.right_height = 1
        #               height
      else:
        self.add(parent.right_children,new_node)
        #              ，          + 1
        parent.right_height = max(parent.right_children.right_height, parent.right_children.left_height) + 1
        # =======            =======
        #                
        if parent.right_height - parent.left_height >= 2:
          self.right_avertence(parent)
    else:
      #         ，        
      if parent.left_children == None:
        parent.left_children = new_node
        parent.left_height = 1
      else:
        self.add(parent.left_children,new_node)
        parent.left_height = max(parent.left_children.right_height, parent.left_children.left_height) + 1
        # =======            =======
        #                
        if parent.left_height - parent.right_height >= 2:
          self.left_avertence(parent)
  #                
  def update_height(self,node):
    #          0
    node.left_height = 0
    node.right_height = 0
    #          
    if node.left_children == None and node.right_children == None:
      return
    else:
      if node.left_children:
        self.update_height(node.left_children)
        #                      + 1
        node.left_height = max(node.left_children.left_height,node.left_children.right_height) + 1
      if node.right_children:
        self.update_height(node.right_children)
        #                      + 1
        node.right_height = max(node.right_children.left_height, node.right_children.right_height) + 1
      #          
      if node.left_height - node.right_height >= 2:
        self.left_avertence(node)
      elif node.left_height - node.right_height <= -2:
        self.right_avertence(node)

  def right_avertence(self,node):
    #                  
    new_code = Node()
    new_code.value = node.value
    new_code.left_children = node.left_children
    best_left = self.best_left_right(node.right_children)
    v = node.value
    #        ,
    if best_left == node.right_children and best_left.left_children == None:
      #            
      node.value = best_left.value
      node.right_children = best_left.right_children
    else:
      node.value = best_left.left_children.value
      best_left.left_children = best_left.left_children.right_children
    node.left_children = new_code
    self.update_height(node)

  #       
  def left_avertence(self,node):
    new_code = Node()
    new_code.value = node.value
    new_code.right_children = node.right_children
    best_right = self.best_left_right(node.left_children,1)
    v = node.value
    #        ,
    if best_right == node.left_children and best_right.right_children == None:
      #            
      node.value = best_right.value
      node.left_children = best_right.left_children
    else:
      node.value = best_right.right_children.value
      best_right.right_children = best_right.right_children.left_children
    node.right_children = new_code
    self.update_height(node)
  #   node    （ ）     
  def best_left_right(self,node,type=0):
    # type=0        
    if type == 0:
      if node.left_children == None:
        return node
      elif node.left_children.left_children == None:
        return node
      else:
        return self.best_left_right(node.left_children,type)
    else:
      if node.right_children == None:
        return node
      elif node.right_children.right_children == None:
        return node
      else:
        return self.best_left_right(node.right_children,type)
  #   (       )
  def front(self,node=None):
    if node == None:
      self.front_list = []
      node = self.root
    #       
    self.front_list.append(node.value)
    #      
    if not node.left_children == None:
      self.front(node.left_children)
    #      
    if not node.right_children == None:
      self.front(node.right_children)
    #       
    return self.front_list
  #   (       )
  def middle(self,node=None):
    if node == None:
      node = self.root
    #      
    if not node.left_children == None:
      self.middle(node.left_children)
    #       
    self.middle_list.append(node.value)
    #      
    if not node.right_children == None:
      self.middle(node.right_children)
    return self.middle_list
  #   (       )
  def after(self,node=None):
    if node == None:
      node = self.root
    #      
    if not node.left_children == None:
      self.after(node.left_children)
    #      
    if not node.right_children == None:
      self.after(node.right_children)
    self.after_list.append(node.value)
    return self.after_list
  #     
  def del_node(self,v,node=None):
    if node == None:
      node = self.root
      #      
      if node.value == v:
        self.del_root(self.root)
        return
    #           
    if node.left_children:
      if node.left_children.value == v:
        self.del_left(node)
        return
    #           
    if node.right_children:
      if node.right_children.value == v:
        self.del_right(node)
        return
    if v > node.value:
      if node.right_children:
        self.del_node(v, node.right_children)
      else:
        print("        ")
    else:
      if node.left_children:
        self.del_node(v, node.left_children)
      else:
        print("        ")
  #          
  def del_right(self,node):
    #   1         
    if node.right_children.right_children == None:
      node.right_children = node.right_children.left_children
    else:
      best_left = self.best_left_right(node.right_children.right_children)
      #              
      if best_left == node.right_children.right_children and best_left.left_children == None:
        node.right_children.value = best_left.value
        node.right_children.right_children = best_left.right_children
      else:
        node.right_children.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children
  #           
  def del_left(self,node):
    #   1         
    if node.left_children.right_children == None:
      node.left_children = node.left_children.left_children
    else:
      best_left = self.best_left_right(node.left_children.right_children)
      #               
      if best_left == node.left_children.right_children and best_left.left_children == None:
        node.left_children.value = best_left.value
        node.left_children.right_children = best_left.right_children
      else:
        node.left_children.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children
  #      
  def del_root(self,node):
    if node.right_children == None:
      if node.left_children == None:
        node.value = None
      else:
        self.root = node.left_children
    else:
      best_left = self.best_left_right(node.right_children)
      #               
      if best_left == node.right_children and best_left.left_children == None:
        node.value = best_left.value
        node.right_children = best_left.right_children
      else:
        node.value = best_left.left_children.value
        best_left.left_children = best_left.left_children.right_children

  #   
  def search(self,v,node=None):
    if node == None:
      node = self.root
    if node.value == v:
      return True
    if v > node.value:
      if not node.right_children == None:
        return self.search(v, node.right_children)
    else:
      if not node.left_children == None:
        return self.search(v, node.left_children)
    return False
if __name__ == '__main__':
  #           
  list = [4, 6, 3, 1, 7, 9, 8, 5, 2]
  t = tree()
  t.create_tree(0,list)
  res = t.front()
  print('  ', res)

실행 결과:
앞 순서[4,2,1,3,7,6,5,9,8]
앞 순 서 를 통 해 이 진 트 리 를 그 릴 수 있다.

완벽 하 다
이것 은 내 가 이틀 동안 파고 들 어서 쓴 코드 입 니 다.하하,노력 한 보람 이 있 습 니 다.화 이 팅!
다음 단 계 는 코드 최적화 입 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.