7.4 이진 탐색 트리¶

아래 그림(7-16)의 이진 탐색 트리(binary search tree)는 다음 조건을 만족한다.

루트에 대해 왼쪽 서브트리의 모든 노드 값 \(<\) 루트 값 \(<\) 오른쪽 서브트리의 모든 노드 값이다.
임의의 노드의 왼쪽과 오른쪽 서브트리도 이진 탐색 트리로, 조건 1.을 만족한다.

이진 탐색 트리

그림 7-16 이진 탐색 트리

7.4.1 이진 탐색 트리의 연산¶

이진 탐색 트리를 BinarySearchTree 클래스로 묶고, 루트 노드를 가리키는 멤버 변수 root를 정의한다.

1. 노드 탐색¶

목표 노드의 값 num이 주어지면 이진 탐색 트리의 성질로 찾을 수 있다. 아래 그림(7-17)과 같이 노드 cur를 두고 루트 root에서 출발하여 cur.val과 num의 대소 관계를 반복해서 비교한다.

cur.val < num이면 목표 노드는 cur의 오른쪽 서브트리에 있으므로 cur = cur.right를 수행한다.
cur.val > num이면 목표 노드는 cur의 왼쪽 서브트리에 있으므로 cur = cur.left를 수행한다.
cur.val = num이면 목표 노드를 찾았으므로 반복문을 빠져나와 해당 노드를 반환한다.

<1><2><3><4>

이진 탐색 트리의 노드 탐색 예시

이진 탐색 트리 탐색 2단계

이진 탐색 트리 탐색 3단계

이진 탐색 트리 탐색 4단계

그림 7-17 이진 탐색 트리의 노드 탐색 예시

이진 탐색 트리의 탐색 원리는 이진 탐색 알고리즘과 같으며, 매번 경우의 절반을 제외한다. 반복 횟수는 최대 트리 높이이므로 트리가 균형을 이루면 \(O(\log n)\) 시간이 걸린다. 예시 코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_tree.py

def search(self, num: int) -> TreeNode | None:
    """노드 탐색"""
    cur = self._root
    # 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while cur is not None:
        # 목표 노드는 cur의 오른쪽 서브트리에 있다
        if cur.val < num:
            cur = cur.right
        # 목표 노드는 cur의 왼쪽 서브트리에 있다
        elif cur.val > num:
            cur = cur.left
        # 목표 노드를 찾았으므로 반복문을 종료한다
        else:
            break
    return cur

binary_search_tree.cpp

/* 노드 탐색 */
TreeNode *search(int num) {
    TreeNode *cur = root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != nullptr) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if (cur->val < num)
            cur = cur->right;
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur->val > num)
            cur = cur->left;
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else
            break;
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.java

/* 노드 탐색 */
TreeNode search(int num) {
    TreeNode cur = root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num)
            cur = cur.right;
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur.val > num)
            cur = cur.left;
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else
            break;
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.cs

/* 노드 탐색 */
TreeNode? Search(int num) {
    TreeNode? cur = root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur =
            cur.right;
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur.val > num)
            cur = cur.left;
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else
            break;
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.go

/* 노드 탐색 */
func (bst *binarySearchTree) search(num int) *TreeNode {
    node := bst.root
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    for node != nil {
        if node.Val.(int) < num {
            // 목표 노드는 cur의 오른쪽 서브트리에 있다
            node = node.Right
        } else if node.Val.(int) > num {
            // 목표 노드는 cur의 왼쪽 서브트리에 있다
            node = node.Left
        } else {
            // 목표 노드를 찾았으므로 반복문을 종료한다
            break
        }
    }
    // 목표 노드를 반환한다
    return node
}

binary_search_tree.swift

/* 노드 탐색 */
func search(num: Int) -> TreeNode? {
    var cur = root
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while cur != nil {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if cur!.val < num {
            cur = cur?.right
        }
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if cur!.val > num {
            cur = cur?.left
        }
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else {
            break
        }
    }
    // 목표 노드를 반환한다
    return cur
}

binary_search_tree.js

/* 노드 탐색 */
search(num) {
    let cur = this.root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur.val > num) cur = cur.left;
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else break;
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.ts

/* 노드 탐색 */
search(num: number): TreeNode | null {
    let cur = this.root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur.val > num) cur = cur.left;
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else break;
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.dart

/* 노드 탐색 */
TreeNode? search(int _num) {
  TreeNode? cur = _root;
  // 반복하여 탐색하다 리프 노드를 지나면 종료한다
  while (cur != null) {
    // 목표 노드는 cur의 오른쪽 서브트리에 있다
    if (cur.val < _num)
      cur = cur.right;
    // 목표 노드는 cur의 왼쪽 서브트리에 있다
    else if (cur.val > _num)
      cur = cur.left;
    // 목표 노드를 찾았으므로 반복문을 종료한다
    else
      break;
  }
  // 목표 노드를 반환한다
  return cur;
}

