데이터 구조 및 변화

집합 하 다.
산 목록
정의:
산 목록: 이 표 의 한 위치 에 요 소 를 매 핑 하여 접근 속 도 를 높 입 니 다. 장 착 인자: 원소 의 개수 / 표 의 길이 충돌: 여러 키워드 가 같은 위치 에 비 치 는 현상 충돌 검출 방안: 직접 주소 지정 법 과 링크 법 단순 일치 해시: 모든 요소 가 해시 되 었 을 때 독립 적 이 고 다른 요소 와 무관 합 니 다. 일치 산열: 모든 키워드 의 탐사 서열 을 가정 합 니 다 ` < 0, 1, 2,..., m - 1 > 의 m!중 배열 의 모든 가능성 은 같다. 키워드 집합 정적: 키워드 집합 은 표 에 저장 한 후 변 하지 않 습 니 다.
해시 함수 의 설계
즉 매 핑 함수. 좋 은 매 핑 함 수 는 간단 한 일치 해시 에 만족 해 야 합 니 다. 일반적으로 키워드 분포 의 제한 적 인 정 보 를 이용 하여 디자인 하 는데, 이 를 계발 식 이 라 고 한다.
곱셈 산열
hk = ka
나눗셈 산열
hk = k mod a
전역 해시 및 디자인
크기 가 m 인 표 에 작용 하 는 맵 함수 H 는 임의의 두 요 소 를 보장 할 수 있 으 며, 최대 | H | / m 개의 맵 함수 만 충돌 할 수 있 습 니 다. 이 디자인 의 평균 성능 이 비교적 좋다.
디자인:
큰 질량 p p > max (e) 를 선택 하 십시오. ha,b(k)=((ak+b)mod p)mod m Hp,m={ha,b:a∈Zp* ,b∈Zp} Hp, m 에는 모두 p (p - 1) 개의 해시 함수 가 있 습 니 다.
디자인 증명:
즉, 서로 다른 값 을 선택 하여 충돌 할 확률 이 1 / m 보다 크 지 않다 는 것 을 증명 한다. 1. 임의의 두 요소 k, l (k! = l) r = (ak + b) mod p s = (al + b) mod p 는 r 를 증명 할 수 있 습 니 다! =s 2 r s 로 a, b a = (r - s) (k - l) - 1 을 표시 할 수 있 습 니 다. mod p) mod p, b = (r - ak) mod p 는 중요 한 것 은 쌍 과 쌍 이 일일이 대응 한 다 는 것 을 증명 할 수 있다. 3. 주어진 r, p 의 선택 수량 은 p - 1 개 이 고 충돌 확률 r = s mod m 의 수량 은 최대 (p - 1) / m 이 므 로 충돌 확률 은 최대 1 / m 임 을 증명 할 수 있 습 니 다.
완전 산열
정의: 정적 집합 에서 최 악의 검색 은 O (1) 의 해시 기술 입 니 다.
디자인:
1 최 외곽 함 수 는 h (k) = (ak + b) mod p) mod m (전역 산열) 2 산열 표 S 의 크기 는 mj 이다 관련 해시 함 수 는 hj (k) = (ajk + bj) mod p) mod mj 입 니 다. 3 mj 는 이 pos 아래 에 떨 어 진 원소 개수 의 제곱 이다.
n 개의 키 워드 를 m = n2 의 산 목록 에 저장 하여 충돌 할 확률 이 1 / 2 보다 적 음 을 증명 합 니 다.
E(x)=Cn2 * 1n2 = n2n2*1n2 < 1/2
전체적인 기대 공간 이 O (n) E 임 을 증명 한다. ∑m1j=0nj^2] =E[ ∑m1j=0 (nj + 2Cnj2)]=n + 2E[∑m1j=0Cnj2]=n+2Cnj2 * 1m = n+2Cnj2 * 1n=n+2n12< 2n
개방 주소 법
모든 요 소 는 표 에 놓 여 있다.탐색 시퀀스 알고리즘 에 따라 충돌 시 다음 탐색 위 치 를 해결 합 니 다. 이 구 조 는 요 소 를 삭제 할 때 해당 하 는 위 치 를 비 워 두 지 않 고 deleted 표 시 를 설정 합 니 다. 선형 탐색 h (k, i) = (h (k) + ci) mod m 2 차 탐사 h (k, i) = (h (k) + c1i + c2i 2) mod m 이중 해시 h (k, i) = (h (k) + h2 (k) i) mod m
실.
창고.
후진 선 출 데이터 구조
대열
선진 적 인 데이터 구조
나무.
이 진 트 리
완전 이 진 트 리: 맨 아래 의 두 층 의 결점 만 2 보다 작 을 수 있 고 맨 아래 층 의 결점 은 모두 이 층 의 가장 왼쪽 에 있 는 몇 개의 위치 에 집 중 된 이 진 트 리 입 니 다. 만 이 진 트 리: 마지막 층 에 아무런 하위 노드 가 없 는 것 을 제외 하고 각 층 의 모든 결점 에는 두 개의 하위 결점 이 있 습 니 다. 이 진 트 리. 균형 이 진 트 리: 좌우 높이 의 차 이 는 1 을 초과 하지 않 고 모두 균형 이 진 트 리 입 니 다. 각 기본 작업 의 운행 시간 은 모두 O (h) h 가 트 리 의 높이 이다. avl 트 리 = 이 진 트 리 검색 + 밸 런 스
반동 적 인 서적
뿌리 노드 와 잎 노드 는 검은색 이 고 둘 사이 의 검은색 노드 의 개 수 는 같다.또 다른 나 무 는 빨 간 나무 이 고 그 부분 은 모두 검 은 나무 이다. 이것 은 빨 간 나무 이다. 최 악의 경우 조작 시간 은 O (lgn) 각 노드 (color, key, left, right, p)
좌선
장남 의 차남 은 자기 의 장남 이다 자 기 는 장남 의 차남 이다
우회전
차남 의 장남 은 제 차남 이다 자 기 는 차남 의 장남 이다
늘다
이 진 트 리 에 따라 걸 려 있 는 부모 노드 를 찾 아 직접 삽입 합 니 다. 색 은 빨간색 입 니 다. 증조: (빨간색 과 검은색 을 거꾸로 약칭) 백 홍 = > 아버님 이 나 를 쓰 러 뜨 렸 다. 백 흑 = > (나 는 장남 이다 = > 나 = 아버지 좌선) 아버지 투기꾼 우회전
삭제 하 다.
실제 삭제 할 노드 y (현재 노드 (쌍둥이 부전) 또는 후임) 를 확인 하기 때문에 y 는 쌍둥이 가 아 닙 니 다. y 의 대체 노드 x 확인 (유일한 아이 또는 비어 있 음) x 위로 y 대신 만약 y 가 어둡다 면 삭제 하 다 삭제: 비교적 번 거 로 우 니, 후속 추출
B 나무
정의 B 트 리 는 밸 런 스 (t +) 포크 트 리 t > = 2 는 최소 도수
일찍이
B - TREE - SPLIT - CHILD: 현재 노드 중간 키 워드 를 위 에 올 리 고 좌우 로 두 개 로 나 눕 니 다. B-TREE-INSERT-CHILD： 1 노드 가 2t - 1 일 때 뜯 기 2. 지정 한 node 위치 에 요 소 를 삽입 합 니 다. node 가 가득 차 면 뜯 습 니 다.(부모 노드 가 가득 차 면 뜯 기)
삭제 하 다.
1. 지정 한 요소 k 를 삭제 합 니 다. 이 요소 가 내 노드 에 있다 면.만약 에 적당 한 중계 또는 후계 e 가 있다 면 e 를 삭제 합 니 다.그렇지 않 으 면 k 를 삭제 하고 좌우 부분 노드 를 합병 합 니 다. 2. 합병 하면 합병 후 조정: 이 노드 요소 의 개 수 를 검사 하고 만족 하지 않 으 면 좌우 형제 에서 요 소 를 끌 거나 합병 합 니 다.
두 갈래 로 된 더미
부모 요소 가 하위 요소 보다 큰 만 이 진 트 리
이항적
병합 가능 더미
create, insert, min, pop, union 다섯 가지 조작 (추가 검사 삭제) 을 지원 하 는 데이터 구조
이항수
재 귀적 으로 정 의 된 질서 있 는 트 리두 개의 나무 B0 은 하나의 노드 만 포함 합 니 다.두 종목 나무 Bk 두 그루 의 Bk - 1 로 연결 되 어 있 으 며, 그 중 하 나 는 다른 나무의 왼쪽 아이 이다. 최소 순서: 노드 의 키 가 부모 노드 보다 크 거나 같은 키 입 니 다.
이항적
최 악의 경우 시간 복잡 도 는 lgn 이다. 최소한 의 질서 있 는 성질 을 가 진 두 나무의 집합 으로, 그 중 에는 근 도수 가 중복 되 는 원소 가 존재 하지 않 는 다 m 개 원소 두 개의 나무의 개 수 는 < = lg2m + 1 임 을 증명 하기 쉽다.
피 보 나치 더미
삭제 제외 한 나머지 작업 시간 은 O (1) 한 조 의 최소 질서 있 는 나무 로 구성 되 어 있 지만, 반드시 두 개의 나무 가 아 닙 니 다. 나무 뿌리 사 이 는 무질서 하고 나무 뿌리 와 각 나무 내 부 는 모두 쌍 사슬 이다.
그림.
선서, 중 서, 후 서
최소 생 성 트 리
무방 향 가중 연통 도 < G, E > ,E1 그룹 선택 ,E1 8712 ° E, 모든 정점 을 연결 할 수 있 습 니 다. min (E1) 을 구 합 니 다.
kruskal 알고리즘 (Oelge)
그림 의 최소 변 을 우선 수집 합 니 다. (이 변 의 두 정점 이 모두 알 고 있 는 정점 에 있 는 경 우 를 제외 하고)
Prim 알고리즘 (OelgV)
이미 알 고 있 는 정점 외곽 의 최소 변 을 수집 합 니 다.
단일 소스 최 단 경로
최 단 경로 추정: 모든 정점 v 8712 ° V 에 대해 하나의 속성 d [v] 를 설정 하여 원점 에서 v 까지 의 최 단 경로 의 상 계 를 설명 합 니 다. 이완 기술: 1. 각 정점 v 와 원점 u 간 의 최 단 경 로 를 초기 화 하 는 것 은 무한 으로 추정 된다. 겨냥 하 다
bellman - ford 알고리즘 (OEV)
각 정점 으로 각 변 을 이완 시 키 면 변 이 마이너스 인 상황 을 처리 할 수 있다.
dijkstra 알고리즘 (Ov2)
1. 정점 집합 S, S 변 에서 가장 짧 은 경로 의 정점 u 를 S 에 추가 합 니 다. 2 u 를 사용 하여 u 주위 의 변 을 이완 시킨다. 마이너스 로 처리 할 수 없 는 상황 입 니 다.
다 원 최 단 경로
정의: 각 정점 간 의 최 단 경 로 를 계산 합 니 다. 패 킷 닫 기: 모든 정점 사이 에 경로 가 존재 하 는 방향 도
floyd - warshall 알고리즘 (OV3)
임의의 정점 k 로 임의의 두 정점 < u, v > 사이 의 변 을 늦추다
johnson 알고리즘
Dijkstra 알고리즘 순서대로 실행 하기
최대 흐름
흐름 보존: 어떤 정점 에 들 어 가 는 속 도 는 이 정점 을 떠 나 는 속도 와 같다. 문제 설명: 용량 제한 에 어 긋 나 지 않 는 조건 에서 물질 을 원점 에서 외환 점 으로 전송 하 는 최대 속 도 는 얼마 입 니까? ford - fulkerson 방법 은 세 가지 중요 한 사상 에 의존 합 니 다. 잔류 네트워크, 확대 경로, 절단.
잔류 유량
Cf(u,v)=c(u,v)-f(u,v)
잔류 망
일류 네트워크 G = (V, E) 와 흐름 f 를 지정 합 니 다. f 로 눌 린 G 의 잔류 네트워크 는 Gf = (V, Ef) 입 니 다.
확장 경로
확장 경 로 는 잔류 네트워크 의 원점 에서 외환 점 까지 의 간단 한 경로 이다.
흐 르 는 네트워크 의 절단
네트워크 를 두 부분 으로 자 르 는 절단 법 최소 절단 은 최소 용량 의 절단 이다. 최대 흐름 최소 베 기 최소 베 기 최대 흐름
기본 ford - fulkerson 알고리즘
전치 0 2. 차례대로 확장 경로 p 를 찾 아 최소 용량 c 를 계산한다. 3. 이 경로 의 각 단락 경로 의 흐름 에 c 를 더 하면 각 단락 경로 의 용량 은 c 를 줄인다. 그래서 알고리즘 의 관건 은 어떻게 확장 경 로 를 찾 느 냐 하 는 것 이다.
edmonds - karp 알고리즘
광도 우선 알고리즘 을 사용 하여 확장 경 로 를 찾 습 니 다.
압 입 과 재 표기 알고리즘
잔류 네트워크 의 각 정점 의 인접 정점 을 순서대로 검사 하 는 것 을 정의 합 니 다. 두 가지 기본 작업: 1. 흐름 의 잔 량 을 한 정점 에서 다른 정점 으로 2 중 표시 합 니 다. 압착: 현재 노드 의 여 류 를 변 을 따라 이웃 점 으로 누른다. 다시 표시: 현재 가장 낮은 인접 점 의 높이 + 1