# 最基礎(chǔ)的遍歷無(wú)序列表的查找算法
# 時(shí)間復(fù)雜度O(n)
 
def sequential_search(lis, key):
  length = len(lis)
  for i in range(length):
    if lis[i] == key:
      return i
    else:
      return False
 
if __name__ == '__main__':
  LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
  result = sequential_search(LIST, 123)
  print(result)

# 針對(duì)有序查找表的二分查找算法
 
def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    mid = int((low + high) / 2)
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印折半的次數(shù)
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 99)
  print(result)

# 插值查找算法
 
def binary_search(lis, key):
  low = 0
  high = len(lis) - 1
  time = 0
  while low < high:
    time += 1
    # 計(jì)算mid值是插值算法的核心代碼
    mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
    print("mid=%s, low=%s, high=%s" % (mid, low, high))
    if key < lis[mid]:
      high = mid - 1
    elif key > lis[mid]:
      low = mid + 1
    else:
      # 打印查找的次數(shù)
      print("times: %s" % time)
      return mid
  print("times: %s" % time)
  return False
 
if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = binary_search(LIST, 444)
  print(result)

# 斐波那契查找算法
# 時(shí)間復(fù)雜度O(log(n))
 
def fibonacci_search(lis, key):
  # 需要一個(gè)現(xiàn)成的斐波那契列表。其最大元素的值必須超過(guò)查找表中元素個(gè)數(shù)的數(shù)值。
  F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
     233, 377, 610, 987, 1597, 2584, 4181, 6765,
     10946, 17711, 28657, 46368]
  low = 0
  high = len(lis) - 1
   
  # 為了使得查找表滿足斐波那契特性，在表的最后添加幾個(gè)同樣的值
  # 這個(gè)值是原查找表的最后那個(gè)元素的值
  # 添加的個(gè)數(shù)由F[k]-1-high決定
  k = 0
  while high > F[k]-1:
    k += 1
  print(k)
  i = high
  while F[k]-1 > i:
    lis.append(lis[high])
    i += 1
  print(lis)
   
  # 算法主邏輯。time用于展示循環(huán)的次數(shù)。
  time = 0
  while low <= high:
    time += 1
    # 為了防止F列表下標(biāo)溢出，設(shè)置if和else
    if k < 2:
      mid = low
    else:
      mid = low + F[k-1]-1
     
    print("low=%s, mid=%s, high=%s" % (low, mid, high))
    if key < lis[mid]:
      high = mid - 1
      k -= 1
    elif key > lis[mid]:
      low = mid + 1
      k -= 2
    else:
      if mid <= high:
        # 打印查找的次數(shù)
        print("times: %s" % time)
        return mid
      else:
        print("times: %s" % time)
        return high
  print("times: %s" % time)
  return False
 
if __name__ == '__main__':
  LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
  result = fibonacci_search(LIST, 444)
  print(result)

# 二叉樹(shù)查找 Python實(shí)現(xiàn)
class BSTNode:
    """
    定義一個(gè)二叉樹(shù)節(jié)點(diǎn)類(lèi)。
    以討論算法為主，忽略了一些諸如對(duì)數(shù)據(jù)類(lèi)型進(jìn)行判斷的問(wèn)題。
    """
    def __init__(self, data, left=None, right=None):
        """
        初始化
        :param data: 節(jié)點(diǎn)儲(chǔ)存的數(shù)據(jù)
        :param left: 節(jié)點(diǎn)左子樹(shù)
        :param right: 節(jié)點(diǎn)右子樹(shù)
        """
        self.data = data
        self.left = left
        self.right = right


