두 갈래 찾기 트리 개념과 관련leetcode 문제

개념

두 갈래로 나무를 찾는데, 두 갈래로 나무를 검색하는 것도 부른다.트리의 임의의 노드, 이 노드의 왼쪽 하위 트리의 모든 노드의 값은 이 노드의 값보다 작다.오른쪽 트리의 각 노드의 값은 이 노드의 값보다 크다.

찾다

루트 노드에서 찾기 시작하고 찾은 데이터가 루트 노드의 값과 같으면 되돌려줍니다.만약 찾은 데이터가 루트 노드의 값보다 작으면 왼쪽 트리에서 차례로 찾기;찾은 데이터가 루트 노드의 값보다 크면 오른쪽 하위 트리에서 차례로 찾습니다.

삽입

삽입된 데이터는 일반적으로 잎 노드에 놓여 있기 때문에 뿌리 노드부터 훑어본다.

만약에 삽입된 데이터가 노드의 데이터보다 크고 노드의 오른쪽 트리가 비어 있다면 삽입된 데이터를 오른쪽 트리 노드로 직접 한다.비어 있지 않으면 오른쪽 하위 트리를 반복해서 삽입 위치를 찾습니다..

같은 이치로 만약에 삽입된 데이터가 노드 데이터보다 작고 노드의 왼쪽 트리가 비어 있다면 삽입된 데이터를 왼쪽 트리 노드로 한다.비어 있지 않으면 왼쪽 트리를 반복해서 삽입 위치를 찾습니다..

삭제

두 갈래 찾기 트리를 삭제하는 작업은 세 가지 상황으로 나뉜다.
1. 삭제된 노드에 좌우 트리가 없으면 부모 노드를 삭제된 노드에 가리키는 바늘을 null로 설정합니다
2. 삭제된 노드에 하위 노드가 있으면 부모 노드의 삭제 노드를 가리키는 바늘을 삭제된 노드를 가리키는 하위 노드로 바꾼다
3. 삭제된 노드는 두 개의 하위 노드가 있습니다. 노드를 삭제한 오른쪽 트리에서 가장 작은 노드를 찾아서 가장 작은 노드를 삭제된 노드로 대체하고 마지막으로 가장 작은 노드를 삭제해야 합니다.

시간 복잡도

시간 복잡도와 나무의 높이는 정비례, 즉 o(height)
최악의 경우
만약 하위 노드가 어느 한쪽에 있다면 체인 테이블로 퇴화되고 시간 복잡도는 o(n)
2. 가장 안정적인 상황
n개 노드의 완전 두 갈래 트리에 대해 트리의 높이는 이 두 가지 사이에 있다.
n >= 1+2+4+8+…+2^(L-2)+1
n <= 1+2+4+8+…+2(L-2)+2(L-1)
L의 범위는 [log2(n+1),log2n+1]입니다.완전 두 갈래 나무의 층수는log(2저수)n+1보다 작다. 즉, 완전 두 갈래 나무의 높이는log(2저수)n보다 작다.
분명히 극도로 불균형적인 두 갈래 검색 트리의 검색 성능은 우리의 요구를 만족시킬 수 없을 것이다.우리는 데이터를 아무리 삭제하고 삽입해도 언제든지 임의의 노드 좌우 트리가 비교적 균형을 잡을 수 있는 두 갈래 찾기 트리를 구축해야 하기 때문에 특수한 두 갈래 찾기 트리, 균형 두 갈래 찾기 트리를 파생시켜야 한다.균형 두 갈래 검색 트리의 높이는logn에 가깝기 때문에 삽입, 삭제, 검색 작업의 시간 복잡도도 비교적 안정적이고 O(logn)이다.

실전 문제

leetcode 104문제, 어떻게 두 갈래 나무의 높이를 구합니까

public int maxDepth(TreeNode root) {

if (root == null) return 0;

if (root.left == null && root.right == null) return 1;

int leftDepth = maxDepth(root.left);

int rightDepth = maxDepth(root.right);

return leftDepth >= rightDepth ? leftDepth + 1 : rightDepth + 1;

}

leetcode 450문제, 두 갈래 트리 삭제 작업

public TreeNode deleteNode(TreeNode root, int key) {

TreeNode del = root;

TreeNode delParent = null;

//  

while (del != null) {

if (del.val == key) break;

if (key > del.val) {

delParent = del;

del = del.right;

} else {

delParent = del;

del = del.left;

}

}

if (del == null) return root;

//  ， 

if (del.left != null && del.right != null) {

TreeNode minDel = del.right;

TreeNode minDelParent = del;

while (minDel.left != null) {

minDelParent = minDel;

minDel = minDel.left;

}

del.val = minDel.val;

del = minDel;

delParent = minDelParent;

}

//  , 

TreeNode child;

if (del.left != null) child = del.left;

else if (del.right != null) child = del.right;

else child = null;

//  

if (delParent == null) return child;

else if (delParent.left == del) delParent.left = child;

else delParent.right = child;

return root;

}