binary_search_tree.rs

/* 노드 탐색 */
pub fn search(&self, num: i32) -> OptionTreeNodeRc {
    let mut cur = self.root.clone();
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while let Some(node) = cur.clone() {
        match num.cmp(&node.borrow().val) {
            // 목표 노드는 cur의 오른쪽 서브트리에 있다
            Ordering::Greater => cur = node.borrow().right.clone(),
            // 목표 노드는 cur의 왼쪽 서브트리에 있다
            Ordering::Less => cur = node.borrow().left.clone(),
            // 목표 노드를 찾았으므로 반복문을 종료한다
            Ordering::Equal => break,
        }
    }

    // 목표 노드를 반환한다
    cur
}

binary_search_tree.c

/* 노드 탐색 */
TreeNode *search(BinarySearchTree *bst, int num) {
    TreeNode *cur = bst->root;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != NULL) {
        if (cur->val < num) {
            // 목표 노드는 cur의 오른쪽 서브트리에 있다
            cur = cur->right;
        } else if (cur->val > num) {
            // 목표 노드는 cur의 왼쪽 서브트리에 있다
            cur = cur->left;
        } else {
            // 목표 노드를 찾았으므로 반복문을 종료한다
            break;
        }
    }
    // 목표 노드를 반환한다
    return cur;
}

binary_search_tree.kt

/* 노드 탐색 */
fun search(num: Int): TreeNode? {
    var cur = root
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 목표 노드는 cur의 오른쪽 서브트리에 있다
        cur = if (cur._val < num)
            cur.right
        // 목표 노드는 cur의 왼쪽 서브트리에 있다
        else if (cur._val > num)
            cur.left
        // 목표 노드를 찾았으므로 반복문을 종료한다
        else
            break
    }
    // 목표 노드를 반환한다
    return cur
}

binary_search_tree.rb

### 노드 탐색 ###
def search(num)
  cur = @root

  # 반복하여 탐색하다 리프 노드를 지나면 종료한다
  while !cur.nil?
    # 목표 노드는 cur의 오른쪽 서브트리에 있다
    if cur.val < num
      cur = cur.right
    # 목표 노드는 cur의 왼쪽 서브트리에 있다
    elsif cur.val > num
      cur = cur.left
    # 목표 노드를 찾았으므로 반복문을 종료한다
    else
      break
    end
  end

  cur
end

코드 시각화

전체 화면 >

2. 노드 삽입¶

삽입할 원소 num이 주어졌을 때 '왼쪽 서브트리 < 루트 < 오른쪽 서브트리'라는 성질을 유지하려면 아래 그림(7-18)과 같이 삽입한다.

삽입 위치 찾기: 탐색과 비슷하게 루트에서 출발하여 현재 노드 값과 num의 대소 관계에 따라 아래로 탐색한다. 리프를 지나 None에 도달하면 반복문을 종료한다.
그 위치에 노드 삽입: 값이 num인 노드를 초기화하여 None 자리에 놓는다.

이진 탐색 트리에 노드 삽입

그림 7-18 이진 탐색 트리에 노드 삽입

구현 시 다음 두 가지에 주의하자.

중복 노드가 있으면 정의에 어긋나므로 이진 탐색 트리는 중복을 허용하지 않는다. 삽입할 노드가 이미 있으면 삽입하지 않고 바로 반환한다.
삽입을 위해 노드 pre에 직전 반복의 노드를 저장해야 한다. 그러면 None에 도달했을 때 그 부모를 얻어 삽입을 완료할 수 있다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_tree.py

def insert(self, num: int):
    """노드 삽입"""
    # 트리가 비어 있으면 루트 노드를 초기화한다
    if self._root is None:
        self._root = TreeNode(num)
        return
    # 반복하여 탐색하다 리프 노드를 지나면 종료한다
    cur, pre = self._root, None
    while cur is not None:
        # 중복 노드를 찾으면 바로 반환한다
        if cur.val == num:
            return
        pre = cur
        # 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if cur.val < num:
            cur = cur.right
        # 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else:
            cur = cur.left
    # 노드 삽입
    node = TreeNode(num)
    if pre.val < num:
        pre.right = node
    else:
        pre.left = node

binary_search_tree.cpp

/* 노드 삽입 */
void insert(int num) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (root == nullptr) {
        root = new TreeNode(num);
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != nullptr) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur->val == num)
            return;
        pre = cur;
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if (cur->val < num)
            cur = cur->right;
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur->left;
    }
    // 노드 삽입
    TreeNode *node = new TreeNode(num);
    if (pre->val < num)
        pre->right = node;
    else
        pre->left = node;
}

binary_search_tree.java