class BinarySortTree:
    """
    基于BSTNode類(lèi)的二叉查找樹(shù)。維護(hù)一個(gè)根節(jié)點(diǎn)的指針。
    """
    def __init__(self):
        self._root = None

    def is_empty(self):
        return self._root is None

    def search(self, key):
        """
        關(guān)鍵碼檢索
        :param key: 關(guān)鍵碼
        :return: 查詢(xún)節(jié)點(diǎn)或None
        """
        bt = self._root
        while bt:
            entry = bt.data
            if key < entry:
                bt = bt.left
            elif key > entry:
                bt = bt.right
            else:
                return entry
        return None

    def insert(self, key):
        """
        插入操作
        :param key:關(guān)鍵碼 
        :return: 布爾值
        """
        bt = self._root
        if not bt:
            self._root = BSTNode(key)
            return
        while True:
            entry = bt.data
            if key < entry:
                if bt.left is None:
                    bt.left = BSTNode(key)
                    return
                bt = bt.left
            elif key > entry:
                if bt.right is None:
                    bt.right = BSTNode(key)
                    return
                bt = bt.right
            else:
                bt.data = key
                return

    def delete(self, key):
        """
        二叉查找樹(shù)最復(fù)雜的方法
        :param key: 關(guān)鍵碼
        :return: 布爾值
        """
        p, q = None, self._root     # 維持p為q的父節(jié)點(diǎn)，用于后面的鏈接操作
        if not q:
            print("空樹(shù)！")
            return
        while q and q.data != key:
            p = q
            if key < q.data:
                q = q.left
            else:
                q = q.right
            if not q:               # 當(dāng)樹(shù)中沒(méi)有關(guān)鍵碼key時(shí)，結(jié)束退出。
                return
        # 上面已將找到了要?jiǎng)h除的節(jié)點(diǎn)，用q引用。而p則是q的父節(jié)點(diǎn)或者None（q為根節(jié)點(diǎn)時(shí)）。
        if not q.left:
            if p is None:
                self._root = q.right
            elif q is p.left:
                p.left = q.right
            else:
                p.right = q.right
            return
        # 查找節(jié)點(diǎn)q的左子樹(shù)的最右節(jié)點(diǎn)，將q的右子樹(shù)鏈接為該節(jié)點(diǎn)的右子樹(shù)
        # 該方法可能會(huì)增大樹(shù)的深度，效率并不算高。可以設(shè)計(jì)其它的方法。
        r = q.left
        while r.right:
            r = r.right
        r.right = q.right
        if p is None:
            self._root = q.left
        elif p.left is q:
            p.left = q.left
        else:
            p.right = q.left

    def __iter__(self):
        """
        實(shí)現(xiàn)二叉樹(shù)的中序遍歷算法,
        展示我們創(chuàng)建的二叉查找樹(shù).
        直接使用python內(nèi)置的列表作為一個(gè)棧。
        :return: data
        """
        stack = []
        node = self._root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.data
            node = node.right


if __name__ == '__main__':
    lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
    bs_tree = BinarySortTree()
    for i in range(len(lis)):
        bs_tree.insert(lis[i])
    # bs_tree.insert(100)
    bs_tree.delete(58)
    for i in bs_tree:
        print(i, end=" ")
    # print("\n", bs_tree.search(4))

class Node(object):
    def __init__(self,key):
        self.key1=key
        self.key2=None
        self.left=None
        self.middle=None
        self.right=None
    def isLeaf(self):
        return self.left is None and self.middle is None and self.right is None
    def isFull(self):
        return self.key2 is not None
    def hasKey(self,key):
        if (self.key1==key) or (self.key2 is not None and self.key2==key):
            return True
        else:
            return False
    def getChild(self,key):
        if key<self.key1:
            return self.left
        elif self.key2 is None:
            return self.middle
        elif key<self.key2:
            return self.middle
        else:
            return self.right
