《 Python 데이터 구조 와 알고리즘 》

58201 단어

 
                  《Data Structures and Algorithms Using Python》
 
 
1 장: ADT 추상 데이터 형식, 데이터 와 조작 정의
 
ADT: 추상 적 인 데이터 형식 이 무엇 인지 데이터 구 조 를 배 운 사람 은 모두 알 고 있 을 것 이다.
How to select datastructures for ADT
  • Dose the data structure provie for the storage requirements as specified by the domain of the ADT?
  • Does the data structure provide the data access and manipulation functionality to fully implement the ADT?
  • Effcient implemention? based on complexity analysis.

  • 다음 코드 는 간단 한 예제 입 니 다. 예 를 들 어 간단 한 Bag 류 를 실현 하고 먼저 가지 고 있 는 조작 을 정의 한 다음 에 우 리 는 유형의 magic method 로 이런 방법 을 실현 합 니 다.
    class Bag:
        """
        constructor:     
        size
        contains
        append
        remove
        iter
        """
        def __init__(self):
            self._items = list()
    
        def __len__(self):
            return len(self._items)
    
        def __contains__(self, item):
            return item in self._items
    
        def add(self, item):
            self._items.append(item)
    
        def remove(self, item):
            assert item in self._items, 'item must in the bag'
            return self._items.remove(item)
    
        def __iter__(self):
            return _BagIterator(self._items)
    
    
    class _BagIterator:
        """             """
        def __init__(self, seq):
            self._bag_items = seq
            self._cur_item = 0
    
        def __iter__(self):
            return self
    
        def __next__(self):
            if self._cur_item < len(self._bag_items):
                item = self._bag_items[self._cur_item]
                self._cur_item += 1
                return item
            else:
                raise StopIteration
    
    
    b = Bag()
    b.add(1)
    b.add(2)
    for i in b:     # for  __iter__  , __next__  
        print(i)
    
    
    """
    # for      
    i = b.__iter__()
    while True:
        try:
            item = i.__next__()
            print(item)
        except StopIteration:
            break
    """

    2 장: array vs list
    array: 길이 가 정 해 져 있 고 조작 이 제한 되 어 있 지만 메모 리 를 절약 합 니 다.내 인생 에서 아직 사용 해 본 적 이 없 는 것 같 지만 python 3.5 에서 나 는 확실히 array 류 가 있어 서 import array 로 직접 가 져 올 수 있다.
    list: 메모 리 를 미리 분배 하고 조작 이 풍부 하지만 메모 리 를 소모 합 니 다.나 는 sys. getsize of 로 실험 을 했다.저 는 개인 적 으로 C + STL 의 vector 와 유사 하 게 가장 자주 사용 하 는 데이터 구 조 를 이해 합 니 다.
  • list. append: 이전에 메모리 가 충분히 분배 되 지 않 았 다 면 새로운 영역 을 다시 개척 한 다음 에 이전의 데 이 터 를 복사 하고 복잡 도 퇴화
  • list. insert: 삽 입 된 영역 을 이동 한 후 모든 요소, O (n)
  • list. pop: pop 의 위치 에 따라 필요 한 복잡 도가 다 릅 니 다. pop (0) 은 O (1) 복잡 도 이 고 pop () 의 첫 번 째 O (n) 복잡 도
  • 입 니 다.
  • list []: slice 작업 copy 데이터 (예약 공간) 를 다른 list
  • 로 이동 합 니 다.
    array 의 ADT 를 실현 합 니 다:
    import ctypes
    
    class Array:
        def __init__(self, size):
            assert size > 0, 'array size must be > 0'
            self._size = size
            PyArrayType = ctypes.py_object * size
            self._elements = PyArrayType()
            self.clear(None)
    
        def __len__(self):
            return self._size
    
        def __getitem__(self, index):
            assert index >= 0 and index < len(self), 'out of range'
            return self._elements[index]
    
        def __setitem__(self, index, value):
            assert index >= 0 and index < len(self), 'out of range'
            self._elements[index] = value
    
        def clear(self, value):
            """        value """
            for i in range(len(self)):
                self._elements[i] = value
    
        def __iter__(self):
            return _ArrayIterator(self._elements)
    
    
    class _ArrayIterator:
        def __init__(self, items):
            self._items = items
            self._idx = 0
    
        def __iter__(self):
            return self
    
        def __next__(self):
            if self._idex < len(self._items):
                val = self._items[self._idx]
                self._idex += 1
                return val
            else:
                raise StopIteration

    Two-Demensional Arrays
    class Array2D:
        """       
        Array2D(nrows, ncols):    constructor
        numRows()
        numCols()
        clear(value)
        getitem(i, j)
        setitem(i, j, val)
        """
        def __init__(self, numrows, numcols):
            self._the_rows = Array(numrows)     #      
            for i in range(numrows):
                self._the_rows[i] = Array(numcols)
    
        @property
        def numRows(self):
            return len(self._the_rows)
    
        @property
        def NumCols(self):
            return len(self._the_rows[0])
    
        def clear(self, value):
            for row in range(self.numRows):
                row.clear(value)
    
        def __getitem__(self, ndx_tuple):    # ndx_tuple: (x, y)
            assert len(ndx_tuple) == 2
            row, col = ndx_tuple[0], ndx_tuple[1]
            assert (row >= 0 and row < self.numRows and
                    col >= 0 and col < self.NumCols)
    
            the_1d_array = self._the_rows[row]
            return the_1d_array[col]
    
        def __setitem__(self, ndx_tuple, value):
            assert len(ndx_tuple) == 2
            row, col = ndx_tuple[0], ndx_tuple[1]
            assert (row >= 0 and row < self.numRows and
                    col >= 0 and col < self.NumCols)
            the_1d_array = self._the_rows[row]
            the_1d_array[col] = value

    The Matrix ADT, m 줄, n 열.이것 은 역시 pandas 로 행렬 을 처리 하 는 것 이 좋 습 니 다. 스스로 실현 하 는 것 이 비교적 * 아 픕 니 다.
    class Matrix:
        """    pandas DataFrame
        Matrix(rows, ncols): constructor
        numCols()
        getitem(row, col)
        setitem(row, col, val)
        scaleBy(scalar):      scalar
        transpose():   transpose  
        add(rhsMatrix):    size must be the same
        subtract(rhsMatrix)
        multiply(rhsMatrix)
        """
        def __init__(self, numRows, numCols):
            self._theGrid = Array2D(numRows, numCols)
            self._theGrid.clear(0)
    
        @property
        def numRows(self):
            return len(self._theGrid.numRows())
    
        @property
        def NumCols(self):
            return len(self._theGrid.numCols())
    
        def __getitem__(self, ndxTuple):
            return self._theGrid[ndxTuple[0], ndxTuple[1]]
    
        def __setitem__(self, ndxTuple, scalar):
            self._theGrid[ndxTuple[0], ndxTuple[1]] = scalar
    
        def scaleBy(self, scalar):
            for r in range(self.numRows):
                for c in range(self.numCols):
                    self[r, c] *= scalar
    
        def __add__(self, rhsMatrix):
            assert (rhsMatrix.numRows == self.numRows and
                    rhsMatrix.numCols == self.numCols)
            newMartrix = Matrix(self.numRows, self.numCols)
            for r in range(self.numRows):
                for c in range(self.numCols):
                    newMartrix[r, c] = self[r, c] + rhsMatrix[r, c]

    3 장: Sets and Maps
    list 를 제외 하고 가장 많이 사용 되 는 것 은 python 에 내 장 된 set 와 dict 일 것 입 니 다.
    sets ADT
    A set is a container that stores a collection of unique values over a given comparable domain in which the stored values have no particular ordering.
    class Set:
        """   list  set ADT
        Set()
        length()
        contains(element)
        add(element)
        remove(element)
        equals(element)
        isSubsetOf(setB)
        union(setB)
        intersect(setB)
        difference(setB)
        iterator()
        """
        def __init__(self):
            self._theElements = list()
    
        def __len__(self):
            return len(self._theElements)
    
        def __contains__(self, element):
            return element in self._theElements
    
        def add(self, element):
            if element not in self:
                self._theElements.append(element)
    
        def remove(self, element):
            assert element in self, 'The element must be set'
            self._theElements.remove(element)
    
        def __eq__(self, setB):
            if len(self) != len(setB):
                return False
            else:
                return self.isSubsetOf(setB)
    
        def isSubsetOf(self, setB):
            for element in self:
                if element not in setB:
                    return False
            return True
    
        def union(self, setB):
            newSet = Set()
            newSet._theElements.extend(self._theElements)
            for element in setB:
                if element not in self:
                    newSet._theElements.append(element)
            return newSet

    Maps or Dict: 키 값 쌍, python 내 부 는 hash 로 이 루어 집 니 다.
    class Map:
        """ Map ADT list implemention
        Map()
        length()
        contains(key)
        add(key, value)
        remove(key)
        valudOf(key)
        iterator()
        """
        def __init__(self):
            self._entryList = list()
    
        def __len__(self):
            return len(self._entryList)
    
        def __contains__(self, key):
            ndx = self._findPosition(key)
            return ndx is not None
    
        def add(self, key, value):
            ndx = self._findPosition(key)
            if ndx is not None:
                self._entryList[ndx].value = value
                return False
            else:
                entry = _MapEntry(key, value)
                self._entryList.append(entry)
                return True
    
        def valueOf(self, key):
            ndx = self._findPosition(key)
            assert ndx is not None, 'Invalid map key'
            return self._entryList[ndx].value
    
        def remove(self, key):
            ndx = self._findPosition(key)
            assert ndx is not None, 'Invalid map key'
            self._entryList.pop(ndx)
    
        def __iter__(self):
            return _MapIterator(self._entryList)
    
        def _findPosition(self, key):
            for i in range(len(self)):
                if self._entryList[i].key == key:
                    return i
            return None
    
    
    class _MapEntry:    # or use collections.namedtuple('_MapEntry', 'key,value')
        def __init__(self, key, value):
            self.key = key
            self.value = value

    The multiArray ADT, 다 차원 배열 은 보통 1 차원 배열 로 시 뮬 레이 션 을 한 다음 에 계산 을 통 해 요 소 를 가 져 옵 니 다.
    class MultiArray:
        """ row-major or column-marjor ordering, this is row-major ordering
        MultiArray(d1, d2, ...dn)
        dims():   the number of dimensions
        length(dim): the length of given array dimension
        clear(value)
        getitem(i1, i2, ... in), index(i1,i2,i3) = i1*(d2*d3) + i2*d3 + i3
        setitem(i1, i2, ... in)
            :index(i1,i2,...in) = i1*f1 + i2*f2 + ... + i(n-1)*f(n-1) + in*1
        """
        def __init__(self, *dimensions):
            # Implementation of MultiArray ADT using a 1-D # array,        。。。
            assert len(dimensions) > 1, 'The array must have 2 or more dimensions'
            self._dims = dimensions
            # Compute to total number of elements in the array
            size = 1
            for d in dimensions:
                assert d > 0, 'Dimensions must be > 0'
                size *= d
            # Create the 1-D array to store the elements
            self._elements = Array(size)
            # Create a 1-D array to store the equation factors
            self._factors = Array(len(dimensions))
            self._computeFactors()
    
        @property
        def numDims(self):
            return len(self._dims)
    
        def length(self, dim):
            assert dim > 0 and dim < len(self._dims), 'Dimension component out of range'
            return self._dims[dim-1]
    
        def clear(self, value):
            self._elements.clear(value)
    
        def __getitem__(self, ndxTuple):
            assert len(ndxTuple) == self.numDims, 'Invalid # of array subscripts'
            index = self._computeIndex(ndxTuple)
            assert index is not None, 'Array subscript out of range'
            return self._elements[index]
    
        def __setitem__(self, ndxTuple, value):
            assert len(ndxTuple) == self.numDims, 'Invalid # of array subscripts'
            index = self._computeIndex(ndxTuple)
            assert index is not None, 'Array subscript out of range'
            self._elements[index] = value
    
        def _computeIndex(self, ndxTuple):
            # using the equation: i1*f1 + i2*f2 + ... + in*fn
            offset = 0
            for j in range(len(ndxTuple)):
                if ndxTuple[j] < 0 or ndxTuple[j] >= self._dims[j]:
                    return None
                else:
                    offset += ndexTuple[j] * self._factors[j]
            return offset

    4 장: 알고리즘 분석
    일반적으로 큰 O 표기 법 을 사용 하여 알고리즘 의 평균 시간 복잡 도 를 평가 합 니 다. 1 < log (n) < n < nlog (n) < n ^ 2 < n ^ 3 < a ^ n.자주 사용 하 는 데이터 구조 작업 의 평균 시간 복잡 도 를 이해 하 는 것 은 더욱 효율 적 인 데이터 구 조 를 사용 하 는 데 유리 하 다. 물론 시간 과 공간 에서 평가 해 야 한다. 어떤 조작 은 심지어 퇴화 하기 도 한다. 예 를 들 어 list 의 append 작업 은 list 공간 이 부족 하면 새로운 공간 을 개척 하고 작업 복잡 도 는 O (n) 로 퇴화 하 며 가끔 은 평균 노점 분석 (amortized) 을 사용 해 야 한다.
    5 장: 검색 및 정렬
    정렬 과 찾기 는 가장 기본 적 이 고 빈번 한 작업 입 니 다. python 에는 in 연산 자 와 bisect 2 분 작업 모듈 이 내장 되 어 있 습 니 다. 정렬 작업 을 수행 하기 위해 sorted 방법 이 내장 되 어 있 습 니 다.2 점 과 빠 른 줄 도 면접 에서 자주 볼 수 있 는 것 으로 본 장 은 기본 적 인 정렬 과 찾기 를 말한다.
    def binary_search(sorted_seq, val):
        """        bisect.bisect_left """
        low = 0
        high = len(sorted_seq) - 1
        while low <= high:
            mid = (high + low) // 2
            if sorted_seq[mid] == val:
                return mid
            elif val < sorted_seq[mid]:
                high = mid - 1
            else:
                low = mid + 1
        return low
    
    def bubble_sort(seq):    # O(n^2), n(n-1)/2 = 1/2(n^2 + n)
        n = len(seq)
        for i in range(n):
            for j in range(n-1):    #                   
                if seq[j] > seq[i]:
                    seq[j], seq[i] = seq[i], seq[j]    # swap seq[j], seq[i]
        #          ,    flag,                   
    
    def select_sort(seq):
        """          ,            ,          """
        n = len(seq)
        for i in range(n-1):
            min_idx = i    # assume the ith element is the smallest
            for j in range(i+1, n):
                if seq[j] < seq[min_idx]:   # find the minist element index
                    min_idx = j
            if min_idx != i:    # swap
                seq[i] = seq[min_idx]
    
    
    def insertion_sort(seq):
        """                    ,          ���   """
        n = len(seq)
        for i in range(1, n):
            value = seq[i]    # save the value to be positioned
            # find the position where value fits in the ordered part of the list
            pos = i
            while pos > 0 and value < seq[pos-1]:
                # Shift the items to the right during the search
                seq[pos] = seq[pos-1]
                pos -= 1
            seq[pos] = value
    
    
    def merge_sorted_list(listA, listB):
        """          """
        new_list = list()
        a = b = 0
        while a < len(listA) and b < len(listB):
            if listA[a] < listB[b]:
                new_list.append(listA[a])
                a += 1
            else:
                new_list.append(listB[b])
                b += 1
    
        while a < len(listA):
            new_list.append(listA[a])
            a += 1
    
        while b < len(listB):
            new_list.append(listB[b])
            b += 1
    
        return new_list

    6 장: 링크 된 구조
    list 는 가장 자주 사용 하 는 데이터 구조 이지 만 list 는 중간 에 요 소 를 증감 할 때 효율 이 낮 습 니 다. 이때 linked list 가 더욱 적합 합 니 다. 단점 은 요 소 를 얻 는 평균 시간 복잡 도가 O (n) 로 바 뀌 었 다 는 것 입 니 다.
    #      
    class ListNode:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    
    def travsersal(head, callback):
        curNode = head
        while curNode is not None:
            callback(curNode.data)
            curNode = curNode.next
    
    
    def unorderdSearch(head, target):
        curNode = head
        while curNode is not None and curNode.data != target:
            curNode = curNode.next
        return curNode is not None
    
    
    # Given the head pointer, prepend an item to an unsorted linked list.
    def prepend(head, item):
        newNode = ListNode(item)
        newNode.next = head
        head = newNode
    
    
    # Given the head reference, remove a target from a linked list
    def remove(head, target):
        predNode = None
        curNode = head
        while curNode is not None and curNode.data != target:
            #     
            predNode = curNode
            curNode = curNode.data
        if curNode is not None:
            if curNode is head:
                head = curNode.next
            else:
                predNode.next = curNode.next

    7 장: 스 택
    스 택 도 컴퓨터 에서 많이 사용 하 는 데이터 구조 입 니 다. 스 택 은 후진 에서 먼저 나 오 는 데이터 구조 로 한 통 에 접 시 를 넣 는 것 으로 이해 할 수 있 습 니 다. 먼저 넣 은 것 은 땅 에 깔 리 고 접 시 를 꺼 낼 때 나중에 놓 은 것 은 먼저 꺼 냅 니 다.
    class Stack:
        """ Stack ADT, using a python list
        Stack()
        isEmpty()
        length()
        pop(): assert not empty
        peek(): assert not empty, return top of non-empty stack without removing it
        push(item)
        """
        def __init__(self):
            self._items = list()
    
        def isEmpty(self):
            return len(self) == 0
    
        def __len__(self):
            return len(self._items)
    
        def peek(self):
            assert not self.isEmpty()
            return self._items[-1]
    
        def pop(self):
            assert not self.isEmpty()
            return self._items.pop()
    
        def push(self, item):
            self._items.append(item)
    
    
    class Stack:
        """ Stack ADT, use linked list
          list     ,        push  ,list            O(n)
         linked list           O(1)
        """
        def __init__(self):
            self._top = None    # top  , _StackNode or None
            self._size = 0    # int
    
        def isEmpty(self):
            return self._top is None
    
        def __len__(self):
            return self._size
    
        def peek(self):
            assert not self.isEmpty()
            return self._top.item
    
        def pop(self):
            assert not self.isEmpty()
            node = self._top
            self.top = self._top.next
            self._size -= 1
            return node.item
    
        def _push(self, item):
            self._top = _StackNode(item, self._top)
            self._size += 1
    
    
    class _StackNode:
        def __init__(self, item, link):
            self.item = item
            self.next = link

    8 장: Queues
    대기 열 도 자주 사용 하 는 데이터 구조 입 니 다. 예 를 들 어 메 시 지 를 보 내 는 등 celery 는 redis 가 제공 하 는 list 를 사용 하여 메시지 대기 열 을 실현 할 수 있 습 니 다.이 장 에서 우 리 는 list 와 linked list 로 대기 열과 우선 순위 대기 열 을 실현 합 니 다.
    class Queue:
        """ Queue ADT, use list。list  ,    push pop     O(n)
        Queue()
        isEmpty()
        length()
        enqueue(item)
        dequeue()
        """
        def __init__(self):
            self._qList = list()
    
        def isEmpty(self):
            return len(self) == 0
    
        def __len__(self):
            return len(self._qList)
    
        def enquue(self, item):
            self._qList.append(item)
    
        def dequeue(self):
            assert not self.isEmpty()
            return self._qList.pop(0)
    
    
    from array import Array    # Array      Array ADT
    class Queue:
        """
        circular Array ,        。list  append pop      ,  
                             O(1),           。
        """
        def __init__(self, maxSize):
            self._count = 0
            self._front = 0
            self._back = maxSize - 1
            self._qArray = Array(maxSize)
    
        def isEmpty(self):
            return self._count == 0
    
        def isFull(self):
            return self._count == len(self._qArray)
    
        def __len__(self):
            return len(self._count)
    
        def enqueue(self, item):
            assert not self.isFull()
            maxSize = len(self._qArray)
            self._back = (self._back + 1) % maxSize     #      
            self._qArray[self._back] = item
            self._count += 1
    
        def dequeue(self):
            assert not self.isFull()
            item = self._qArray[self._front]
            maxSize = len(self._qArray)
            self._front = (self._front + 1) % maxSize
            self._count -= 1
            return item
    
    class _QueueNode:
        def __init__(self, item):
            self.item = item
    
    
    class Queue:
        """ Queue ADT, linked list   。                ,  
               linked list  。
        """
        def __init__(self):
            self._qhead = None
            self._qtail = None
            self._qsize = 0
    
        def isEmpty(self):
            return self._qhead is None
    
        def __len__(self):
            return self._count
    
        def enqueue(self, item):
            node = _QueueNode(item)    #               
            if self.isEmpty():
                self._qhead = node
            else:
                self._qtail.next = node
            self._qtail = node
            self._qcount += 1
    
        def dequeue(self):
            assert not self.isEmpty(), 'Can not dequeue from an empty queue'
            node = self._qhead
            if self._qhead is self._qtail:
                self._qtail = None
            self._qhead = self._qhead.next    #      
            self._count -= 1
            return node.item
    
    
    class UnboundedPriorityQueue:
        """ PriorityQueue ADT:    item     p,     dequeue
            :
        - bounded PriorityQueue:           [0...p)
        - unbounded PriorityQueue:       
    
        PriorityQueue()
        BPriorityQueue(numLevels): create a bounded PriorityQueue with priority in range
            [0, numLevels-1]
        isEmpty()
        length()
        enqueue(item, priority):    bounded PriorityQueue, priority      
        dequeue():         ,       FIFO  
    
        -       :
        1.          ,              ,    O(n)
        2.        ,             ,     O(1)
        (     list  list.append pop             )
        """
        from collections import namedtuple
        _PriorityQEntry = namedtuple('_PriorityQEntry', 'item, priority')
    
        #     1,   list  unbounded PriorityQueue
        def __init__(self):
            self._qlist = list()
    
        def isEmpty(self):
            return len(self) == 0
    
        def __len__(self):
            return len(self._qlist)
    
        def enqueue(self, item, priority):
            entry = UnboundedPriorityQueue._PriorityQEntry(item, priority)
            self._qlist.append(entry)
    
        def deque(self):
            assert not self.isEmpty(), 'can not deque from an empty queue'
            highest = self._qlist[0].priority
            for i in range(len(self)):    #     O(n),         
                if self._qlist[i].priority < highest:
                    highest = self._qlist[i].priority
            entry = self._qlist.pop(highest)
            return entry.item
    
    
    class BoundedPriorityQueue:
        """ BoundedPriorityQueue ADT, linked list  。         BoundedPriorityQueue
                BoundedPriorityQueue ? BoundedPriorityQueue        [0, maxPriority-1]
           UnboundedPriorityQueue,                 item,    
         O(n)   ,     BoundedPriorityQueue,               ,
              。         ,                    。
        (         ,   )
    
        qlist
        [0] -> ["white"]
        [1]
        [2] -> ["black", "green"]
        [3] -> ["purple", "yellow"]
        """
        # Implementation of the bounded Priority Queue ADT using an array of #
        # queues in which the queues are implemented using a linked list.
        from array import Array    #        ADT
    
        def __init__(self, numLevels):
            self._qSize = 0
            self._qLevels = Array(numLevels)
            for i in range(numLevels):
                self._qLevels[i] = Queue()    #       linked list   Queue
    
        def isEmpty(self):
            return len(self) == 0
    
        def __len__(self):
            return len(self._qSize)
    
        def enqueue(self, item, priority):
            assert priority >= 0 and priority < len(self._qLevels), 'invalid priority'
            self._qLevel[priority].enquue(item)    #      priority       
    
        def deque(self):
            assert not self.isEmpty(), 'can not deque from an empty queue'
            i = 0
            p = len(self._qLevels)
            while i < p and not self._qLevels[i].isEmpty():    #          
                i += 1
            return self._qLevels[i].dequeue()
    

    9 장: 고급 링크 목록
     
    이전에 소 개 된 단일 체인 테이블 은 하나의 체인 테이블 노드 에 data 와 next 필드 만 있 고 본 장 은 고급 체인 테이블 을 소개 한다.
    Doubly Linked List, 더 블 링크, 각 노드 에 prev 가 앞 노드 를 가리 키 고 있 습 니 다.더 블 링크 는 텍스트 편집기 의 buffer 를 만 드 는 데 사용 할 수 있 습 니 다.
    class DListNode:
        def __init__(self, data):
            self.data = data
            self.prev = None
            self.next = None
    
    
    def revTraversa(tail):
        curNode = tail
        while cruNode is not None:
            print(curNode.data)
            curNode = curNode.prev
    
    
    def search_sorted_doubly_linked_list(head, tail, probe, target):
        """ probing technique   ,      ,           O(n)
        searching a sorted doubly linked list using the probing technique
        Args:
            head (DListNode obj)
            tail (DListNode obj)
            probe (DListNode or None)
            target (DListNode.data): data to search
        """
        if head is None:    # make sure list is not empty
            return False
        if probe is None:    # if probe is null, initialize it to first node
            probe = head
    
        # if the target comes before the probe node, we traverse backward, otherwise
        # traverse forward
        if target < probe.data:
            while probe is not None and target <= probe.data:
                if target == probe.dta:
                    return True
                else:
                    probe = probe.prev
        else:
            while probe is not None and target >= probe.data:
                if target == probe.data:
                    return True
                else:
                    probe = probe.next
        return False
    
    
    def insert_node_into_ordered_doubly_linekd_list(value):
        """       ,         ,      """
        newnode = DListNode(value)
    
        if head is None:    # empty list
            head = newnode
            tail = head
    
        elif value < head.data:    # insert before head
            newnode.next = head
            head.prev = newnode
            head = newnode
    
        elif value > tail.data:    # insert after tail
            newnode.prev = tail
            tail.next = newnode
            tail = newnode
    
        else:    # insert into middle
            node = head
            while node is not None and node.data < value:
                node = node.next
            newnode.next = node
            newnode.prev = node.prev
            node.prev.next = newnode
            node.prev = newnode

    순환 링크
    def travrseCircularList(listRef):
        curNode = listRef
        done = listRef is None
        while not None:
            curNode = curNode.next
            print(curNode.data)
            done = curNode is listRef   #        
    
    
    def searchCircularList(listRef, target):
        curNode = listRef
        done = listRef is None
        while not done:
            curNode = curNode.next
            if curNode.data == target:
                return True
            else:
                done = curNode is listRef or curNode.data > target
        return False
    
    
    def add_newnode_into_ordered_circular_linked_list(listRef, value):
        """        
        1.     ;2.    ;3.    ;4.       
        """
        newnode = ListNode(value)
        if listRef is None:    # empty list
            listRef = newnode
            newnode.next = newnode
    
        elif value < listRef.next.data:    # insert in front
            newnode.next = listRef.next
            listRef.next = newnode
    
        elif value > listRef.data:    # insert in back
            newnode.next = listRef.next
            listRef.next = newnode
            listRef = newnode
    
        else:    # insert in the middle
            preNode = None
            curNode = listRef
            done = listRef is None
            while not done:
                preNode = curNode
                preNode = curNode.next
                done = curNode is listRef or curNode.data > value
    
            newnode.next = curNode
            preNode.next = newnode

    10 장: Recursion
    Recursion is a process for solving problems by subdividing a larger problem into smaller cases of the problem itself and then solving the smaller, more trivial parts.
    재 귀 함수: 자신의 함수 호출
    #     :       ,           ,       
    def printRev(n):
        if n > 0:
            print(n)
            printRev(n-1)
    
    
    printRev(3)    #  10   1
    
    
    #      ,print               
    def printInOrder(n):
        if n > 0:
            printInOrder(n-1)
            print(n)    #                    n==1      ,    
                        #   ,    print  ,   n==1,        ,      
    
    printInOrder(3)    #     

    Properties of Recursion: stack 으로 해결 하 는 문 제 는 재 귀적 으로 해결 할 수 있 습 니 다.
  • A recursive solution must contain a base case; 재 귀 출구, 대표 최 자식 문제 (n = = 0 인쇄 종료)
  • A recursive solution must contain a recursive case; 분해 가능 한 하위 문제
  • 리 커 시 브 솔 루 션 은 기본 케이스 를 향 해 진행 해 야 합 니 다. n 을 점차 줄 여 n 을 재 귀 출구 에 가 깝 게 합 니 다
  • Tail Recursion: occurs when a function includes a single recursive call as the last statement of the function. In this case, a stack is not needed to store values to te used upon the return of the recursive call and thus a solution can be implemented using a iterative loop instead.
    # Recursive Binary Search
    
    def recBinarySearch(target, theSeq, first, last):
        #                     
        if first > last:    #     1
            return False
        else:
            mid = (first + last) // 2
            if theSeq[mid] == target:
                return True    #     2
            elif theSeq[mid] > target:
                return recBinarySearch(target, theSeq, first, mid - 1)
            else:
                return recBinarySearch(target, theSeq, mid + 1, last)

    11 장: Hash Tables
     
    비교 검색 (선형 검색, 질서 있 는 배열 의 2 분 검색) 을 바탕 으로 가장 좋 은 시간 복잡 도 는 O (logn) 에 만 도달 할 수 있 습 니 다. hash 를 이용 하여 O (1) 검색 을 실현 할 수 있 습 니 다. python 내 장 된 dict 의 실현 방식 은 hash 입 니 다. dict 의 key 가 반드시 실현 되 어야 한 다 는 것 을 알 게 될 것 입 니 다.hash__와eq__방법의
    Hashing: hashing is the process of mapping a search a key to a limited range of array indeices with the goal of providing direct access to the keys.
    hash 방법 은 키 에 hash 값 을 계산 하 는 데 사용 되 는 hash 함수 가 있 습 니 다.키 가 hash 함수 에 따라 계 산 된 아래 표 시 를 계산 하 는 동시에 충돌 이 발생 합 니 다.충돌 을 해결 하 는 방법 은 여러 가지 가 있 습 니 다. 예 를 들 어 모든 슬롯 을 링크 로 만 들 고 충돌 할 때마다 이 슬롯 링크 의 끝 에 놓 지만 조회 시간 은 퇴화 되 고 더 이상 O (1) 가 아 닙 니 다.또 하나의 탐사 방식 은 키 의 홈 이 충돌 할 때 하나의 계산 방식 에 따라 다음 빈 홈 을 찾 아 저장 하고 탐사 방식 은 선형 탐사, 이차 탐사 법 등 이 있 으 며 cpython 해석 기 는 이차 탐사 법 을 사용한다.또 하나의 문 제 는 python 이 사용 하 는 슬롯 의 수량 이 미리 분 배 된 2 / 3 보다 많 을 때 메모 리 를 재배 치 하고 예전 의 데 이 터 를 복사 하기 때문에 가끔 dict 의 add 작업 대가 가 비교적 높 고 공간 을 희생 하지만 O (1) 의 조회 효율 을 항상 보장 할 수 있다 는 것 이다.만약 대량의 데이터 가 있다 면, Bloomfilter 나 redis 가 제공 하 는 HyperLogLog 를 사용 하 는 것 을 권장 합 니 다.
    관심 이 있다 면 c 해석 기 가 어떻게 실현 하 는 python dict 대상: Python dictionary implementation 을 소개 합 니 다.우 리 는 Python 을 사용 하여 유사 한 hash 구 조 를 실현 합 니 다.
    import ctypes
    
    class Array:  #          ADT,    HashMap      
        def __init__(self, size):
            assert size > 0, 'array size must be > 0'
            self._size = size
            PyArrayType = ctypes.py_object * size
            self._elements = PyArrayType()
            self.clear(None)
    
        def __len__(self):
            return self._size
    
        def __getitem__(self, index):
            assert index >= 0 and index < len(self), 'out of range'
            return self._elements[index]
    
        def __setitem__(self, index, value):
            assert index >= 0 and index < len(self), 'out of range'
            self._elements[index] = value
    
        def clear(self, value):
            """        value """
            for i in range(len(self)):
                self._elements[i] = value
    
        def __iter__(self):
            return _ArrayIterator(self._elements)
    
    
    class _ArrayIterator:
        def __init__(self, items):
            self._items = items
            self._idx = 0
    
        def __iter__(self):
            return self
    
        def __next__(self):
            if self._idx < len(self._items):
                val = self._items[self._idx]
                self._idx += 1
                return val
            else:
                raise StopIteration
    
    
    class HashMap:
        """ HashMap ADT  ,   python   dict
                :
        1.     HashMap.UNUSED。           ,       UNUSEd         
        2.     remove ,    HashMap.EMPTY,              key
        3.      _MapEntry  
        """
    
        class _MapEntry:    #        
            def __init__(self, key, value):
                self.key = key
                self.value = value
    
        UNUSED = None    #        ,           ,    is   
        EMPTY = _MapEntry(None, None)     #           
    
        def __init__(self):
            self._table = Array(7)    #    7  
            self._count = 0
            #   2/3          ,load factor = 2/3
            self._maxCount = len(self._table) - len(self._table) // 3
    
        def __len__(self):
            return self._count
    
        def __contains__(self, key):
            slot = self._findSlot(key, False)
            return slot is not None
    
        def add(self, key, value):
            if key in self:    #     value
                slot = self._findSlot(key, False)
                self._table[slot].value = value
                return False
            else:
                slot = self._findSlot(key, True)
                self._table[slot] = HashMap._MapEntry(key, value)
                self._count += 1
                if self._count == self._maxCount:    #   2/3   rehash
                    self._rehash()
                return True
    
        def valueOf(self, key):
            slot = self._findSlot(key, False)
            assert slot is not None, 'Invalid map key'
            return self._table[slot].value
    
        def remove(self, key):
            """ remove      EMPTY"""
            assert key in self, 'Key error %s' % key
            slot = self._findSlot(key, forInsert=False)
            value = self._table[slot].value
            self._count -= 1
            self._table[slot] = HashMap.EMPTY
            return value
    
        def __iter__(self):
            return _HashMapIteraotr(self._table)
    
        def _slot_can_insert(self, slot):
            return (self._table[slot] is HashMap.EMPTY or
                    self._table[slot] is HashMap.UNUSED)
    
        def _findSlot(self, key, forInsert=False):
            """        ,        ,        
            Args:
                forInsert (bool): if the search is for an insertion
            Returns:
                slot or None
            """
            slot = self._hash1(key)
            step = self._hash2(key)
            _len = len(self._table)
    
            if not forInsert:    #       key
                while self._table[slot] is not HashMap.UNUSED:
                    #       UNUSED,    
                    if self._table[slot] is HashMap.EMPTY:
                        slot = (slot + step) % _len
                        continue
                    elif self._table[slot].key == key:
                        return slot
                    slot = (slot + step) % _len
                return None
    
            else:    #     key
                while not self._slot_can_insert(slot):    #               
                    slot = (slot + step) % _len
                return slot
    
        def _rehash(self):    #          2/3        table
            origTable = self._table
            newSize = len(self._table) * 2 + 1    #    2*n+1 
            self._table = Array(newSize)
    
            self._count = 0
            self._maxCount = newSize - newSize // 3
    
            #     key value     table
            for entry in origTable:
                if entry is not HashMap.UNUSED and entry is not HashMap.EMPTY:
                    slot = self._findSlot(entry.key, True)
                    self._table[slot] = entry
                    self._count += 1
    
        def _hash1(self, key):
            """   key hash """
            return abs(hash(key)) % len(self._table)
    
        def _hash2(self, key):
            """ key             """
            return 1 + abs(hash(key)) % (len(self._table)-2)
    
    
    class _HashMapIteraotr:
        def __init__(self, array):
            self._array = array
            self._idx = 0
    
        def __iter__(self):
            return self
    
        def __next__(self):
            if self._idx < len(self._array):
                if self._array[self._idx] is not None and self._array[self._idx].key is not None:
                    key = self._array[self._idx].key
                    self._idx += 1
                    return key
                else:
                    self._idx += 1
            else:
                raise StopIteration
    
    
    def print_h(h):
        for idx, i in enumerate(h):
            print(idx, i)
        print('
    ') def test_HashMap(): """ , """ h = HashMap() assert len(h) == 0 h.add('a', 'a') assert h.valueOf('a') == 'a' assert len(h) == 1 a_v = h.remove('a') assert a_v == 'a' assert len(h) == 0 h.add('a', 'a') h.add('b', 'b') assert len(h) == 2 assert h.valueOf('b') == 'b' b_v = h.remove('b') assert b_v == 'b' assert len(h) == 1 h.remove('a') assert len(h) == 0 n = 10 for i in range(n): h.add(str(i), i) assert len(h) == n print_h(h) for i in range(n): assert str(i) in h for i in range(n): h.remove(str(i)) assert len(h) == 0

    12 장: 고급 정렬
     
    제5 장 은 기본 적 인 정렬 알고리즘 을 소개 하고 이 장 은 고급 정렬 알고리즘 을 소개 한다.
    병합 정렬 (mergesort): 분할 방법
    def merge_sorted_list(listA, listB):
        """         ,O(max(m, n)) ,m n     """
        print('merge left right list', listA, listB, end='')
        new_list = list()
        a = b = 0
        while a < len(listA) and b < len(listB):
            if listA[a] < listB[b]:
                new_list.append(listA[a])
                a += 1
            else:
                new_list.append(listB[b])
                b += 1
    
        while a < len(listA):
            new_list.append(listA[a])
            a += 1
    
        while b < len(listB):
            new_list.append(listB[b])
            b += 1
    
        print(' ->', new_list)
        return new_list
    
    
    def mergesort(theList):
        """ O(nlogn),log   ,  n   
        mergesort: divided and conquer   
        1.                
        2.               
        """
        print(theList)    #           ,            
        if len(theList) <= 1:    #     
            return theList
        else:
            mid = len(theList) // 2
    
            #           
            left_half = mergesort(theList[:mid])
            right_half = mergesort(theList[mid:])
    
            #           
            newList = merge_sorted_list(left_half, right_half)
            return newList
    
    """                
    [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    [10, 9, 8, 7, 6]
    [10, 9]
    [10]
    [9]
    merge left right list [10] [9] -> [9, 10]
    [8, 7, 6]
    [8]
    [7, 6]
    [7]
    [6]
    merge left right list [7] [6] -> [6, 7]
    merge left right list [8] [6, 7] -> [6, 7, 8]
    merge left right list [9, 10] [6, 7, 8] -> [6, 7, 8, 9, 10]
    [5, 4, 3, 2, 1]
    [5, 4]
    [5]
    [4]
    merge left right list [5] [4] -> [4, 5]
    [3, 2, 1]
    [3]
    [2, 1]
    [2]
    [1]
    merge left right list [2] [1] -> [1, 2]
    merge left right list [3] [1, 2] -> [1, 2, 3]
    merge left right list [4, 5] [1, 2, 3] -> [1, 2, 3, 4, 5]
    """

    빠 른 정렬
    def quicksort(theSeq, first, last):
        """
        quicksort :      ,           ,      (pivot)      
              
        1.      pivot      ,pivot        ,          
        2.             ,      (        2)
        3.  pivot                 
        """
        if first < last:
            pos = partitionSeq(theSeq, first, last)
            #            
            quicksort(theSeq, first, pos - 1)
            quicksort(theSeq, pos + 1, last)
    
    
    def partitionSeq(theSeq, first, last):
        """         ,  pivot      , pivot      """
        pivot = theSeq[first]
        print('before partitionSeq', theSeq)
    
        left = first + 1
        right = last
    
        while True:
            #       pivot  
            while left <= right and theSeq[left] < pivot:
                left += 1
    
            #         pivot  
            while right >= left and theSeq[right] >= pivot:
                right -= 1
    
            if right < left:
                break
            else:
                theSeq[left], theSeq[right] = theSeq[right], theSeq[left]
    
        #  pivot       
        theSeq[first], theSeq[right] = theSeq[right], theSeq[first]
    
        print('after partitionSeq {}: {}\t'.format(theSeq, pivot))
        return right    #   pivot   
    
    
    def test_partitionSeq():
        l = [0,1,2,3,4]
        assert partitionSeq(l, 0, len(l)-1) == 0
        l = [4,3,2,1,0]
        assert partitionSeq(l, 0, len(l)-1) == 4
        l = [2,3,0,1,4]
        assert partitionSeq(l, 0, len(l)-1) == 2
    
    test_partitionSeq()
    
    
    def test_quicksort():
        def _is_sorted(seq):
            for i in range(len(seq)-1):
                if seq[i] > seq[i+1]:
                    return False
            return True
    
        from random import randint
        for i in range(100):
            _len = randint(1, 100)
            to_sort = []
            for i in range(_len):
                to_sort.append(randint(0, 100))
            quicksort(to_sort, 0, len(to_sort)-1)    #           ,       
            print(to_sort)
            assert _is_sorted(to_sort)
    
    test_quicksort()

    빠 른 배열 의 paritionseq 작업 을 이용 하여 우 리 는 또 다른 알고리즘 을 실현 할 수 있 습 니 다. nthelement, 무질서 한 배열 의 k 번 째 요 소 를 빠르게 찾 습 니 다.
    def nth_element(seq, beg, end, k):
        if beg == end:
            return seq[beg]
        pivot_index = partitionSeq(seq, beg, end)
        if pivot_index == k:
            return seq[k]
        elif pivot_index > k:
            return nth_element(seq, beg, pivot_index-1, k)
        else:
            return nth_element(seq, pivot_index+1, end, k)
    
    def test_nth_element():
        from random import shuffle
        n = 10
        l = list(range(n))
        shuffle(l)
        print(l)
        for i in range(len(l)):
            assert nth_element(l, 0, len(l)-1, i) == i
    
    test_nth_element()

    13 장: 바 이 너 리 트 리
    The binary Tree: 이 진 트 리, 노드 마다 많이 하면 두 개의 키 노드 만 있 습 니 다.
    class _BinTreeNode:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None
    
    
    #   depth-first  
    def preorderTrav(subtree):
        """  ( )   """
        if subtree is not None:
            print(subtree.data)
            preorderTrav(subtree.left)
            preorderTrav(subtree.right)
    
    
    def inorderTrav(subtree):
        """  ( )   """
        if subtree is not None:
            preorderTrav(subtree.left)
            print(subtree.data)
            preorderTrav(subtree.right)
    
    
    def postorderTrav(subtree):
        """  ( )   """
        if subtree is not None:
            preorderTrav(subtree.left)
            preorderTrav(subtree.right)
            print(subtree.data)
    
    
    #       (bradth-First Traversal):       ,   queue
    def breadthFirstTrav(bintree):
        from queue import Queue    # py3
        q = Queue()
        q.put(bintree)
        while not q.empty():
            node = q.get()
            print(node.data)
            if node.left is not None:
                q.put(node.left)
            if node.right is not None:
                q.put(node.right)
    
    
    class _ExpTreeNode:
        __slots__ = ('element', 'left', 'right')
    
        def __init__(self, data):
            self.element = data
            self.left = None
            self.right = None
    
        def __repr__(self):
            return '<_exptreenode:>'.format(
                self.element, self.left, self.right)
    
    from queue import Queue
    class ExpressionTree:
        """
            :                        。(        )
            *
           / \
          +   -
         / \  / \
         9  3 8   4
        (9+3) * (8-4)
    
        Expression Tree Abstract Data Type,         
        ExpressionTree(expStr): user string as constructor param
        evaluate(varDict): evaluates the expression and returns the numeric result
        toString(): constructs and retutns a string represention of the expression
    
        Usage:
            vars = {'a': 5, 'b': 12}
            expTree = ExpressionTree("(a/(b-3))")
            print('The result = ', expTree.evaluate(vars))
        """
    
        def __init__(self, expStr):
            self._expTree = None
            self._buildTree(expStr)
    
        def evaluate(self, varDict):
            return self._evalTree(self._expTree, varDict)
    
        def __str__(self):
            return self._buildString(self._expTree)
    
        def _buildString(self, treeNode):
            """                ,              """
            # print(treeNode)
            if treeNode.left is None and treeNode.right is None:
                return str(treeNode.element)    #             
            else:
                expStr = '('
                expStr += self._buildString(treeNode.left)
                expStr += str(treeNode.element)
                expStr += self._buildString(treeNode.right)
                expStr += ')'
                return expStr
    
        def _evalTree(self, subtree, varDict):
            #        ,          ,    
            if subtree.left is None and subtree.right is None:
                #          
                if subtree.element >= '0' and subtree.element <= '9':
                    return int(subtree.element)
                else:    #        
                    assert subtree.element in varDict, 'invalid variable.'
                    return varDict[subtree.element]
            else:    #            
                lvalue = self._evalTree(subtree.left, varDict)
                rvalue = self._evalTree(subtree.right, varDict)
                print(subtree.element)
                return self._computeOp(lvalue, subtree.element, rvalue)
    
        def _computeOp(self, left, op, right):
            assert op
            op_func = {
                '+': lambda left, right: left + right,    # or import operator, operator.add
                '-': lambda left, right: left - right,
                '*': lambda left, right: left * right,
                '/': lambda left, right: left / right,
                '%': lambda left, right: left % right,
            }
            return op_func[op](left, right)
    
        def _buildTree(self, expStr):
            expQ = Queue()
            for token in expStr:    #              
                expQ.put(token)
            self._expTree = _ExpTreeNode(None)    #   root  
            self._recBuildTree(self._expTree, expQ)
    
        def _recBuildTree(self, curNode, expQ):
            token = expQ.get()
            if token == '(':
                curNode.left = _ExpTreeNode(None)
                self._recBuildTree(curNode.left, expQ)
    
                # next token will be an operator: + = * / %
                curNode.element = expQ.get()
                curNode.right = _ExpTreeNode(None)
                self._recBuildTree(curNode.right, expQ)
    
                # the next token will be ')', remmove it
                expQ.get()
    
            else:  # the token is a digit that has to be converted to an int.
                curNode.element = token
    
    
    vars = {'a': 5, 'b': 12}
    expTree = ExpressionTree("((2*7)+8)")
    print(expTree)
    print('The result = ', expTree.evaluate(vars))

    Heap (더미): 이 진 트 리 의 가장 직접적인 응용 은 바로 더 미 를 실현 하 는 것 이다.더 미 는 완전히 이 진 트 리 로 가장 많은 비 잎 노드 의 가 치 는 모두 아이 보다 크 고 가장 작은 비 잎 노드 의 가 치 는 모두 아이 보다 작다.python 에 hepq 모듈 이 내장 되 어 있 습 니 다. 예 를 들 어 내 장 된 hepq 모듈 로 쌓 기 정렬 을 실현 합 니 다.
    #   python   heapq  heap sort
    def heapsort(iterable):
        from heapq import heappush, heappop
        h = []
        for value in iterable:
            heappush(h, value)
        return [heappop(h) for i in range(len(h))]

    그러나 일반적으로 무 더 기 를 실현 할 때 실제 적 으로 몇 개의 노드 로 이 루어 지 는 것 이 아니 라 배열 로 이 루어 져 효율 이 비교적 높다.왜 배열 로 이 루어 질 수 있 습 니까?완전 이 진 트 리 의 성질 때문에 아래 표 시 된 관계 로 노드 간 의 관 계 를 나 타 낼 수 있 습 니 다. MaxHeap 의 docstring 에서 설명 되 었 습 니 다.
    class MaxHeap:
        """
        Heaps:
             ,                ,                
        Heap      ,order property   shape property(a complete binary tree),   
                ,          
            :             , sift-up        
        extract  :        ,          copy     ,sift-down       
    
             heap,      ,               ,         
          ,      i,               :
            parent = (i-1) // 2
            left = 2 * i + 1
            rgiht = 2 * i + 2
                      ,          ,               ,  
            。
    
        """
    
        def __init__(self, maxSize):
            self._elements = Array(maxSize)    #       Array ADT
            self._count = 0
    
        def __len__(self):
            return self._count
    
        def capacity(self):
            return len(self._elements)
    
        def add(self, value):
            assert self._count < self.capacity(), 'can not add to full heap'
            self._elements[self._count] = value
            self._count += 1
            self._siftUp(self._count - 1)
            self.assert_keep_heap()    #      add        
    
        def extract(self):
            assert self._count > 0, 'can not extract from an empty heap'
            value = self._elements[0]    # save root value
            self._count -= 1
            self._elements[0] = self._elements[self._count]    #         root siftDown
            self._siftDown(0)
            self.assert_keep_heap()
            return value
    
        def _siftUp(self, ndx):
            if ndx > 0:
                parent = (ndx - 1) // 2
                # print(ndx, parent)
                if self._elements[ndx] > self._elements[parent]:    # swap
                    self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
                    self._siftUp(parent)    #   
    
        def _siftDown(self, ndx):
            left = 2 * ndx + 1
            right = 2 * ndx + 2
            # determine which node contains the larger value
            largest = ndx
            if (left < self._count and
                self._elements[left] >= self._elements[largest] and
                self._elements[left] >= self._elements[right]):  #                 largest
                largest = left
            elif right < self._count and self._elements[right] >= self._elements[largest]:
                largest = right
            if largest != ndx:
                self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
                self._siftDown(largest)
    
        def __repr__(self):
            return ' '.join(map(str, self._elements))
    
        def assert_keep_heap(self):
            """               add  extract  ,         """
            _len = len(self)
            for i in range(0, int((_len-1)/2)):    #     (     )
                l = 2 * i + 1
                r = 2 * i + 2
                if l < _len and r < _len:
                    assert self._elements[i] >= self._elements[l] and self._elements[i] >= self._elements[r]
    
    def test_MaxHeap():
        """              """
        _len = 10
        h = MaxHeap(_len)
        for i in range(_len):
            h.add(i)
            h.assert_keep_heap()
        for i in range(_len):
            #               ,             
            assert h.extract() == _len-i-1
    
    test_MaxHeap()
    
    def simpleHeapSort(theSeq):
        """       MaxHeap     ,         inplace  """
        if not theSeq:
            return theSeq
        _len = len(theSeq)
        heap = MaxHeap(_len)
        for i in theSeq:
            heap.add(i)
        for i in reversed(range(_len)):
            theSeq[i] = heap.extract()
        return theSeq
    
    
    def test_simpleHeapSort():
        """                       """
        def _is_sorted(seq):
            for i in range(len(seq)-1):
                if seq[i] > seq[i+1]:
                    return False
            return True
    
        from random import randint
        assert simpleHeapSort([]) == []
        for i in range(1000):
            _len = randint(1, 100)
            to_sort = []
            for i in range(_len):
                to_sort.append(randint(0, 100))
            simpleHeapSort(to_sort)    #           ,       
            assert _is_sorted(to_sort)
    
    
    test_simpleHeapSort()

    14 장: 검색 트 리
     
    이차 트 리 성질 찾기: 내부 노드 마다 V,
  • 모든 key 는 V. key 보다 작은 V 의 왼쪽 트 리 에 저 장 됩 니 다.
  • 모든 key 가 V. key 보다 큰 V 의 오른쪽 하위 트 리 가 BST 를 중간 순서 로 옮 겨 다 니 면 상승 순 서 를 얻 을 수 있 는 key 시퀀스
  • class _BSTMapNode:
        __slots__ = ('key', 'value', 'left', 'right')
    
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.left = None
            self.right = None
    
        def __repr__(self):
            return ' left:{}, right:{}'.format(
                self.key, self.value, self.left, self.right)
    
        __str__ = __repr__
    
    
    class BSTMap:
        """ BST,     key payload。 BST      hash    Map ADT.
          :       V,
        1.    V,  key  V.key    V    。
        2.  key  V.key    V    
         BST            key  
        """
        def __init__(self):
            self._root = None
            self._size = 0
            self._rval = None     #   remove    
    
        def __len__(self):
            return self._size
    
        def __iter__(self):
            return _BSTMapIterator(self._root, self._size)
    
        def __contains__(self, key):
            return self._bstSearch(self._root, key) is not None
    
        def valueOf(self, key):
            node = self._bstSearch(self._root, key)
            assert node is not None, 'Invalid map key.'
            return node.value
    
        def _bstSearch(self, subtree, target):
            if subtree is None:    #     ,         key    
                return None
            elif target < subtree.key:
                return self._bstSearch(subtree.left, target)
            elif target > subtree.key:
                return self._bstSearch(subtree.right, target)
            return subtree    #     
    
        def _bstMinumum(self, subtree):
            """                  ,            """
            if subtree is None:
                return None
            elif subtree.left is None:
                return subtree
            else:
                return subtree._bstMinumum(self, subtree.left)
    
        def add(self, key, value):
            """         key value, O(N) """
            node = self._bstSearch(self._root, key)
            if node is not None:    # if key already exists, update value
                node.value = value
                return False
            else:   # insert a new entry
                self._root = self._bstInsert(self._root, key, value)
                self._size += 1
                return True
    
        def _bstInsert(self, subtree, key, value):
            """                  """
            if subtree is None:
                subtree = _BSTMapNode(key, value)
            elif key < subtree.key:
                subtree.left = self._bstInsert(subtree.left, key, value)
            elif key > subtree.key:
                subtree.right = self._bstInsert(subtree.right, key, value)
            #       else   ,       add            key
            return subtree
    
        def remove(self, key):
            """ O(N)
                      :
            1.    :               None
            2.        :       ,               
            3.       :
                (1)       N    S(           )
                (2)  S key N
                (3) N         S(  N        )
            """
            assert key in self, 'invalid map key'
            self._root = self._bstRemove(self._root, key)
            self._size -= 1
            return self._rval
    
        def _bstRemove(self, subtree, target):
            # search for the item in the tree
            if subtree is None:
                return subtree
            elif target < subtree.key:
                subtree.left = self._bstRemove(subtree.left, target)
                return subtree
            elif target > subtree.key:
                subtree.right = self._bstRemove(subtree.right, target)
                return subtree
    
            else:    # found the node containing the item
                self._rval = subtree.value
                if subtree.left is None and subtree.right is None:
                    #   node
                    return None
                elif subtree.left is None or subtree.right is None:
                    #        
                    if subtree.left is not None:
                        return subtree.left
                    else:
                        return subtree.right
                else:   #       
                    successor = self._bstMinumum(subtree.right)
                    subtree.key = successor.key
                    subtree.value = successor.value
                    subtree.right = self._bstRemove(subtree.right, successor.key)
                    return subtree
    
        def __repr__(self):
            return '->'.join([str(i) for i in self])
    
        def assert_keep_bst_property(self, subtree):
            """          add delete       bst    """
            if subtree is None:
                return
            if subtree.left is not None and subtree.right is not None:
                assert subtree.left.value <= subtree.value
                assert subtree.right.value >= subtree.value
                self.assert_keep_bst_property(subtree.left)
                self.assert_keep_bst_property(subtree.right)
    
            elif subtree.left is None and subtree.right is not None:
                assert subtree.right.value >= subtree.value
                self.assert_keep_bst_property(subtree.right)
    
            elif subtree.left is not None and subtree.right is None:
                assert subtree.left.value <= subtree.value
                self.assert_keep_bst_property(subtree.left)
    
    
    class _BSTMapIterator:
        def __init__(self, root, size):
            self._theKeys = Array(size)
            self._curItem = 0
            self._bstTraversal(root)
            self._curItem = 0
    
        def __iter__(self):
            return self
    
        def __next__(self):
            if self._curItem < len(self._theKeys):
                key = self._theKeys[self._curItem]
                self._curItem += 1
                return key
            else:
                raise StopIteration
    
        def _bstTraversal(self, subtree):
            if subtree is not None:
                self._bstTraversal(subtree.left)
                self._theKeys[self._curItem] = subtree.key
                self._curItem += 1
                self._bstTraversal(subtree.right)
    
    
    def test_BSTMap():
        l = [60, 25, 100, 35, 17, 80]
        bst = BSTMap()
        for i in l:
            bst.add(i)
    
    def test_HashMap():
        """        hash   map,   BST   Map   """
        # h = HashMap()
        h = BSTMap()
        assert len(h) == 0
        h.add('a', 'a')
        assert h.valueOf('a') == 'a'
        assert len(h) == 1
    
        a_v = h.remove('a')
        assert a_v == 'a'
        assert len(h) == 0
    
        h.add('a', 'a')
        h.add('b', 'b')
        assert len(h) == 2
        assert h.valueOf('b') == 'b'
        b_v = h.remove('b')
        assert b_v == 'b'
        assert len(h) == 1
        h.remove('a')
    
        assert len(h) == 0
    
        _len = 10
        for i in range(_len):
            h.add(str(i), i)
        assert len(h) == _len
        for i in range(_len):
            assert str(i) in h
        for i in range(_len):
            print(len(h))
            print('bef', h)
            _ = h.remove(str(i))
            assert _ == i
            print('aft', h)
            print(len(h))
        assert len(h) == 0
    
    test_HashMap() 

     
     
     
     
     

    좋은 웹페이지 즐겨찾기