/* 노드 삽입 */
void insert(int num) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode cur = root, pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur.val == num)
            return;
        pre = cur;
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num)
            cur = cur.right;
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur.left;
    }
    // 노드 삽입
    TreeNode node = new TreeNode(num);
    if (pre.val < num)
        pre.right = node;
    else
        pre.left = node;
}

binary_search_tree.cs

/* 노드 삽입 */
void Insert(int num) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (root == null) {
        root = new TreeNode(num);
        return;
    }
    TreeNode? cur = root, pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur.val == num)
            return;
        pre = cur;
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num)
            cur = cur.right;
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur.left;
    }

    // 노드 삽입
    TreeNode node = new(num);
    if (pre != null) {
        if (pre.val < num)
            pre.right = node;
        else
            pre.left = node;
    }
}

binary_search_tree.go

/* 노드 삽입 */
func (bst *binarySearchTree) insert(num int) {
    cur := bst.root
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if cur == nil {
        bst.root = NewTreeNode(num)
        return
    }
    // 삽입할 노드의 부모가 될 노드 위치
    var pre *TreeNode = nil
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    for cur != nil {
        if cur.Val == num {
            return
        }
        pre = cur
        if cur.Val.(int) < num {
            cur = cur.Right
        } else {
            cur = cur.Left
        }
    }
    // 노드 삽입
    node := NewTreeNode(num)
    if pre.Val.(int) < num {
        pre.Right = node
    } else {
        pre.Left = node
    }
}

binary_search_tree.swift

/* 노드 삽입 */
func insert(num: Int) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if root == nil {
        root = TreeNode(x: num)
        return
    }
    var cur = root
    var pre: TreeNode?
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while cur != nil {
        // 중복 노드를 찾으면 바로 반환한다
        if cur!.val == num {
            return
        }
        pre = cur
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if cur!.val < num {
            cur = cur?.right
        }
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else {
            cur = cur?.left
        }
    }
    // 노드 삽입
    let node = TreeNode(x: num)
    if pre!.val < num {
        pre?.right = node
    } else {
        pre?.left = node
    }
}

binary_search_tree.js

/* 노드 삽입 */
insert(num) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (this.root === null) {
        this.root = new TreeNode(num);
        return;
    }
    let cur = this.root,
        pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur.val === num) return;
        pre = cur;
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else cur = cur.left;
    }
    // 노드 삽입
    const node = new TreeNode(num);
    if (pre.val < num) pre.right = node;
    else pre.left = node;
}

binary_search_tree.ts

/* 노드 삽입 */
insert(num: number): void {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (this.root === null) {
        this.root = new TreeNode(num);
        return;
    }
    let cur: TreeNode | null = this.root,
        pre: TreeNode | null = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur.val === num) return;
        pre = cur;
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else cur = cur.left;
    }
    // 노드 삽입
    const node = new TreeNode(num);
    if (pre!.val < num) pre!.right = node;
    else pre!.left = node;
}

binary_search_tree.dart

/* 노드 삽입 */
void insert(int _num) {
  // 트리가 비어 있으면 루트 노드를 초기화한다
  if (_root == null) {
    _root = TreeNode(_num);
    return;
  }
  TreeNode? cur = _root;
  TreeNode? pre = null;
  // 반복하여 탐색하다 리프 노드를 지나면 종료한다
  while (cur != null) {
    // 중복 노드를 찾으면 바로 반환한다
    if (cur.val == _num) return;
    pre = cur;
    // 삽입 위치는 cur의 오른쪽 서브트리에 있다
    if (cur.val < _num)
      cur = cur.right;
    // 삽입 위치는 cur의 왼쪽 서브트리에 있다
    else
      cur = cur.left;
  }
  // 노드 삽입
  TreeNode? node = TreeNode(_num);
  if (pre!.val < _num)
    pre.right = node;
  else
    pre.left = node;
}

binary_search_tree.rs

/* 노드 삽입 */
pub fn insert(&mut self, num: i32) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if self.root.is_none() {
        self.root = Some(TreeNode::new(num));
        return;
    }
    let mut cur = self.root.clone();
    let mut pre = None;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while let Some(node) = cur.clone() {
        match num.cmp(&node.borrow().val) {
            // 중복 노드를 찾으면 바로 반환한다
            Ordering::Equal => return,
            // 삽입 위치는 cur의 오른쪽 서브트리에 있다
            Ordering::Greater => {
                pre = cur.clone();
                cur = node.borrow().right.clone();
            }
            // 삽입 위치는 cur의 왼쪽 서브트리에 있다
            Ordering::Less => {
                pre = cur.clone();
                cur = node.borrow().left.clone();
            }
        }
    }
    // 노드 삽입
    let pre = pre.unwrap();
    let node = Some(TreeNode::new(num));
    if num > pre.borrow().val {
        pre.borrow_mut().right = node;
    } else {
        pre.borrow_mut().left = node;
    }
}

binary_search_tree.c