class 2_3_Tree(object):
    def __init__(self):
        self.root=None
    def get(self,key):
        if self.root is None:
            return None
        else:
            return self._get(self.root,key)
    def _get(self,node,key):
        if node is None:
            return None
        elif node.hasKey(key):
            return node
        else:
            child=node.getChild(key)
            return self._get(child,key)
    def put(self,key):
        if self.root is None:
            self.root=Node(key)
        else:
            pKey,pRef=self._put(self.root,key)
            if pKey is not None:
                newnode=Node(pKey)
                newnode.left=self.root
                newnode.middle=pRef
                self.root=newnode
    def _put(self,node,key):
        if node.hasKey(key):
            return None,None
        elif node.isLeaf():
            return self._addtoNode(node,key,None)
        else:
            child=node.getChild(key)
            pKey,pRef=self._put(child,key)
            if pKey is None:
                return None,None
            else:
                return self._addtoNode(node,pKey,pRef)
             
         
    def _addtoNode(self,node,key,pRef):
        if node.isFull():
            return self._splitNode(node,key,pRef)
        else:
            if key<node.key1:
                node.key2=node.key1
                node.key1=key
                if pRef is not None:
                    node.right=node.middle
                    node.middle=pRef
            else:
                node.key2=key
                if pRef is not None:
                    node.right=Pref
            return None,None
    def _splitNode(self,node,key,pRef):
        newnode=Node(None)
        if key<node.key1:
            pKey=node.key1
            node.key1=key
            newnode.key1=node.key2
            if pRef is not None:
                newnode.left=node.middle
                newnode.middle=node.right
                node.middle=pRef
        elif key<node.key2:
            pKey=key
            newnode.key1=node.key2
            if pRef is not None:
                newnode.left=Pref
                newnode.middle=node.right
        else:
            pKey=node.key2
            newnode.key1=key
            if pRef is not None:
                newnode.left=node.right
                newnode.middle=pRef
        node.key2=None
        return pKey,newnode

#紅黑樹(shù)
from random import randint

RED = 'red'
BLACK = 'black'

