バイナリプローブツリー実装

2071 ワード
テキストリンク

バイナリナビゲーション

  • ナビゲーション時間複雑度O(logn)
  • 入力および削除不可

    接続リスト

  • ナビゲーション時間複雑度O(n)
  • データの入力と削除の時間的複雑度はO(1)
    • である.

    バイナリプローブツリー

  • 各ノードの左側のノードには、そのノードよりも小さい値が存在する.
  • 各ノードの右側ノードには、ノードよりも高い値が存在する.
  • ノードの重複は許可されていません.
  • 中位数(左サブツリー->ノード->右サブツリー)

    • class Node {
    let value: Int
var leftChild: Node?
var rightChild: Node?

init(value: Int, leftChild: Node?, rightChild: Node?) {

    self.value = value
    self.leftChild = leftChild
    self.rightChild = rightChild
 }
    }
    //Left Branch
    let oneNode = Node(value: 1, leftChild: nil, rightChild: nil)
let fiveNode = Node(value: 5, leftChild: oneNode, rightChild: nil)
    //Right Branch
    let elevenNode = Node(value: 11, leftChild: nil, rightChild: nil)
let twentyNode = Node(value: 20, leftChild: nil, rightChild: nil)
let fourteenNode = Node(value: 14, leftChild: elevenNode, rightChild: twentyNode)
    //TOP
    let tenRootNode = Node(value: 10, leftChild: fiveNode, rightChild: fourteenNode)
    func search(node: Node?, searchValue: Int) -> Bool {
       if node == nil {

	return false
   }

   if node?.value == searchValue {

	return true
   }

   // improve
   else if searchValue < node?.value ?? 0 {

	return search(node: node?.leftChild, searchValue: searchValue)
   }
   else {

	return search(node: node?.rightChild, searchValue: searchValue)
   }
   
   // basic
   else {
   
   	return search(node: node?.leftChild, searchValue: searchValue) ||
               search(node: node?.rightChild, searchValue: searchValue)
   }
    }
    search(node: tenRootNode, searchValue: 20)
    //improve version: 2 times
    //basic version: 5 times
    compared to arr
    let arr = [1, 5, 10, 11, 14 ,20]
    let index = arr.firstIndex(where: { $0 == 20 })//7 times
    Subarray Division 1
    Oracleへの接続