/* 노드 삽입 */
void insert(BinarySearchTree *bst, int num) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (bst->root == NULL) {
        bst->root = newTreeNode(num);
        return;
    }
    TreeNode *cur = bst->root, *pre = NULL;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != NULL) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur->val == num) {
            return;
        }
        pre = cur;
        if (cur->val < num) {
            // 삽입 위치는 cur의 오른쪽 서브트리에 있다
            cur = cur->right;
        } else {
            // 삽입 위치는 cur의 왼쪽 서브트리에 있다
            cur = cur->left;
        }
    }
    // 노드 삽입
    TreeNode *node = newTreeNode(num);
    if (pre->val < num) {
        pre->right = node;
    } else {
        pre->left = node;
    }
}

binary_search_tree.kt

/* 노드 삽입 */
fun insert(num: Int) {
    // 트리가 비어 있으면 루트 노드를 초기화한다
    if (root == null) {
        root = TreeNode(num)
        return
    }
    var cur = root
    var pre: TreeNode? = null
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 중복 노드를 찾으면 바로 반환한다
        if (cur._val == num)
            return
        pre = cur
        // 삽입 위치는 cur의 오른쪽 서브트리에 있다
        cur = if (cur._val < num)
            cur.right
        // 삽입 위치는 cur의 왼쪽 서브트리에 있다
        else
            cur.left
    }
    // 노드 삽입
    val node = TreeNode(num)
    if (pre?._val!! < num)
        pre.right = node
    else
        pre.left = node
}

binary_search_tree.rb

### 노드 삽입 ###
def insert(num)
  # 트리가 비어 있으면 루트 노드를 초기화한다
  if @root.nil?
    @root = TreeNode.new(num)
    return
  end

  # 반복하여 탐색하다 리프 노드를 지나면 종료한다
  cur, pre = @root, nil
  while !cur.nil?
    # 중복 노드를 찾으면 바로 반환한다
    return if cur.val == num

    pre = cur
    # 삽입 위치는 cur의 오른쪽 서브트리에 있다
    if cur.val < num
      cur = cur.right
    # 삽입 위치는 cur의 왼쪽 서브트리에 있다
    else
      cur = cur.left
    end
  end

  # 노드 삽입
  node = TreeNode.new(num)
  if pre.val < num
    pre.right = node
  else
    pre.left = node
  end
end

코드 시각화

전체 화면 >

노드 탐색과 마찬가지로 삽입에는 \(O(\log n)\) 시간이 걸린다.

3. 노드 삭제¶

먼저 트리에서 목표 노드를 찾은 뒤 삭제한다. 삽입과 마찬가지로 삭제 후에도 '왼쪽 서브트리 < 루트 < 오른쪽 서브트리'라는 성질을 유지해야 한다. 따라서 목표 노드의 자식 수가 0, 1, 2인 세 경우로 나누어 삭제한다.

아래 그림(7-19)과 같이 삭제할 노드의 차수가 \(0\)이면 리프 노드이므로 바로 삭제할 수 있다.

이진 탐색 트리의 노드 삭제: 차수 0

그림 7-19 이진 탐색 트리의 노드 삭제: 차수 0

아래 그림(7-20)과 같이 차수가 \(1\)이면 삭제할 노드를 그 자식으로 바꾸면 된다.

이진 탐색 트리의 노드 삭제: 차수 1

그림 7-20 이진 탐색 트리의 노드 삭제: 차수 1

차수가 \(2\)이면 바로 삭제할 수 없어 다른 노드로 대체해야 한다. '왼쪽 서브트리 \(<\) 루트 \(<\) 오른쪽 서브트리' 성질을 유지하려면 오른쪽 서브트리의 최소 노드 또는 왼쪽 서브트리의 최대 노드로 대체할 수 있다.

오른쪽 서브트리의 최소 노드(중위 순회에서 다음 노드)를 선택하면 삭제 과정은 아래 그림(7-21)과 같다.

삭제할 노드의 '중위 순회 순서'상 다음 노드를 찾아 tmp라고 한다.
삭제할 노드의 값을 tmp의 값으로 덮어쓰고, 트리에서 노드 tmp를 재귀적으로 삭제한다.

<1><2><3><4>

이진 탐색 트리의 노드 삭제: 차수 2

차수 2인 노드 삭제 2단계

차수 2인 노드 삭제 3단계

차수 2인 노드 삭제 4단계

그림 7-21 이진 탐색 트리의 노드 삭제: 차수 2

노드 삭제에도 \(O(\log n)\) 시간이 걸린다. 삭제할 노드를 찾는 데 \(O(\log n)\), 중위 순회의 후속 노드를 구하는 데 \(O(\log n)\) 시간이 든다. 예시 코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_tree.py