class RBT:
    def __init__(self):
       # self.items = []
        self.root = None
        self.zlist = []

    def LEFT_ROTATE(self, x):
        # x是一個(gè)RBTnode
        y = x.right
        if y is None:
            # 右節(jié)點(diǎn)為空，不旋轉(zhuǎn)
            return
        else:
            beta = y.left
            x.right = beta
            if beta is not None:
                beta.parent = x

            p = x.parent
            y.parent = p
            if p is None:
                # x原來(lái)是root
                self.root = y
            elif x == p.left:
                p.left = y
            else:
                p.right = y
            y.left = x
            x.parent = y

    def RIGHT_ROTATE(self, y):
        # y是一個(gè)節(jié)點(diǎn)
        x = y.left
        if x is None:
            # 右節(jié)點(diǎn)為空，不旋轉(zhuǎn)
            return
        else:
            beta = x.right
            y.left = beta
            if beta is not None:
                beta.parent = y

            p = y.parent
            x.parent = p
            if p is None:
                # y原來(lái)是root
                self.root = x
            elif y == p.left:
                p.left = x
            else:
                p.right = x
            x.right = y
            y.parent = x

    def INSERT(self, val):

        z = RBTnode(val)
        y = None
        x = self.root
        while x is not None:
            y = x
            if z.val < x.val:
                x = x.left
            else:
                x = x.right

        z.PAINT(RED)
        z.parent = y

        if y is None:
            # 插入z之前為空的RBT
            self.root = z
            self.INSERT_FIXUP(z)
            return

        if z.val < y.val:
            y.left = z
        else:
            y.right = z

        if y.color == RED:
            # z的父節(jié)點(diǎn)y為紅色，需要fixup。
            # 如果z的父節(jié)點(diǎn)y為黑色，則不用調(diào)整
            self.INSERT_FIXUP(z)

        else:
            return

    def INSERT_FIXUP(self, z):
        # case 1:z為root節(jié)點(diǎn)
        if z.parent is None:
            z.PAINT(BLACK)
            self.root = z
            return

        # case 2:z的父節(jié)點(diǎn)為黑色
        if z.parent.color == BLACK:
            # 包括了z處于第二層的情況
            # 這里感覺(jué)不必要啊。。似乎z.parent為黑色則不會(huì)進(jìn)入fixup階段
            return

        # 下面的幾種情況，都是z.parent.color == RED:
        # 節(jié)點(diǎn)y為z的uncle
        p = z.parent
        g = p.parent  # g為x的grandpa
        if g is None:
            return
            #   return 這里不能return的。。。
        if g.right == p:
            y = g.left
        else:
            y = g.right

        # case 3-0:z沒(méi)有叔叔。即：y為NIL節(jié)點(diǎn)
        # 注意，此時(shí)z的父節(jié)點(diǎn)一定是RED
        if y == None:
            if z == p.right and p == p.parent.left:
                # 3-0-0:z為右兒子,且p為左兒子，則把p左旋
                # 轉(zhuǎn)化為3-0-1或3-0-2的情況
                self.LEFT_ROTATE(p)
                p, z = z, p
                g = p.parent
            elif z == p.left and p == p.parent.right:
                self.RIGHT_ROTATE(p)
                p, z = z, p

            g.PAINT(RED)
            p.PAINT(BLACK)
            if p == g.left:
                # 3-0-1:p為g的左兒子
                self.RIGHT_ROTATE(g)
            else:
                # 3-0-2:p為g的右兒子
                self.LEFT_ROTATE(g)

            return

        # case 3-1:z有黑叔
        elif y.color == BLACK:
            if p.right == z and p.parent.left == p:
                # 3-1-0:z為右兒子,且p為左兒子,則左旋p
                # 轉(zhuǎn)化為3-1-1或3-1-2
                self.LEFT_ROTATE(p)
                p, z = z, p
            elif p.left == z and p.parent.right == p:
                self.RIGHT_ROTATE(p)
                p, z = z, p

            p = z.parent
            g = p.parent

            p.PAINT(BLACK)
            g.PAINT(RED)
            if p == g.left:
                # 3-1-1:p為g的左兒子，則右旋g
                self.RIGHT_ROTATE(g)
            else:
                # 3-1-2:p為g的右兒子，則左旋g
                self.LEFT_ROTATE(g)

            return


        # case 3-2:z有紅叔
        # 則涂黑父和叔，涂紅爺，g作為新的z，遞歸調(diào)用
        else:
            y.PAINT(BLACK)
            p.PAINT(BLACK)
            g.PAINT(RED)
            new_z = g
            self.INSERT_FIXUP(new_z)

    def DELETE(self, val):
        curNode = self.root
        while curNode is not None:
            if val < curNode.val:
                curNode = curNode.left
            elif val > curNode.val:
                curNode = curNode.right
            else:
                # 找到了值為val的元素,正式開(kāi)始刪除

                if curNode.left is None and curNode.right is None:
                    # case1:curNode為葉子節(jié)點(diǎn)：直接刪除即可
                    if curNode == self.root:
                        self.root = None
                    else:
                        p = curNode.parent
                        if curNode == p.left:
                            p.left = None
                        else:
                            p.right = None

                elif curNode.left is not None and curNode.right is not None:
                    sucNode = self.SUCCESOR(curNode)
                    curNode.val, sucNode.val  = sucNode.val, curNode.val
                    self.DELETE(sucNode.val)

                else:
                    p = curNode.parent
                    if curNode.left is None:
                        x = curNode.right
                    else:
                        x = curNode.left
                    if curNode == p.left:
                        p.left = x
                    else:
                        p.right = x
                    x.parent = p
                    if curNode.color == BLACK:
                        self.DELETE_FIXUP(x)

                curNode = None
        return False

    def DELETE_FIXUP(self, x):
        p = x.parent
        # w:x的兄弟結(jié)點(diǎn)
        if x == p.left:
            w = x.right
        else:
            w = x.left

        # case1:x的兄弟w是紅色的
        if w.color == RED:
            p.PAINT(RED)
            w.PAINT(BLACK)
            if w == p.right:
                self.LEFT_ROTATE(p)
            else:
                self.RIGHT_ROTATE(p)

        if w.color == BLACK:
            # case2:x的兄弟w是黑色的，而且w的兩個(gè)孩子都是黑色的
            if w.left.color == BLACK and w.right.color == BLACK:
                w.PAINT(RED)
                if p.color == BLACK:
                    return
                else:
                    p.color = BLACK
                    self.DELETE_FIXUP(p)

            # case3:x的兄弟w是黑色的，而且w的左兒子是紅色的，右兒子是黑色的
            if w.left.color == RED and w.color == BLACK:
                w.left.PAINT(BLACK)
                w.PAINT(RED)
                self.RIGHT_ROTATE(w)

            # case4:x的兄弟w是黑色的，而且w的右兒子是紅
            if w.right.color == RED:
                p.PAINT(BLACK)
                w.PAINT(RED)
                if w == p.right:
                    self.LEFT_ROTATE(p)
                else:
                    self.RIGHT_ROTATE(p)

    def SHOW(self):
        self.DISPLAY1(self.root)
        return self.zlist

    def DISPLAY1(self, node):
        if node is None:
            return
        self.DISPLAY1(node.left)
        self.zlist.append(node.val)
        self.DISPLAY1(node.right)

    def DISPLAY2(self, node):
        if node is None:
            return
        self.DISPLAY2(node.left)
        print(node.val)
        self.DISPLAY2(node.right)

    def DISPLAY3(self, node):
        if node is None:
            return
        self.DISPLAY3(node.left)
        self.DISPLAY3(node.right)
        print(node.val)