def remove(self, num: int):
    """노드 삭제"""
    # 트리가 비어 있으면 바로 반환하여 종료한다
    if self._root is None:
        return
    # 반복하여 탐색하다 리프 노드를 지나면 종료한다
    cur, pre = self._root, None
    while cur is not None:
        # 삭제할 노드를 찾았으므로 반복문을 종료한다
        if cur.val == num:
            break
        pre = cur
        # 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if cur.val < num:
            cur = cur.right
        # 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else:
            cur = cur.left
    # 삭제할 노드가 없으면 바로 반환한다
    if cur is None:
        return

    # 자식 노드 수 = 0 또는 1
    if cur.left is None or cur.right is None:
        # 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        child = cur.left or cur.right
        # 노드 cur를 삭제한다
        if cur != self._root:
            if pre.left == cur:
                pre.left = child
            else:
                pre.right = child
        else:
            # 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            self._root = child
    # 자식 노드 수 = 2
    else:
        # 중위 순회에서 cur의 다음 노드를 구한다
        tmp: TreeNode = cur.right
        while tmp.left is not None:
            tmp = tmp.left
        # 노드 tmp를 재귀적으로 삭제한다
        self.remove(tmp.val)
        # tmp로 cur를 덮어쓴다
        cur.val = tmp.val

binary_search_tree.cpp

/* 노드 삭제 */
void remove(int num) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (root == nullptr)
        return;
    TreeNode *cur = root, *pre = nullptr;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != nullptr) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur->val == num)
            break;
        pre = cur;
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if (cur->val < num)
            cur = cur->right;
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur->left;
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur == nullptr)
        return;
    // 자식 노드 수 = 0 또는 1
    if (cur->left == nullptr || cur->right == nullptr) {
        // 자식 노드 수가 0 / 1이면 child = nullptr / 해당 자식 노드다
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 노드 cur를 삭제한다
        if (cur != root) {
            if (pre->left == cur)
                pre->left = child;
            else
                pre->right = child;
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            root = child;
        }
        // 메모리 해제
        delete cur;
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        TreeNode *tmp = cur->right;
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 노드 tmp를 재귀적으로 삭제한다
        remove(tmp->val);
        // tmp로 cur를 덮어쓴다
        cur->val = tmpVal;
    }
}

binary_search_tree.java

/* 노드 삭제 */
void remove(int num) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (root == null)
        return;
    TreeNode cur = root, pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur.val == num)
            break;
        pre = cur;
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num)
            cur = cur.right;
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur.left;
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur == null)
        return;
    // 자식 노드 수 = 0 또는 1
    if (cur.left == null || cur.right == null) {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        TreeNode child = cur.left != null ? cur.left : cur.right;
        // 노드 cur를 삭제한다
        if (cur != root) {
            if (pre.left == cur)
                pre.left = child;
            else
                pre.right = child;
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            root = child;
        }
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        TreeNode tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        // 노드 tmp를 재귀적으로 삭제한다
        remove(tmp.val);
        // tmp로 cur를 덮어쓴다
        cur.val = tmp.val;
    }
}

binary_search_tree.cs

/* 노드 삭제 */
void Remove(int num) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (root == null)
        return;
    TreeNode? cur = root, pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur.val == num)
            break;
        pre = cur;
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num)
            cur = cur.right;
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else
            cur = cur.left;
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur == null)
        return;
    // 자식 노드 수 = 0 또는 1
    if (cur.left == null || cur.right == null) {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        TreeNode? child = cur.left ?? cur.right;
        // 노드 cur를 삭제한다
        if (cur != root) {
            if (pre!.left == cur)
                pre.left = child;
            else
                pre.right = child;
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            root = child;
        }
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        TreeNode? tmp = cur.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        // 노드 tmp를 재귀적으로 삭제한다
        Remove(tmp.val!.Value);
        // tmp로 cur를 덮어쓴다
        cur.val = tmp.val;
    }
}

binary_search_tree.go

/* 노드 삭제 */
func (bst *binarySearchTree) remove(num int) {
    cur := bst.root
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if cur == nil {
        return
    }
    // 삭제할 노드의 부모 노드 위치
    var pre *TreeNode = nil
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    for cur != nil {
        if cur.Val == num {
            break
        }
        pre = cur
        if cur.Val.(int) < num {
            // 삭제할 노드는 오른쪽 서브트리에 있다
            cur = cur.Right
        } else {
            // 삭제할 노드는 왼쪽 서브트리에 있다
            cur = cur.Left
        }
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if cur == nil {
        return
    }
    // 자식 노드 수가 0 또는 1
    if cur.Left == nil || cur.Right == nil {
        var child *TreeNode = nil
        // 삭제할 노드의 자식 노드를 구한다
        if cur.Left != nil {
            child = cur.Left
        } else {
            child = cur.Right
        }
        // 노드 cur를 삭제한다
        if cur != bst.root {
            if pre.Left == cur {
                pre.Left = child
            } else {
                pre.Right = child
            }
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            bst.root = child
        }
        // 자식 노드 수가 2
    } else {
        // 중위 순회에서 삭제할 노드 cur의 다음 노드를 구한다
        tmp := cur.Right
        for tmp.Left != nil {
            tmp = tmp.Left
        }
        // 노드 tmp를 재귀적으로 삭제한다
        bst.remove(tmp.Val.(int))
        // tmp로 cur를 덮어쓴다
        cur.Val = tmp.Val
    }
}

binary_search_tree.swift

/* 노드 삭제 */
func remove(num: Int) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if root == nil {
        return
    }
    var cur = root
    var pre: TreeNode?
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while cur != nil {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if cur!.val == num {
            break
        }
        pre = cur
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if cur!.val < num {
            cur = cur?.right
        }
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else {
            cur = cur?.left
        }
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if cur == nil {
        return
    }
    // 자식 노드 수 = 0 또는 1
    if cur?.left == nil || cur?.right == nil {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        let child = cur?.left ?? cur?.right
        // 노드 cur를 삭제한다
        if cur !== root {
            if pre?.left === cur {
                pre?.left = child
            } else {
                pre?.right = child
            }
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            root = child
        }
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        var tmp = cur?.right
        while tmp?.left != nil {
            tmp = tmp?.left
        }
        // 노드 tmp를 재귀적으로 삭제한다
        remove(num: tmp!.val)
        // tmp로 cur를 덮어쓴다
        cur?.val = tmp!.val
    }
}

binary_search_tree.js

/* 노드 삭제 */
remove(num) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (this.root === null) return;
    let cur = this.root,
        pre = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur.val === num) break;
        pre = cur;
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else cur = cur.left;
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur === null) return;
    // 자식 노드 수 = 0 또는 1
    if (cur.left === null || cur.right === null) {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        const child = cur.left !== null ? cur.left : cur.right;
        // 노드 cur를 삭제한다
        if (cur !== this.root) {
            if (pre.left === cur) pre.left = child;
            else pre.right = child;
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            this.root = child;
        }
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        let tmp = cur.right;
        while (tmp.left !== null) {
            tmp = tmp.left;
        }
        // 노드 tmp를 재귀적으로 삭제한다
        this.remove(tmp.val);
        // tmp로 cur를 덮어쓴다
        cur.val = tmp.val;
    }
}

binary_search_tree.ts

/* 노드 삭제 */
remove(num: number): void {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (this.root === null) return;
    let cur: TreeNode | null = this.root,
        pre: TreeNode | null = null;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur !== null) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur.val === num) break;
        pre = cur;
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        if (cur.val < num) cur = cur.right;
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else cur = cur.left;
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur === null) return;
    // 자식 노드 수 = 0 또는 1
    if (cur.left === null || cur.right === null) {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        const child: TreeNode | null =
            cur.left !== null ? cur.left : cur.right;
        // 노드 cur를 삭제한다
        if (cur !== this.root) {
            if (pre!.left === cur) pre!.left = child;
            else pre!.right = child;
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            this.root = child;
        }
    }
    // 자식 노드 수 = 2
    else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        let tmp: TreeNode | null = cur.right;
        while (tmp!.left !== null) {
            tmp = tmp!.left;
        }
        // 노드 tmp를 재귀적으로 삭제한다
        this.remove(tmp!.val);
        // tmp로 cur를 덮어쓴다
        cur.val = tmp!.val;
    }
}

binary_search_tree.dart

/* 노드 삭제 */
void remove(int _num) {
  // 트리가 비어 있으면 바로 반환하여 종료한다
  if (_root == null) return;
  TreeNode? cur = _root;
  TreeNode? pre = null;
  // 반복하여 탐색하다 리프 노드를 지나면 종료한다
  while (cur != null) {
    // 삭제할 노드를 찾았으므로 반복문을 종료한다
    if (cur.val == _num) break;
    pre = cur;
    // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
    if (cur.val < _num)
      cur = cur.right;
    // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
    else
      cur = cur.left;
  }
  // 삭제할 노드가 없으면 바로 반환한다
  if (cur == null) return;
  // 자식 노드 수 = 0 또는 1
  if (cur.left == null || cur.right == null) {
    // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
    TreeNode? child = cur.left ?? cur.right;
    // 노드 cur를 삭제한다
    if (cur != _root) {
      if (pre!.left == cur)
        pre.left = child;
      else
        pre.right = child;
    } else {
      // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
      _root = child;
    }
  } else {
    // 자식 노드 수 = 2
    // 중위 순회에서 cur의 다음 노드를 구한다
    TreeNode? tmp = cur.right;
    while (tmp!.left != null) {
      tmp = tmp.left;
    }
    // 노드 tmp를 재귀적으로 삭제한다
    remove(tmp.val);
    // tmp로 cur를 덮어쓴다
    cur.val = tmp.val;
  }
}

binary_search_tree.rs