class RBTnode:
    '''紅黑樹(shù)的節(jié)點(diǎn)類(lèi)型'''
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

    def PAINT(self, color):
        self.color = color

def zuoxuan(b, c):
    a = b.parent
    a.left = c
    c.parent = a
    b.parent = c
    c.left = b

if __name__ == '__main__':
    rbt=RBT()
    b = []

    for i in range(100):
        m = randint(0, 500)
        rbt.INSERT(m)
        b.append(m)

    a = rbt.SHOW()
    b.sort()
    equal = True
    for i in range(100):
        if a[i] != b[i]:
            equal = False
            break

    if not equal:
        print('wrong')
    else:
        print('OK!')

# -*- coding: UTF-8 -*-
# B樹(shù)查找

class BTree:  #B樹(shù)
    def __init__(self,value):
        self.left=None
        self.data=value
        self.right=None

    def insertLeft(self,value):
        self.left=BTree(value)
        return self.left

    def insertRight(self,value):
        self.right=BTree(value)
        return self.right

    def show(self):
        print(self.data)


def inorder(node):  #中序遍歷：先左子樹(shù)，再根節(jié)點(diǎn)，再右子樹(shù)
    if node.data:
        if node.left:
            inorder(node.left)
        node.show()
        if node.right:
            inorder(node.right)


def rinorder(node):  #倒中序遍歷
    if node.data:
        if node.right:
            rinorder(node.right)
        node.show()
        if node.left:
            rinorder(node.left)

def insert(node,value):
    if value > node.data:
        if node.right:
            insert(node.right,value)
        else:
            node.insertRight(value)
    else:
        if node.left:
            insert(node.left,value)
        else:
            node.insertLeft(value)


if __name__ == "__main__":

    l=[88,11,2,33,22,4,55,33,221,34]
    Root=BTree(l[0])
    node=Root
    for i in range(1,len(l)):
        insert(Root,l[i])

    print("中序遍歷（從小到大排序 ）")
    inorder(Root)
    print("倒中序遍歷（從大到小排序）")
    rinorder(Root)

# 忽略了對(duì)數(shù)據(jù)類(lèi)型，元素溢出等問(wèn)題的判斷。
 
class HashTable:
  def __init__(self, size):
    self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結(jié)構(gòu)作為哈希表元素保存方法
    self.count = size # 最大表長(zhǎng)
 
  def hash(self, key):
    return key % self.count # 散列函數(shù)采用除留余數(shù)法
 
  def insert_hash(self, key):
    """插入關(guān)鍵字到哈希表內(nèi)"""
    address = self.hash(key) # 求散列地址
    while self.elem[address]: # 當(dāng)前位置已經(jīng)有數(shù)據(jù)了，發(fā)生沖突。
      address = (address+1) % self.count # 線性探測(cè)下一地址是否可用
    self.elem[address] = key # 沒(méi)有沖突則直接保存。
 
  def search_hash(self, key):
    """查找關(guān)鍵字，返回布爾值"""
    star = address = self.hash(key)
    while self.elem[address] != key:
      address = (address + 1) % self.count
      if not self.elem[address] or address == star: # 說(shuō)明沒(méi)找到或者循環(huán)到了開(kāi)始的位置
        return False
    return True
 
 
if __name__ == '__main__':
  list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
  hash_table = HashTable(12)
  for i in list_a:
    hash_table.insert_hash(i)
 
  for i in hash_table.elem:
    if i:
      print((i, hash_table.elem.index(i)), end=" ")
  print("\n")
 
  print(hash_table.search_hash(15))
  print(hash_table.search_hash(33))