/* 노드 삭제 */
pub fn remove(&mut self, num: i32) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if self.root.is_none() {
        return;
    }
    let mut cur = self.root.clone();
    let mut pre = None;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while let Some(node) = cur.clone() {
        match num.cmp(&node.borrow().val) {
            // 삭제할 노드를 찾았으므로 반복문을 종료한다
            Ordering::Equal => break,
            // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
            Ordering::Greater => {
                pre = cur.clone();
                cur = node.borrow().right.clone();
            }
            // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
            Ordering::Less => {
                pre = cur.clone();
                cur = node.borrow().left.clone();
            }
        }
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if cur.is_none() {
        return;
    }
    let cur = cur.unwrap();
    let (left_child, right_child) = (cur.borrow().left.clone(), cur.borrow().right.clone());
    match (left_child.clone(), right_child.clone()) {
        // 자식 노드 수 = 0 또는 1
        (None, None) | (Some(_), None) | (None, Some(_)) => {
            // 자식 노드 수가 0 / 1이면 child = nullptr / 해당 자식 노드다
            let child = left_child.or(right_child);
            let pre = pre.unwrap();
            // 노드 cur를 삭제한다
            if !Rc::ptr_eq(&cur, self.root.as_ref().unwrap()) {
                let left = pre.borrow().left.clone();
                if left.is_some() && Rc::ptr_eq(left.as_ref().unwrap(), &cur) {
                    pre.borrow_mut().left = child;
                } else {
                    pre.borrow_mut().right = child;
                }
            } else {
                // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
                self.root = child;
            }
        }
        // 자식 노드 수 = 2
        (Some(_), Some(_)) => {
            // 중위 순회에서 cur의 다음 노드를 구한다
            let mut tmp = cur.borrow().right.clone();
            while let Some(node) = tmp.clone() {
                if node.borrow().left.is_some() {
                    tmp = node.borrow().left.clone();
                } else {
                    break;
                }
            }
            let tmp_val = tmp.unwrap().borrow().val;
            // 노드 tmp를 재귀적으로 삭제한다
            self.remove(tmp_val);
            // tmp로 cur를 덮어쓴다
            cur.borrow_mut().val = tmp_val;
        }
    }
}

binary_search_tree.c

/* 노드 삭제 */
// stdio.h를 포함했으므로 여기서는 remove라는 이름을 사용할 수 없다
void removeItem(BinarySearchTree *bst, int num) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (bst->root == NULL)
        return;
    TreeNode *cur = bst->root, *pre = NULL;
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != NULL) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur->val == num)
            break;
        pre = cur;
        if (cur->val < num) {
            // 삭제할 노드가 root의 오른쪽 서브트리에 있다
            cur = cur->right;
        } else {
            // 삭제할 노드가 root의 왼쪽 서브트리에 있다
            cur = cur->left;
        }
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur == NULL)
        return;
    // 삭제할 노드에 자식 노드가 있는지 확인한다
    if (cur->left == NULL || cur->right == NULL) {
        /* 자식 노드 수 = 0 또는 1 */
        // 자식 노드 수가 0 / 1이면 child = nullptr / 해당 자식 노드다
        TreeNode *child = cur->left != NULL ? cur->left : cur->right;
        // 노드 cur를 삭제한다
        if (pre->left == cur) {
            pre->left = child;
        } else {
            pre->right = child;
        }
        // 메모리 해제
        free(cur);
    } else {
        /* 자식 노드 수 = 2 */
        // 중위 순회에서 cur의 다음 노드를 구한다
        TreeNode *tmp = cur->right;
        while (tmp->left != NULL) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 노드 tmp를 재귀적으로 삭제한다
        removeItem(bst, tmp->val);
        // tmp로 cur를 덮어쓴다
        cur->val = tmpVal;
    }
}

binary_search_tree.kt

/* 노드 삭제 */
fun remove(num: Int) {
    // 트리가 비어 있으면 바로 반환하여 종료한다
    if (root == null)
        return
    var cur = root
    var pre: TreeNode? = null
    // 반복하여 탐색하다 리프 노드를 지나면 종료한다
    while (cur != null) {
        // 삭제할 노드를 찾았으므로 반복문을 종료한다
        if (cur._val == num)
            break
        pre = cur
        // 삭제할 노드는 cur의 오른쪽 서브트리에 있다
        cur = if (cur._val < num)
            cur.right
        // 삭제할 노드는 cur의 왼쪽 서브트리에 있다
        else
            cur.left
    }
    // 삭제할 노드가 없으면 바로 반환한다
    if (cur == null)
        return
    // 자식 노드 수 = 0 또는 1
    if (cur.left == null || cur.right == null) {
        // 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
        val child = if (cur.left != null)
            cur.left
        else
            cur.right
        // 노드 cur를 삭제한다
        if (cur != root) {
            if (pre!!.left == cur)
                pre.left = child
            else
                pre.right = child
        } else {
            // 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
            root = child
        }
        // 자식 노드 수 = 2
    } else {
        // 중위 순회에서 cur의 다음 노드를 구한다
        var tmp = cur.right
        while (tmp!!.left != null) {
            tmp = tmp.left
        }
        // 노드 tmp를 재귀적으로 삭제한다
        remove(tmp._val)
        // tmp로 cur를 덮어쓴다
        cur._val = tmp._val
    }
}

binary_search_tree.rb

### 노드 삭제 ###
def remove(num)
  # 트리가 비어 있으면 바로 반환하여 종료한다
  return if @root.nil?

  # 반복하여 탐색하다 리프 노드를 지나면 종료한다
  cur, pre = @root, nil
  while !cur.nil?
    # 삭제할 노드를 찾았으므로 반복문을 종료한다
    break if cur.val == num

    pre = cur
    # 삭제할 노드는 cur의 오른쪽 서브트리에 있다
    if cur.val < num
      cur = cur.right
    # 삭제할 노드는 cur의 왼쪽 서브트리에 있다
    else
      cur = cur.left
    end
  end
  # 삭제할 노드가 없으면 바로 반환한다
  return if cur.nil?

  # 자식 노드 수 = 0 또는 1
  if cur.left.nil? || cur.right.nil?
    # 자식 노드 수 = 0 / 1이면 child = null / 해당 자식 노드이다
    child = cur.left || cur.right
    # 노드 cur를 삭제한다
    if cur != @root
      if pre.left == cur
        pre.left = child
      else
        pre.right = child
      end
    else
      # 삭제할 노드가 루트 노드이면 루트 노드를 다시 지정한다
      @root = child
    end
  # 자식 노드 수 = 2
  else
    # 중위 순회에서 cur의 다음 노드를 구한다
    tmp = cur.right
    while !tmp.left.nil?
      tmp = tmp.left
    end
    # 노드 tmp를 재귀적으로 삭제한다
    remove(tmp.val)
    # tmp로 cur를 덮어쓴다
    cur.val = tmp.val
  end
end

코드 시각화

전체 화면 >

4. 중위 순회 결과의 정렬 성질¶

아래 그림(7-22)과 같이 이진 트리의 중위 순회는 '왼쪽 \(\rightarrow\) 루트 \(\rightarrow\) 오른쪽' 순서이며, 이진 탐색 트리는 '왼쪽 자식 \(<\) 루트 \(<\) 오른쪽 자식'의 대소 관계를 만족한다.

따라서 중위 순회에서는 항상 다음으로 작은 노드를 먼저 방문한다. 여기서 이진 탐색 트리의 중위 순회 결과는 오름차순이다라는 중요한 성질을 얻는다.

이 성질을 이용하면 별도 정렬 없이 \(O(n)\) 시간만으로 정렬된 데이터를 얻을 수 있어 매우 효율적이다.

이진 탐색 트리의 중위 순회 결과

그림 7-22 이진 탐색 트리의 중위 순회 결과

7.4.2 이진 탐색 트리의 효율¶

데이터 집합을 배열이나 이진 탐색 트리에 저장한다고 하자. 아래 표(7-2)를 보면 이진 탐색 트리의 각 연산은 로그 시간 복잡도로 안정적이고 효율적이다. 데이터 추가는 잦고 탐색과 삭제는 드문 상황에서만 배열이 더 효율적이다.

표 7-2 배열과 탐색 트리의 효율 비교

	정렬되지 않은 배열	이진 탐색 트리
원소 탐색	\(O(n)\)	\(O(\log n)\)
원소 삽입	\(O(1)\)	\(O(\log n)\)
원소 삭제	\(O(n)\)	\(O(\log n)\)

이상적인 경우 이진 탐색 트리는 '균형'을 이루므로 어떤 노드든 \(\log n\) 회의 반복 안에 찾을 수 있다.

하지만 삽입과 삭제를 계속하다 보면 아래 그림(7-23)의 연결 리스트로 퇴화할 수 있다. 이때 각 연산의 시간 복잡도도 \(O(n)\)으로 저하된다.

이진 탐색 트리의 퇴화

그림 7-23 이진 탐색 트리의 퇴화

7.4.3 이진 탐색 트리의 주요 응용¶

시스템의 다단계 인덱스로 사용하여 효율적인 탐색, 삽입, 삭제를 구현한다.
일부 탐색 알고리즘의 기반 자료 구조로 사용한다.
데이터 스트림을 저장하면서 정렬 상태를 유지한다.

7.4 이진 탐색 트리¶

7.4.1 이진 탐색 트리의 연산¶

1. 노드 탐색¶

2. 노드 삽입¶

3. 노드 삭제¶

4. 중위 순회 결과의 정렬 성질¶

7.4.2 이진 탐색 트리의 효율¶

7.4.3 이진 탐색 트리의 주요 응용¶

댓글로 의견이나 질문, 제안을 남겨 주세요